기하학(geometry) 에서, 교차 (intersection )는 (직선, 곡선, 평면, 및 표면과 같은) 둘 이상의 대상에 공통적인 점, 직선, 또는 곡선입니다. 유클리드 기하학(Euclidean geometry) 에서 가장-간단한 경우는 두 구별되는 직선(lines) 이 교차하는 것이며, 그것은 하나의 점(point) 또는 만약 직선들이 평행(parallel) 하면 존재하지 않는 것 중 하나입니다.
The red dot represents the point at which the two lines intersect. 플랫(flats) – 선형 기하학적 대상은 더-높은-차원(dimension) 의 공간에서 삽입됩니다 – 의 교차의 결정은 선형 대수(linear algebra) 의 간단한 임무, 즉 선형 방정식의 시스템(system of linear equations) 의 해입니다. 일반적으로, 교차의 결정은 비-선형 방정식(non-linear equation) 으로 이어지며, 이것은 예를 들어 뉴턴 반복(Newton iteration) 을 사용하여, 수치적으로 해결(solved numerically) 될 수 있습니다. 직선과 원뿔 단면(conic section) (원, 타원, 포물선, 등.) 또는 이차-초곡면(quadric) (구, 원기둥, 쌍곡면체, 등.) 사이의 교차 문제는 쉽게 해결될 수 있는 이차 방정식(quadratic equation) 으로 이어집니다. 이차-초곡면 사이의 교차는 대수적으로(algebraically) 해결될 수 있는 사차 방정식(quartic equation) 으로 이어집니다.
On a plane Two lines 두 비-평행 직선
a
1
x
+
b
1
y
=
c
1
,
a
2
x
+
b
2
y
=
c
2
{\displaystyle a_{1}x+b_{1}y=c_{1},\ a_{2}x+b_{2}y=c_{2}}
크라메르의 규칙(Cramer's rule) 또는 변수를 치환함으로써, 교차 점
(
x
s
,
y
s
)
{\displaystyle (x_{s},y_{s})}
x
s
=
c
1
b
2
−
c
2
b
1
a
1
b
2
−
a
2
b
1
,
y
s
=
a
1
c
2
−
a
2
c
1
a
1
b
2
−
a
2
b
1
.
{\displaystyle x_{s}={\frac {c_{1}b_{2}-c_{2}b_{1}}{a_{1}b_{2}-a_{2}b_{1}}},\quad y_{s}={\frac {a_{1}c_{2}-a_{2}c_{1}}{a_{1}b_{2}-a_{2}b_{1}}}.\ }
(만약
a
1
b
2
−
a
2
b
1
=
0
{\displaystyle a_{1}b_{2}-a_{2}b_{1}=0}
Two line segments Intersection of two line segments 두 비-평행 선분(line segment)
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
{\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}
(
x
3
,
y
3
)
,
(
x
4
,
y
4
)
{\displaystyle (x_{3},y_{3}),(x_{4},y_{4})}
(
x
0
,
y
0
)
{\displaystyle (x_{0},y_{0})}
(
x
(
s
)
,
y
(
s
)
)
=
(
x
1
+
s
(
x
2
−
x
1
)
,
y
1
+
s
(
y
2
−
y
1
)
)
,
{\displaystyle (x(s),y(s))=(x_{1}+s(x_{2}-x_{1}),y_{1}+s(y_{2}-y_{1})),}
(
x
(
t
)
,
y
(
t
)
)
=
(
x
3
+
t
(
x
4
−
x
3
)
,
y
3
+
t
(
y
4
−
y
3
)
)
.
{\displaystyle (x(t),y(t))=(x_{3}+t(x_{4}-x_{3}),y_{3}+t(y_{4}-y_{3})).}
선분은 만약 해당하는 매개변수
s
0
,
t
0
{\displaystyle s_{0},t_{0}}
0
≤
s
0
,
t
0
≤
1
{\displaystyle 0\leq s_{0},t_{0}\leq 1}
(
x
0
,
y
0
)
{\displaystyle (x_{0},y_{0})}
s
0
,
t
0
{\displaystyle s_{0},t_{0}}
s
(
x
2
−
x
1
)
−
t
(
x
4
−
x
3
)
=
x
3
−
x
1
,
{\displaystyle s(x_{2}-x_{1})-t(x_{4}-x_{3})=x_{3}-x_{1},}
s
(
y
2
−
y
1
)
−
t
(
y
4
−
y
3
)
=
y
3
−
y
1
.
{\displaystyle s(y_{2}-y_{1})-t(y_{4}-y_{3})=y_{3}-y_{1}\ .}
그것은 크라메르의 규칙을 사용하여 s 와 t 에 대해 풀릴 수 있습니다 (위를 참조하십시오). 만약 조건
0
≤
s
0
,
t
0
≤
1
{\displaystyle 0\leq s_{0},t_{0}\leq 1}
s
0
{\displaystyle s_{0}}
t
0
{\displaystyle t_{0}}
(
x
0
,
y
0
)
{\displaystyle (x_{0},y_{0})}
예제: 선분
(
1
,
1
)
,
(
3
,
2
)
{\displaystyle (1,1),(3,2)}
(
1
,
4
)
,
(
2
,
−
1
)
{\displaystyle (1,4),(2,-1)}
2
s
−
t
=
0
{\displaystyle 2s-t=0}
s
+
5
t
=
3
{\displaystyle s+5t=3}
그리고
s
0
=
3
11
,
t
0
=
6
11
{\displaystyle s_{0}={\tfrac {3}{11}},t_{0}={\tfrac {6}{11}}}
(
17
11
,
14
11
)
{\displaystyle ({\tfrac {17}{11}},{\tfrac {14}{11}})}
주의: 선분 대신에, 직선을 고려하면, 점의 쌍으로 결정되며, 각 조건
0
≤
s
0
,
t
0
≤
1
{\displaystyle 0\leq s_{0},t_{0}\leq 1}
위를 참조하십시오).
Line–circle intersection A line and a circle 다음의 교차에 대해
직선
a
x
+
b
y
=
c
{\displaystyle ax+by=c}
원
x
2
+
y
2
=
r
2
{\displaystyle x^{2}+y^{2}=r^{2}}
우리는 x 또는 y 에 대해 방정식을 풀고 그것을 원의 방정식에 대입(substitutes) 하고, 만약
r
2
(
a
2
+
b
2
)
−
c
2
≥
0
{\displaystyle r^{2}(a^{2}+b^{2})-c^{2}\geq 0}
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
{\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}
x
1
/
2
=
a
c
±
b
r
2
(
a
2
+
b
2
)
−
c
2
a
2
+
b
2
,
{\displaystyle x_{1/2}={\frac {ac\pm b{\sqrt {r^{2}(a^{2}+b^{2})-c^{2}}}}{a^{2}+b^{2}}}\ ,}
y
1
/
2
=
b
c
∓
a
r
2
(
a
2
+
b
2
)
−
c
2
a
2
+
b
2
.
{\displaystyle y_{1/2}={\frac {bc\mp a{\sqrt {r^{2}(a^{2}+b^{2})-c^{2}}}}{a^{2}+b^{2}}}\ .}
만약 이 조건이 엄격한 부등식을 보존하면, 두 교차 점이 있습니다; 이 경우에서 그 직선은 원의 가름 선(secant line) 이라고 불리고, 교차 점을 포함하는 선분은 원의 현(chord) 이라고 불립니다.
만약
r
2
(
a
2
+
b
2
)
−
c
2
=
0
{\displaystyle r^{2}(a^{2}+b^{2})-c^{2}=0}
만약 원의 중간점이 원점이 아니면, 참조하십시오.[1]
Two circles 다음 두 원의 교차 점의 결정은
(
x
−
x
1
)
2
+
(
y
−
y
1
)
2
=
r
1
2
,
(
x
−
x
2
)
2
+
(
y
−
y
2
)
2
=
r
2
2
{\displaystyle (x-x_{1})^{2}+(y-y_{1})^{2}=r_{1}^{2},\ \quad (x-x_{2})^{2}+(y-y_{2})^{2}=r_{2}^{2}}
직선과 원을 교차하는 것의 이전 경우로 추론될 수 있습니다. 두 주어진 방정식의 뺄셈에 의해, 우리는 직선 방정식을 얻습니다:
2
(
x
2
−
x
1
)
x
+
2
(
y
2
−
y
1
)
y
=
r
1
2
−
x
1
2
−
y
1
2
−
r
2
2
+
x
2
2
+
y
2
2
.
{\displaystyle 2(x_{2}-x_{1})x+2(y_{2}-y_{1})y=r_{1}^{2}-x_{1}^{2}-y_{1}^{2}-r_{2}^{2}+x_{2}^{2}+y_{2}^{2}.}
이 특별한 직선은 두 원의 근본 직선(radical line) 입니다.
Intersection of two circles with centers on the x-axis, their radical line is dark red 특별한 경우
x
1
=
y
1
=
y
2
=
0
{\displaystyle \;x_{1}=y_{1}=y_{2}=0}
2
x
2
x
=
r
1
2
−
r
2
2
+
x
2
2
{\displaystyle \;2x_{2}x=r_{1}^{2}-r_{2}^{2}+x_{2}^{2}\;}
(
x
0
,
±
y
0
)
{\displaystyle (x_{0},\pm y_{0})}
x
0
=
r
1
2
−
r
2
2
+
x
2
2
2
x
2
,
y
0
=
r
1
2
−
x
0
2
.
{\displaystyle x_{0}={\frac {r_{1}^{2}-r_{2}^{2}+x_{2}^{2}}{2x_{2}}},\quad y_{0}={\sqrt {r_{1}^{2}-x_{0}^{2}}}\ .}
r
1
2
<
x
0
2
{\displaystyle r_{1}^{2}<x_{0}^{2}}
r
1
2
=
x
0
2
{\displaystyle r_{1}^{2}=x_{0}^{2}}
위에 쓰인 임의의 일반적인 경우는 이동과 회전에 의해 특수한 경우로 변환될 수 있습니다.
두 디스크(disks) (두 원의 내부)의 교차는 렌즈(lens) 라고 불리는 모양을 형성합니다.
circle–ellipse intersection Two conic sections 타원/쌍곡선/포물선과 또 다른 원뿔 단면(conic section) 의 교차 문제는 이차 방정식의 시스템(system of quadratic equations) 으로 이어지며, 특수한 경우에서 하나의 좌표의 제거에 의해 쉽게 풀릴 수 있습니다. 원뿔 단면의 특수 속성은 해(solution) 를 얻기 위해 사용될 수 있습니다. 일반적으로, 교차 점은 뉴턴 반복에 의한 방정식을 풂으로써 결정할 수 있습니다. 만약 a) 두 원뿔형이 이-차원 뉴턴 반복을 (방정식에 의해) 암시적으로 주어지면 b) 하나의 암시적으로 및 다른 하나의 매개변수적으로 주어진 1-차원 뉴턴 반복이 필요합니다. 다음 섹션을 참조하십시오.
Two smooth curves A transversal intersection of two curves touching intersection (left), touching (right)
R
2
{\displaystyle \mathbb {R} ^{2}}
a: 다른 접선 ((횡당 (transversal )교차 ), 또는
b: 공통으로 접선과 그것들이 서로 교차하는 것 (접촉하는 교차 , 다이어그램을 참조하십시오) 만약 두 곡선이 점 S 과 공통으로 그곳에서 접선을 가지지만 서로 교차하지 않으면, 그것들은 점 S 에서 단지 접촉하는 것입니다.
접촉 교차는 드물게 나타나고 다루는 것이 어렵기 때문에, 다음 고려-사항이 이 경우를 생략합니다. 아래의 임의의 경우에서 모든 필요한 미분 조건이 전제됩니다. 교차 점의 결정은 항상 뉴턴 반복에 의해 풀릴 수 있는 하나 또는 둘의 비-선형 방정식으로 이어집니다. 나타나는 경우의 목록은 다음과 같습니다:
intersection of a parametric curve and an implicit curve intersection of two implicit curves 만약 두 곡선이 명시적으로 주어지면:
y
=
f
1
(
x
)
,
y
=
f
2
(
x
)
{\displaystyle y=f_{1}(x),\ y=f_{2}(x)}
그것들을 같게 하면 다음 방정식을 산출합니다:
f
1
(
x
)
=
f
2
(
x
)
.
{\displaystyle f_{1}(x)=f_{2}(x)\ .}
만약 두 곡선이 매개변수적으로 주어지면:
C
1
:
(
x
1
(
t
)
,
y
1
(
t
)
)
,
C
2
:
(
x
2
(
s
)
,
y
2
(
s
)
)
.
{\displaystyle C_{1}:(x_{1}(t),y_{1}(t)),\ C_{2}:(x_{2}(s),y_{2}(s)).}
그것들을 같게 하면 두 변수에서 두 방정식을 산출합니다:
x
1
(
t
)
=
x
2
(
s
)
,
y
1
(
t
)
=
y
2
(
s
)
.
{\displaystyle x_{1}(t)=x_{2}(s),\ y_{1}(t)=y_{2}(s)\ .}
만약 하나의 곡선이 매개변수적으로 및 다른 하나는 암시적으로 주어지면:
C
1
:
(
x
1
(
t
)
,
y
1
(
t
)
)
,
C
2
:
f
(
x
,
y
)
=
0.
{\displaystyle C_{1}:(x_{1}(t),y_{1}(t)),\ C_{2}:f(x,y)=0.}
이것은 명시적인 경우를 제외하고 가장 간단한 경우입니다. 우리는
C
1
{\displaystyle C_{1}}
C
2
{\displaystyle C_{2}}
f
(
x
,
y
)
=
0
{\displaystyle f(x,y)=0}
f
(
x
1
(
t
)
,
y
2
(
t
)
)
=
0
.
{\displaystyle f(x_{1}(t),y_{2}(t))=0\ .}
만약 두 곡선이 암시적으로 주어지면:
C
1
:
f
1
(
x
,
y
)
=
0
,
C
2
:
f
2
(
x
,
y
)
=
0.
{\displaystyle C_{1}:f_{1}(x,y)=0,\ C_{2}:f_{2}(x,y)=0.}
여기서, 교차 점은 다음 시스템의 해입니다:
f
1
(
x
,
y
)
=
0
,
f
2
(
x
,
y
)
=
0
.
{\displaystyle f_{1}(x,y)=0,\ f_{2}(x,y)=0\ .}
임의의 뉴턴 반복은 편리한 시작하는 값이 필요하며, 이것은 두 곡선의 시각화에 의해 유도될 수 있습니다. 매개변수적으로 또는 명시적으로 주어진 곡선은 쉽게 시각화될 수 있는데, 왜냐하면 임의의 매개변수 t 또는 x 에 대해 각각 해당하는 점을 계산하기 쉽기 때문입니다. 암시적으로 주어진 곡선에 대해 이 작업은 쉽지 않습니다. 이 경우에서 우리는 시작하는 값과 반복의 도움과 함께 곡선 점을 결정해야 합니다. 참조하십시오.[2]
예제:
1:
C
1
:
(
t
,
t
3
)
{\displaystyle C_{1}:(t,t^{3})}
C
2
:
(
x
−
1
)
2
+
(
y
−
1
)
2
−
10
=
0
{\displaystyle C_{2}:(x-1)^{2}+(y-1)^{2}-10=0}
다음 함수에 대해 뉴턴 반복
t
n
+
1
:=
t
n
−
f
(
t
n
)
f
′
(
t
n
)
{\displaystyle t_{n+1}:=t_{n}-{\frac {f(t_{n})}{f'(t_{n})}}}
f
(
t
)
=
(
t
−
1
)
2
+
(
t
3
−
1
)
2
−
10
{\displaystyle f(t)=(t-1)^{2}+(t^{3}-1)^{2}-10}
교차 점은 다음입니다: (−1.1073, −1.3578), (1.6011, 4.1046)
2:
C
1
:
f
1
(
x
,
y
)
=
x
4
+
y
4
−
1
=
0
,
{\displaystyle C_{1}:f_{1}(x,y)=x^{4}+y^{4}-1=0,}
C
2
:
f
2
(
x
,
y
)
=
(
x
−
0.5
)
2
+
(
y
−
0.5
)
2
−
1
=
0
{\displaystyle C_{2}:f_{2}(x,y)=(x-0.5)^{2}+(y-0.5)^{2}-1=0}
뉴턴 반복
(
x
n
+
1
y
n
+
1
)
=
(
x
n
+
δ
x
y
n
+
δ
y
)
{\displaystyle {x_{n+1} \choose y_{n+1}}={x_{n}+\delta _{x} \choose y_{n}+\delta _{y}}}
(
δ
x
δ
y
)
{\displaystyle {\delta _{x} \choose \delta _{y}}}
(
x
n
,
y
n
)
{\displaystyle (x_{n},y_{n})}
(
∂
f
1
∂
x
∂
f
1
∂
y
∂
f
2
∂
x
∂
f
2
∂
y
)
(
δ
x
δ
y
)
=
(
−
f
1
−
f
2
)
{\displaystyle {\begin{pmatrix}{\frac {\partial f_{1}}{\partial x}}&{\frac {\partial f_{1}}{\partial y}}\\{\frac {\partial f_{2}}{\partial x}}&{\frac {\partial f_{2}}{\partial y}}\end{pmatrix}}{\delta _{x} \choose \delta _{y}}={-f_{1} \choose -f_{2}}}
선형 시스템은 크라메르의 규칙에 의해 풀릴 수 있습니다.
교차 점은 (−0.3686, 0.9953) 및 (0.9953, −0.3686)입니다. Two polygons intersection of two polygons: window test 만약 우리가 두 다각형(polygon) 의 교차하는 점을 결정하기를 원하면, 우리는 다각형의 선분의 임의의 쌍의 교차를 확인할 수 있습니다 (위를 참조하십시오). 많은 선분을 갖는 다각형에 대해 이 방법은 다소 시간-소모적입니다. 실제에서 우리는 창 테스트 를 사용함으로써 교차 알고리듬을 가속화합니다. 이 경우에서 우리는 다각형을 작은 부분-다각형으로 나누고 임의의 부분-다각형에 대해 가장 작은 창 (좌표 축에 평행한 변을 갖는 직사각형)을 결정합니다. 두 선분의 교차 점의 시간-소모적 결정을 시작하기 전에, 임의의 창의 쌍이 공통 점에 대해 테스트됩니다. 참조하십시오.[3]
In space (three dimensions) 3-차원 공간에서 곡선과 표면 사이에 교차 점 (공통 점)이 있습니다. 다음 섹션에서 우리는 오직 횡당 (transversal )교차 를 고려합니다.
A line and a plane Line–plane intersection 삼-차원의 일반적인 위치 (general position )에서 직선과 평면의 교차는 하나의 점입니다.
공통적으로 공간에서 직선은 매개변수적으로
(
x
(
t
)
,
y
(
t
)
,
z
(
t
)
)
{\displaystyle (x(t),y(t),z(t))}
a
x
+
b
y
+
c
z
=
d
{\displaystyle ax+by+cz=d}
(
x
(
t
0
)
,
y
(
t
0
)
,
z
(
t
0
)
)
{\displaystyle (x(t_{0}),y(t_{0}),z(t_{0}))}
t
0
{\displaystyle t_{0}}
a
x
(
t
)
+
b
y
(
t
)
+
c
z
(
t
)
=
d
.
{\displaystyle ax(t)+by(t)+cz(t)=d\ .}
만약 선형 방정식이 해를 가지지 않으면, 직선은 평면 위에 놓이거나 그것에 평행합니다.
Three planes 만약 직선이 두 교차하는 평면
ε
i
:
n
→
i
⋅
x
→
=
d
i
,
i
=
1
,
2
{\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2}
ε
3
:
n
→
3
⋅
x
→
=
d
3
{\displaystyle \varepsilon _{3}:\ {\vec {n}}_{3}\cdot {\vec {x}}=d_{3}}
선형 독립 법선 벡터
n
→
1
,
n
→
2
,
n
→
3
{\displaystyle {\vec {n}}_{1},{\vec {n}}_{2},{\vec {n}}_{3}}
ε
i
:
n
→
i
⋅
x
→
=
d
i
,
i
=
1
,
2
,
3
{\displaystyle \varepsilon _{i}:\ {\vec {n}}_{i}\cdot {\vec {x}}=d_{i},\ i=1,2,3}
p
→
0
=
d
1
(
n
→
2
×
n
→
3
)
+
d
2
(
n
→
3
×
n
→
1
)
+
d
3
(
n
→
1
×
n
→
2
)
n
→
1
⋅
(
n
→
2
×
n
→
3
)
.
{\displaystyle {\vec {p}}_{0}={\frac {d_{1}({\vec {n}}_{2}\times {\vec {n}}_{3})+d_{2}({\vec {n}}_{3}\times {\vec {n}}_{1})+d_{3}({\vec {n}}_{1}\times {\vec {n}}_{2})}{{\vec {n}}_{1}\cdot ({\vec {n}}_{2}\times {\vec {n}}_{3})}}\ .}
증명에 대해, 우리는 스칼라 세-쌍 곱의 규칙을 사용하여
n
→
i
⋅
p
→
0
=
d
i
,
i
=
1
,
2
,
3
,
{\displaystyle {\vec {n}}_{i}\cdot {\vec {p}}_{0}=d_{i},\ i=1,2,3,}
스칼라 세-쌍 곱(scalar triple product) 이 0과 같으면, 평면은 세-쌍 교차를 가지지 않거나 그것은 하나의 직선입니다 (또는 만약 모든 세 평면이 같은 것이면 하나의 평면입니다).
A curve and a surface intersection of curve
(
t
,
t
2
,
t
3
)
{\displaystyle (t,t^{2},t^{3})}
x
4
+
y
4
+
z
4
=
1
{\displaystyle x^{4}+y^{4}+z^{4}=1}
평면의 경우와 유사하게 다음의 경우는 1- 또는 3-차원 뉴턴 반복을 사용하여 풀릴 수 있는 비-선형 시스템으로 이어집니다.[4]
매개변수 곡선
C
:
(
x
(
t
)
,
y
(
t
)
,
z
(
t
)
)
{\displaystyle C:(x(t),y(t),z(t))}
매개변수 표면
S
:
(
x
(
u
,
v
)
,
y
(
u
,
v
)
,
z
(
u
,
v
)
)
,
{\displaystyle S:(x(u,v),y(u,v),z(u,v))\ ,}
매개변수 곡선
C
:
(
x
(
t
)
,
y
(
t
)
,
z
(
t
)
)
{\displaystyle C:(x(t),y(t),z(t))}
암시적 표면
S
:
f
(
x
,
y
,
z
)
=
0
.
{\displaystyle S:f(x,y,z)=0\ .}
예제:
매개변수 곡선
C
:
(
t
,
t
2
,
t
3
)
{\displaystyle C:(t,t^{2},t^{3})}
암시적 표면
S
:
x
4
+
y
4
+
z
4
−
1
=
0
{\displaystyle S:x^{4}+y^{4}+z^{4}-1=0}
교차 점은 다음입니다: (−0.8587, 0.7374, −0.6332), (0.8587, 0.7374, 0.6332). 직선–구 교차(line–sphere intersection) 는 단순한 특수 경우입니다.
직선과 평면의 경우와 마찬가지로, 일반적인 위치 (general position )에서 곡선과 표면의 교차는 이산 점으로 구성되지만, 곡선은 표면에 부분적으로 또는 전체적으로 포함될 수 있습니다.
A line and a polyhedron Two surfaces 두 가로로 교차하는 표면은 교차 곡선(intersection curve) 을 제공합니다. 가장 간단한 경우는 두 비-평행 평면의 교차 선입니다.
See also References
^ Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN
^ Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN
^ Erich Hartmann: CDKG: Computerunterstützte Darstellende und Konstruktive Geometrie
^ Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN
Further reading Nicholas M. Patrikalakis and Takashi Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing , Springer, 2002, ISBN 3540424547 , 9783540424543, pp. 408. [1]
