0
/여러 라인 세그먼트로 정의 된 한 쌍의 선이 교차하는지 확인해야합니다. 예를 들어 (0,0), (1,2), (3,1)에 의해 정의 된 선과 (0,2), (2,-1), (4,1)으로 정의 된 선이 교차하는지 확인해야합니다.세그먼트 화 된 선의 교차점 결정
교차가 어디인지를 결정할 필요는 없지만 매우 많은 수의 모서리를 가질 수 있으므로 효율적인 방법이 필요합니다. 두 세그먼트가 교차하는지 확인하기 위해 아래 코드를 사용하고 있지만 더 긴 길이의 라인에서는 비효율적입니다. 또한 선은 그래프의 가장자리이며 알려진 최대 길이로 제한됩니다.
static bool IsOnSegment(float xi, float yi, float xj, float yj,
float xk, float yk) {
return (xi <= xk || xj <= xk) && (xk <= xi || xk <= xj) &&
(yi <= yk || yj <= yk) && (yk <= yi || yk <= yj);
}
static char ComputeDirection(float xi, float yi, float xj, float yj,
float xk, float yk) {
float a = (xk - xi) * (yj - yi);
float b = (xj - xi) * (yk - yi);
return a < b ? -1 : a > b ? 1 : 0;
}
// Do line segments (x1, y1)--(x2, y2) and (x3, y3)--(x4, y4) intersect?/
bool DoLineSegmentsIntersect(float x1, float y1, float x2, float y2,
float x3, float y3, float x4, float y4) {
char d1 = ComputeDirection(x3, y3, x4, y4, x1, y1);
char d2 = ComputeDirection(x3, y3, x4, y4, x2, y2);
char d3 = ComputeDirection(x1, y1, x2, y2, x3, y3);
char d4 = ComputeDirection(x1, y1, x2, y2, x4, y4);
return (((d1 > 0 && d2 < 0) || (d1 < 0 && d2 > 0)) &&
((d3 > 0 && d4 < 0) || (d3 < 0 && d4 > 0))) ||
(d1 == 0 && IsOnSegment(x3, y3, x4, y4, x1, y1)) ||
(d2 == 0 && IsOnSegment(x3, y3, x4, y4, x2, y2)) ||
(d3 == 0 && IsOnSegment(x1, y1, x2, y2, x3, y3)) ||
(d4 == 0 && IsOnSegment(x1, y1, x2, y2, x4, y4));
}
가능한 중복 어떻게 두 선분이 교차하는지 감지합니까?] (http://stackoverflow.com/questions/563198/how-do-you-detect-where-two-line-segments-intersect) – hivert
그 질문은 두 개의 단일 세그먼트가 교차 하는지를 결정하는 함수를주었습니다. 그러나 세그먼트의 경로를 고려하고 다른 세그먼트와 교차점을 찾아야합니다 통로. –
* (0,0), (1.2) 및 (3,1) *로 정의 된 선; 이것은 2 개의 선분 또는 삼각형의 합집합입니까? –