[Geometry] 외적을 이용해 선분간의 교차점을 구하는 방법
📄외적을 이용한 선분과 선분의 교차점 구하기
선분은 기하를 구성하는 기본요소이기 때문에 선분의 교차점을 구하는 것은 기하 문제의 기본입니다. 이런 선분의 교차점은 다양한 곳에서 사용 할 수 있습니다.
하지만 교차점을 구하는 것은 여러 변수들이 존재해서 생각보다 까다롭습니다.
✏️직선과 직선의 교차점
선분은 직선의 일부분이기에 먼저 직선과 직선의 교차점을 구합니다.
좌표평면에서 두 직선에 대한 방정식을 x, y에 대해 세우고 연립 방정식을 푸는 것을 코드로 작성 할 수 있다. 하지만 그러면 수평과 수직에 대한 예외를 따로 처리해야해 코드가 간결하지 못합니다.
그렇다면 두 직선을 벡터로 표현 하고 벡터의 연산을 이용해 연립방정식을 풀면 외적으로 표현된 간결한 해를 얻을 수 있습니다.
✏️방정식 풀이1
\(\overrightarrow{a_x} + p\overrightarrow{b_x} = \overrightarrow{c_x} + q\overrightarrow{d_x}\)
\(\overrightarrow{a_y} + p\overrightarrow{b_y} = \overrightarrow{c_y} + q\overrightarrow{d_y}\)
이 연립방정식을 p에 대해 풀면 다음과 같습니다.
이 때 분모가 0인 경우는 두 직선이 평행한 경우로 교점이 정의되지 않습니다.
이제 p를 외적으로 더 간략하게 나타낼 수 있습니다.
\(p=\frac{(\overrightarrow{c}-\overrightarrow{a})\times\overrightarrow{d}}{\overrightarrow{b}\times\overrightarrow{d} }(\overrightarrow{b}\times\overrightarrow{d}\neq 0)\)
💻코드
// 점 a, b를 지나는 직선과 점 c, d를 지나는 직선의 교차점 x를 반환한다.
// 두 직선이 평행하면 false, 아니면 true를 반환한다.
public bool lineIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d, ref Vector2 x)
{
// 분모
float det = Vector3.Cross((Vector3)(b - a), (Vector3)(d - c)).z;
// 두 직선이 평행한 경우라면
if (Mathf.Abs(det) < 0.00005f) return false;
x = a + (b - a) * (Cross(c - a, d - c) / det);
return true;
}
public float Cross(Vector2 a, Vector2 b)
{
return Vector3.Cross((Vector3)a, (Vector3)b).z;
}
✏️방정식 풀이2
선분의 시작점을 $S_1$과 $S_2$이라고 하고 $S_{1}+ tP_{1}, S_{2}+ uP_2$ 으로 각각 두 선분 상의 임의의 점으로 나타낼 수 있습니다. 그렇다는 것은 $S_{1}+ tP_{1}= S_{2}+ uP_2$ 일때가 두 선분이 교차하는 지점이라는 뜻이고 u와 t에 대해서 방정식을 풀 수있다면 교차점을 구할 수 있습니다.
t나 u를 구하기 위해서는 두 변수 중 하나를 제거해야 하며, 이를 외적을 통해 해결할 수 있습니다. 외적은 두 벡터가 평행할 때 0이 되는 성질을 이용합니다. 따라서 t와 곱해져 있는 벡터와 동일한 벡터를 양쪽에 외적해 주면 됩니다. 자기 자신을 외적하면 0이 되기 때문에, 양쪽에 P₁이나 P₂를 외적하여 구할 수 있습니다.
\(S_{1}+ tP_{1}= S_{2}+ uP_2\)
\((S_{1}+ tP_{1})\times P_{1}= (S_{2}+ uP_{2)} \times P_1\)
\(S_{1} \times P_{1}= S_{2} \times P_{1}+ u(P_{2}\times P_1)\)
\(\frac{(S_{1} - S_{2}) \times P_1}{P_{2} \times P_{1}}= u\)
\(S_{1}+ tP_{1}= S_{2}+ uP_2\)
\((S_{1}+ tP_{1})\times P_{2}= (S_{2}+ uP_{2)} \times P_2\)
\(S_{2} + P_{2}= S_{1} \times P_{2}+ t(P_{1}\times P_2)\)
\(\frac{(S_{2} - S_{1}) \times P_2}{P_{1} \times P_{2}}= t\)
방정식 풀이
💻코드
public bool IsIntersectingSegments(Segment s, bool includeEndPoints = true)
{
Point p1 = End - Start, p2 = s.End - s.Start;
float rxs = Cross(p1, p2);
// 두 선분이 평행하면 false다
if (FloatZero(rxs)) return false;
// a_x + ub_x = c_x + td_x // a_y + ub_y = c_y + td_y // 이 식을 u나 t에대해서 풀고 외적으로 표현할 수도 있고
// a + ub = c + td
// (a + ub) X b = (c + td) X b : X는 외적
// 각각 b나 d를 외적해서 u나 b 하나를 없애고 나머지 하나에 대해서 연립해서 풀수도 있다.
float u = Cross(this.Start - s.Start, p1) / -rxs;
float t = Cross(s.Start - this.Start, p2) / rxs;
// u와 t는 각각의 선분에서의 보간(Lerp) 비율을 나타내는 값이다.
if (includeEndPoints) return u >= 0 && u <= 1 && t >= 0 && t <= 1;
// 교차점이 끝에 걸려있는지 체크한다.
else return u > 0 && u < 1 && t > 0 && t < 1;
}
// 교차점을 구하는 함수
public Point Intersection(Segment s)
{
if (s is null || !IsIntersectingSegments(s)) return null;
// 겹쳐져 있다면 결국 두 선분 사이에 있다는 뜻
// 그러니 교차점의 t(alpha) 값을 구하는 공식을 써서 교차점을 반환해준다.
Point p1 = End - Start, p2 = s.End - s.Start;
float rxs = Cross(p1, p2);
float t = Cross(s.Start - Start, p2) / rxs;
return Start + new Point(t * p1.x, t * p1.y);
}
✏️선분과 선분의 교차점
선분은 생각외로 직선보다 고려해야할 사항이 많습니다.
두 선분이 모두 한 직선 위에 있는 경우에 처리하기가 힘듭니다.
- 두 선분이 서로 겹치지 않는다
- 두 선분이 한점에 닿는다
- 두 선분이 겹쳐진다
- 한 선분이 다른 선분안에 포함된다
원래는 첫번째의 경우만 겹쳐지지 않지만 위에서 작성한 코드로는 2,3,4도 겹쳐지지 않았다고 판별하기 때문입니다.
💻코드
// 선분 a, b 선분 c, d가 평행하면 한 점에서 겹치는지 확인한다.
bool paralleSegments(Vector2 a, Vector2 b, Vector2 c, Vector2 d, ref Vector2 p)
{
if (b.x < a.x && b.y < a.y) Swap(ref a, ref b);
if (d.x < c.x && d.y < c.y) Swap(ref c, ref d);
// 한 직선위에 없거나 두 선분이 겹치지 않는 경우를 우선 걸러낸다.
if (ccw(a, b, c) != 0 || (b.x < c.x && b.y < c.y) || (d.x < a.x && d.y < a.y)) return false;
// 두 선분이 겹친다면 교차점 하나를 찾는다.
if (a.x < c.x && a.y < c.y) p = c;
else p = a;
return true;
}
// - p가 두 점 a, b를 감싸면서 각 변이 x, y축에 평행한 최소사각형 내부에 있는지 확인한다.
// a, b, p는 일직선 상에 있다고 가정한다.
bool inBoundingRectangle(Vector2 p, Vector2 a, Vector2 b)
{
if (b.x < a.x && b.y < a.y) Swap(ref a, ref b);
return p == a || p == b || ((a.x < p.x && a.y < p.y) && (p.x < b.x && p.y < b.y));
}
// - 두 점 a, b를 지나는 선분과 두 점 c, b를 지나는 선분을 p에 반환한다.
// - 교점이 여러개일 경우 아무점이나 반환한다.
bool segmentIntersection(Vector2 a, Vector2 b, Vector2 c, Vector2 d, ref Vector2 p){
//두 직선이 평행인 경우를 우선 예외로 처리한다.
if(!lineIntersection(a, b, c, d, ref p))
return paralleSegments(a, b, c, d, ref p);
//p가 두 선분에 포함되어 있는 경우에만 참을 반환한다.
return inBoundingRectangle(p, a, b) && inBoundingRectangle(p, c, d);
}
댓글남기기