기하학(geometry)에서, 교차(intersection)는 (직선, 곡선, 평면, 및 표면과 같은) 둘 이상의 대상에 공통적인 점, 직선, 또는 곡선입니다. 유클리드 기하학(Euclidean geometry)에서 가장-간단한 경우는 두 구별되는 직선(lines)이 교차하는 것이며, 그것은 하나의 점(point) 또는 만약 직선들이 평행(parallel)하면 존재하지 않는 것 중 하나입니다.
플랫(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_1x+b_1y=c_1, \ a_2x+b_2y=c_2 \)의 교차 점의 결정에 대해, 우리는, 크라메르의 규칙(Cramer's rule) 또는 변수를 치환함으로써, 교차 점 \((x_s,y_s)\)의 좌표를 얻습니다:
\(\quad\displaystyle x_s=\frac{c_1b_2-c_2b_1}{a_1b_2-a_2b_1} , \quad y_s=\frac{a_1c_2-a_2c_1}{a_1b_2-a_2b_1}. \ \)
(만약 \( a_1b_2-a_2b_1=0\)이면 직선들은 평행이고 이들 공식은 사용될 수 없는데 왜냐하면 그것들은 0에 의한 나눗셈을 포함하기 때문입니다.)
Two line segments
두 비-평행 선분(line segment) \((x_1,y_1),(x_2,y_2)\) 및 \((x_3,y_3),(x_4,y_4)\)에 대해, 반드시 교차점이 있는 것은 아닌데 (다이어그램 참조), 왜냐하면 해당하는 직선의 교차 점 \((x_0,y_0)\)이 선분 안에 포함될 필요가 없기 때문입니다. 상황을 확인하기 위해, 우리는 직선의 매개변수적 표현을 사용합니다:
\(\quad (x(s),y(s))=(x_1+s(x_2-x_1),y_1+s(y_2-y_1)),\)
\(\quad (x(t),y(t))=(x_3+t(x_4-x_3),y_3+t(y_4-y_3)). \)
선분은 만약 해당하는 매개변수 \(s_0,t_0\)가 조건 \( 0\le s_0,t_0 \le 1 \)을 충족하면 해당하는 직선의 공통 점 \((x_0,y_0)\)에서 오직 교차합니다. 매개변수 \(s_0,t_0 \)는 선형 시스템의 해입니다:
\(\quad s(x_2-x_1)-t(x_4-x_3)=x_3-x_1,\)
\(\quad s(y_2-y_1)-t(y_4-y_3)=y_3-y_1 \ .\)
그것은 크래머의 규칙을 사용하여 s와 t에 대해 풀릴 수 있습니다 (위를 참조하십시오). 만약 조건 \( 0\le s_0,t_0 \le 1 \)이 충족되면, 우리는 \(s_0\) 또는 \(t_0\)를 해당하는 매개변수 표현에 삽입하고 교차 점 \((x_0,y_0)\)을 얻습니다.
예제: 선분 \((1,1),(3,2)\) 및 \((1,4),(2,-1)\)에 대해, 우리는 다음 선형 시스템을 얻습니다:
\(\quad 2s-t=0\)
\(\quad s+5t=3\)
그리고 \(s_0=\tfrac{3}{11}, t_0=\tfrac{6}{11}\)입니다. 이것은 직선이 점 \((\tfrac{17}{11},\tfrac{14}{11})\)에서 교차함을 의미합니다.
주의: 선분 대신에, 직선을 고려하면, 점의 쌍으로 결정되며, 각 조건 \( 0\le s_0,t_0 \le 1 \)은 버려질 수 있고 그 방법은 직선의 교차 점을 산출합니다 (위를 참조하십시오).
A line and a circle
다음의 교차에 대해
- 직선 \(ax+by=c\)와 원 \(x^2+y^2=r^2\)
우리는 x 또는 y에 대해 방정식을 풀고 그것을 원의 방정식에 대입(substitutes)하고, 만약 \( r^2(a^2+b^2)-c^2\ge0\)이면, 해 \((x_1,y_1),(x_2,y_2)\)에 대해 (이차 방정식의 공식을 사용하여) 다음을 얻습니다:
\(\quad\displaystyle x_{1/2}= \frac{ac\pm b\sqrt{r^2(a^2+b^2)-c^2}}{a^2+b^2} \ ,\)
\(\quad\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 \)를 보존하면, 오직 하나의 교차 점이 있고 그 직선은 원에 대한 접선입니다. 만약 약한 부등식이 보존되지 않으면, 그 직선은 원과 교차하지 않습니다.
만약 원의 중간점이 원점이 아니면, 참조하십시오. 직선과 포물선 또는 쌍곡선의 교차는 유사하게 취급될 수 있습니다.
Two circles
다음 두 원의 교차 점의 결정은
- \((x-x_1)^2+(y-y_1)^2=r_1^2 ,\ \quad (x-x_2)^2+(y-y_2)^2=r_2^2\)
직선과 원을 교차하는 것의 이전 경우로 추론될 수 있습니다. 두 주어진 방정식의 뺄셈에 의해, 우리는 직선 방정식을 얻습니다:
\(\quad 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)입니다.
특별한 경우 \(\;x_1=y_1=y_2=0 \) :
이 경우에서 원점은 첫 번째 원의 중심이고 두 번째 중심은 x-축 위에 놓입니다 (그림 참조).
근본 축의 방정식은 \(\;2x_2x=r_1^2-r_2^2+x_2^2\;\)로 단순화되고 교차의 점은 다음과 함께 \((x_0,\pm y_0)\)로 쓰일 수 있습니다:
\(\quad\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\)의 경우에서 그 원은 공통으로 점을 가지지 않습니다.
\(r_1^2=x_0^2\)의 경우에서 그 원은 공통으로 한 점을 가지고 근본 직선은 공통 접선입니다.
위에 쓰인 임의의 일반적인 경우는 이동과 회전에 의해 특수한 경우로 변환될 수 있습니다.
두 디스크(disks) (두 원의 내부)의 교차는 렌즈(lens)라고 불리는 모양을 형성합니다.
Two conic sections
타원/쌍곡선/포물선과 또 다른 원뿔 단면(conic section)의 교차 문제는 이차 방정식의 시스템(system of quadratic equations)으로 이어지며, 특수한 경우에서 하나의 좌표의 제거에 의해 쉽게 풀릴 수 있습니다. 원뿔 단면의 특수 속성은 해(solution)를 얻기 위해 사용될 수 있습니다. 일반적으로, 교차 점은 뉴턴 반복에 의한 방정식을 풂으로써 결정할 수 있습니다. 만약 a) 두 원뿔형이 이-차원 뉴턴 반복을 (방정식에 의해) 암시적으로 주어지면 b) 하나의 암시적으로 및 다른 하나의 매개변수적으로 주어진 1-차원 뉴턴 반복이 필요합니다. 다음 섹션을 참조하십시오.
Two smooth curves
\(\mathbb{R}^2\) (이-차원 공간)에서 두 곡선이, 이것들이 연속적으로 미분-가능하며 (즉, 날카로운 꺾어짐이 없음), 만약 그것들이 공통으로 평면의 점을 가지고 이 점에서 다음을 가지면 교차 점을 가집니다:
- a: 다른 접선 ((횡당(transversal) 교차), 또는
- b: 공통으로 접선과 그것들이 서로 교차하는 것 (접촉하는 교차, 다이어그램을 참조하십시오)
만약 두 곡선이 점 S과 공통으로 그곳에서 접선을 가지지만 서로 교차하지 않으면, 그것들은 점 S에서 단지 접촉하는 것입니다.
접촉 교차는 드물게 나타나고 다루는 것이 어렵기 때문에, 다음 고려-사항이 이 경우를 생략합니다. 아래의 임의의 경우에서 모든 필요한 미분 조건이 전제됩니다. 교차 점의 결정은 항상 뉴턴 반복에 의해 풀릴 수 있는 하나 또는 둘의 비-선형 방정식으로 이어집니다. 나타나는 경우의 목록은 다음과 같습니다:
- 만약 두 곡선이 명시적으로 주어지면: \( y=f_1(x), \ y=f_2(x)\),
- 그것들을 같게 하면 다음 방정식을 산출합니다:
- \(f_1(x)=f_2(x) \ .\)
- 만약 두 곡선이 매개변수적으로 주어지면: \(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) \ .\)
- 만약 하나의 곡선이 매개변수적으로 및 다른 하나는 암시적으로 주어지면: \(C_1: (x_1(t),y_1(t)), \ C_2: f(x,y)=0.\)
- 이것은 명시적인 경우를 제외하고 가장 간단한 경우입니다. 우리는 \(C_1\)의 매개변수적 표현을 곡선 \(C_2\)의 방정식 \(f(x,y)=0\)에 삽입해야 하고 우리는 다음 방정식을 얻습니다:
- \(f(x_1(t),y_2(t))=0 \ .\)
- 만약 두 곡선이 암시적으로 주어지면: \(C_1: f_1(x,y)=0, \ C_2: f_2(x,y)=0.\)
- 여기서, 교차 점은 다음 시스템의 해입니다:
- \(f_1(x,y)=0, \ f_2(x,y)=0 \ .\)
임의의 뉴턴 반복은 편리한 시작하는 값이 필요하며, 이것은 두 곡선의 시각화에 의해 유도될 수 있습니다. 매개변수적으로 또는 명시적으로 주어진 곡선은 쉽게 시각화될 수 있는데, 왜냐하면 임의의 매개변수 t 또는 x에 대해 각각 해당하는 점을 계산하기 쉽기 때문입니다. 암시적으로 주어진 곡선에 대해 이 작업은 쉽지 않습니다. 이 경우에서 우리는 시작하는 값과 반복의 도움과 함께 곡선 점을 결정해야 합니다. 참조하십시오.
예제:
- 1:\(C_1: (t,t^3)\)과 원 \(C_2: (x-1)^2+(y-1)^2-10=0\) (다이어그램을 참조).
- 다음 함수에 대해 뉴턴 반복 \(t_{n+1}:=t_n-\frac{f(t_n)}{f'(t_n)}\)이 행해져야 합니다:
- \(f(t)=(t-1)^2+(t^3-1)^2-10\). 시작 값으로 우리는 −1 및 1.5을 선택할 수 있습니다.
- 교차 점은 다음입니다: (−1.1073, −1.3578), (1.6011, 4.1046)
- 2:\(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 \) (다이어그램을 참조).
- 뉴턴 반복
- \({x_{n+1}\choose y_{n+1}}={x_{n}+\delta_x\choose y_n+\delta_y}\)은 수행되어야 하며, 여기서 \({\delta_x \choose \delta_y}\)는 점 \((x_n,y_n)\)에서 다음 선형 시스템의 해입니다:
- \(\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.5, 1) 및 (1, −0.5)를 선택할 수 있습니다. - 선형 시스템은 크래머의 규칙에 의해 풀릴 수 있습니다.
- 교차 점은 (−0.3686, 0.9953) 및 (0.9953, −0.3686)입니다.
Two polygons
만약 우리가 두 다각형(polygon)의 교차하는 점을 결정하기를 원하면, 우리는 다각형의 선분의 임의의 쌍의 교차를 확인할 수 있습니다 (위를 참조하십시오). 많은 선분을 갖는 다각형에 대해 이 방법은 다소 시간-소모적입니다. 실제에서 우리는 창 테스트를 사용함으로써 교차 알고리듬을 가속화합니다. 이 경우에서 우리는 다각형을 작은 부분-다각형으로 나누고 임의의 부분-다각형에 대해 가장 작은 창 (좌표 축에 평행한 변을 갖는 직사각형)을 결정합니다. 두 선분의 교차 점의 시간-소모적 결정을 시작하기 전에, 임의의 창의 쌍이 공통 점에 대해 테스트됩니다. 참조하십시오.
In space (three dimensions)
3-차원 공간에서 곡선과 표면 사이에 교차 점 (공통 점)이 있습니다. 다음 섹션에서 우리는 오직 횡당(transversal) 교차를 고려합니다.
A line and a plane
삼-차원의 [[general position|''일반적인 위치''(''general position'')]]''에서'' 직선과 평면의 교차는 하나의 점입니다.
공통적으로 공간에서 직선은 매개변수적으로 \( (x(t),y(t),z(t)) \) 표현되고 평면은 방정식 \(ax+by+cz=d\)에 의해 표현됩니다. 매개변수 표현을 방정식에 대입하면 교차 점 \((x(t_0),y(t_0),z(t_0))\)의 매개변수 \(t_0\)에 대해 다음 선형 방정식을 산출합니다:
\(\quad ax(t)+by(t)+cz(t)=d\ .\)
만약 선형 방정식이 해를 가지지 않으면, 직선은 평면 위에 놓이거나 그것에 평행합니다.
Three planes
만약 직선이 두 교차하는 평면 \(\varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2\)에 의해 정의되고 세 번째 평면 \(\varepsilon_3: \ \vec n_3\cdot\vec x=d_3 \)에 삽입되어야 하면, 세 평면의 공통 교차 점은 평가되어야 합니다.
선형 독립 법선 벡터 \( \vec n_1,\vec n_2, \vec n_3\)를 갖는 세 평면 \(\varepsilon_i: \ \vec n_i\cdot\vec x=d_i, \ i=1,2,3 \)은 다음 교차 점을 가집니다:
\(\quad\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)} \ .\)
증명에 대해, 우리는 스칼라 세-쌍 곱의 규칙을 사용하여 \(\vec n_i\cdot\vec p_0=d_i, \ i=1,2,3 , \)를 수립해야 합니다. 만약 스칼라 세-쌍 곱(scalar triple product)이 0과 같으면, 평면은 세-쌍 교차를 가지지 않거나 그것은 하나의 직선입니다 (또는 만약 모든 세 평면이 같은 것이면 하나의 평면입니다).
A curve and a surface
평면의 경우와 유사하게 다음의 경우는 1- 또는 3-차원 뉴턴 반복을 사용하여 풀릴 수 있는 비-선형 시스템으로 이어집니다.
- 매개변수 곡선 \(C: (x(t),y(t),z(t)) \)과
- 매개변수 표면 \(S: (x(u,v),y(u,v),z(u,v))\ ,\)
- 매개변수 곡선 \(C: (x(t),y(t),z(t)) \)과
- 암시적 표면 \( S: f(x,y,z)=0\ .\)
예제:
- 매개변수 곡선 \(C: (t,t^2,t^3)\)과
- 암시적 표면 \(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)에서 곡선과 표면의 교차는 이산 점으로 구성되지만, 곡선은 표면에 부분적으로 또는 전체적으로 포함될 수 있습니다.
Two surfaces
두 가로로 교차하는 표면은 교차 곡선(intersection curve)을 제공합니다. 가장 간단한 경우는 두 비-평행 평면의 교차 선입니다.
References
- Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN. Lecture notes, Technische Universität Darmstadt, October 2003, p. 17
- Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN. Lecture notes, Technische Universität Darmstadt, October 2003, p. 33
- Erich Hartmann: CDKG: Computerunterstützte Darstellende und Konstruktive Geometrie. Lecture notes, TU Darmstadt, 1997, p. 79 (PDF; 3,4 MB)
- Erich Hartmann: Geometry and Algorithms for COMPUTER AIDED DESIGN. Lecture notes, Technische Universität Darmstadt, October 2003, p. 93
Further reading
- Nicholas M. Patrikalakis and Takashi Maekawa, Shape Interrogation for Computer Aided Design and Manufacturing, Springer, 2002, ISBN 3540424547, 9783540424543, pp. 408. [1]
