이 기사의 내용은 주로 나와 같은 초보자를위한 매우 기본이므로 모든 알고리즘 황제에게 빠른 살펴 보도록 요청하십시오.
인용하다
ABCD가 종말점 인 선 세그먼트 1 (a, b) 및 라인 세그먼트 2 (c, d)는 라인 세그먼트의 교차점 P를 찾는 것으로 알려져있다. (평행 또는 공동체는 분리 된 것으로 간주됩니다)
알고리즘 1 : 두 줄 세그먼트가있는 직선의 교차점을 찾은 다음 교차점이 두 줄 세그먼트에 있는지 여부를 결정하십시오.
직선의 교차점을 찾을 때, 우리는 직선의 AX+BY+C = 0 의 일반적인 방정식을 통해 찾을 수 있습니다 (방정식의 ABC는 위에서 언급 한 끝점이 아니라 계수입니다. 또한 점 사선 방정식과 비스듬한 절편 방정식도 사용할 수 있습니다).
그런 다음 교차점과 라인 세그먼트의 종말점 사이의 위치 관계를 기반으로 교차점이 라인 세그먼트에 있는지 여부를 결정할 수 있습니다.
공식은 다음과 같습니다.
<code> 함수 segmentsintr (a, b, c, d) { /** 1 선형 방정식 시스템을 해결하고 선 세그먼트의 교차점을 찾습니다. **/ // 분모가 0 인 경우 평행하거나 콜린트이며 var denominator = (by -ay)*(dx -cx) - (ax -bx)*(cy -dy); if (denominator == 0) {return false; } // 라인 세그먼트가 위치한 직선의 교차 좌표 (x, y) var x = ((bx -ax) * (dx -cx) * (cy -ay) + (by -ay) * (dx -cx) * ax- (dy -cy) * (bx - ax) * cx) / delominator; var y = - ((by -ay) * (dy -cy) * (cx- ax) + (bx- ax) * (dy- cy) * ay- (dx -cx) * (by -ay) * cy) / denominator; / ** 2 교차점이 두 세그먼트에 있는지 여부를 결정합니다 **/ if (// 교차로가 선 세그먼트 1 (x -ax) * (x -bx) <= 0 && (y -ay) * (y -by) <= 0 //에 있습니다. // 교차로로 돌아 가기 P return {x : x, y : y}} // 그렇지 않으면, disjoint return false} </code>알고리즘은 먼저 명확하고 이해하기 쉬운 아이디어를 가지고 있지만 성능은 높지 않습니다. 교차로가 유효한지 여부 (온라인 세그먼트에서)가 불확실하기 전에 교차로를 계산하기 때문에 많은 시간이 걸립니다.
교차점이 마침내 유효하지 않은 것으로 판명되면 이전 계산이 헛된 것입니다. 또한 전체 계산 프로세스도 매우 복잡합니다.
그렇다면 효과적인 교차점이 먼저 있는지 여부를 말한 다음 계산할 수있는 방법이 있습니까?
분명히 대답은 예입니다. 따라서 일부 알고리즘이 발견됩니다.
알고리즘 2 : 각 라인 세그먼트의 두 종점이 다른 라인 세그먼트의 양쪽에 있는지 여부를 결정하십시오. 그런 다음 두 라인 세그먼트가있는 직선의 교차점을 찾으십시오. 그렇지 않으면 교차하지 않습니다.
첫 번째 단계는 두 점이 특정 라인 세그먼트의 양쪽에 있는지 여부를 결정하는 것입니다. 프로젝션 방법은 일반적으로 사용할 수 있습니다.
라인 세그먼트의 일반 벡터를 찾은 다음 지점을 일반 선에 투사하고 마침내 투사 된 위치를 기반으로 포인트와 라인 세그먼트 간의 관계를 판단하십시오.
아래 그림을 참조하십시오
지점 A 및 점 B의 정상 선 세그먼트 CD에 대한 투사는 그림에 나와 있습니다. 이 시점에서도 정상 선에서 라인 세그먼트 CD를 투사해야합니다 (점 C 또는 지점 D 중 하나를 선택).
주로 참조에 사용됩니다.
그림에서, 점 A와 점 B의 투영은 점 C 투영의 양쪽에 투영되며, 라인 세그먼트 AB의 라인 세그먼트 Cd의 양면을 나타낸다.
마찬가지로, CD가 라인 세그먼트 AB의 양쪽에 있는지 여부를 다시 판단하십시오.
정상, 투영 및 기타 사항을 찾는 것은 매우 복잡한 소리를냅니다. 그러나 실제로 그것은 실제로 나에게 상당히 복잡합니다. 몇 달 전에 기하학적 지식에 대해 많이 알지 못했습니다 (공부할 때 기하학에 대한 모든 지식을 잊어 버렸습니다 : '()'.
다행히도 학습과 구현은 복잡하지 않으며 따라야 할 공식이 있습니다.
라인 세그먼트 AB의 정상을 찾으십시오.
var nx = by -ay, ny = ax -bx; var normalline = {x : nx, y : ny}; 참고 : normalLine.x 및 normalLine.y 의 기하학적 의미는 좌표가 아니라 정상 선의 방향을 나타냅니다.
일반 선에서 점 C의 투영 위치를 찾으십시오.
var dist = normalline.x*cx + normalline.y*cy;
참고 : 여기서 "투사 위치"는 스칼라이며, 이는 투영 지점의 좌표가 아니라 정상의 원점까지의 거리를 나타냅니다.
일반적 으로이 거리를 아는 것으로 충분합니다.
그림에서 점 A (dista), 지점 B (distb) 및 점 C (distc)의 투영을 계산 한 후, 각 크기에 따라 상대 위치를 쉽게 판단 할 수 있습니다.
dista == distb == distc 일 때, 두 세그먼트는 공동체입니다
dista == distb! = distc 일 때, 두 줄 세그먼트는 평행합니다
Dista와 Distb가 Distc의 동일한쪽에있을 때, 두 줄 세그먼트는 교차하지 않습니다.
Dista와 Distb가 Distc의 반대쪽에있을 때, 2 라인 세그먼트가 교차하는지 여부 C와 선 세그먼트 AB 사이의 관계가 다시 판단되어야합니다.
이전 단계는 "라인 세그먼트가 교차하는지 판단하는 것"만 구현합니다. 결과가 사실이되면 교차점을 더 찾아야합니다.
나중에 교차점을 찾는 과정에 대해 이야기합시다. 먼저이 알고리즘의 전체 구현을 살펴 보겠습니다.
함수 세그먼트 intr (a, b, c, d) {// normal n1 var nx1 = (by -ay), ny1 = (ax -bx); // normal n2 var nx2 = (dy -cy), ny2 = (cx -dx); // 결과가 0 인 경우 두 개의 정상이 곱하면 선 세그먼트 AB와 세그먼트 CD가 평행 또는 공동체이며 var denominator = nx1*ny2 -ny1*nx2; if (denominator == 0) {return false; } // 정상 N2 var distc_n2 = nx2 * cx + ny2 * cy에서의 투영; var dista_n2 = nx2 * ax + ny2 * ay-distc_n2; var distb_n2 = nx2 * bx + ny2 * by-distc_n2; // 지점 A와 점 B의 투영은 지점 C 프로젝션의 동일한 측면에 있습니다 (줄 세그먼트의 경우에,이 예제는 분리 된 것으로 취급됨); if (dista_n2*distb_n2> = 0) {return false; } // // 지점 C 점 D와 라인 세그먼트 사이의 관계를 판단하면 원리는 정상 N1 var dista_n1 = nx1 * ax + ny1 * ay; var distc_n1 = nx1 * cx + ny1 * cy-dista_n1; var distd_n1 = nx1 * dx + ny1 * dy-dista_n1; if (distc_n1*distd_n1> = 0) {return false; } // 교차 좌표를 계산합니다. var fraction = dista_n2 / denominator; var dx = fraction * ny1, dy = -fraction * nx1; 반환 {x : ax + dx, y : ay + dy}; }교차점 지점의 좌표를 찾는 데 사용되는 방법은 조금 이상하게 보이며 눈에 띄지 않는 것처럼 느껴집니다.
실제로, 그것은 많은 계산 항이 미리 계산되었다는 점을 제외하고 알고리즘 1의 알고리즘과 유사합니다.
다시 말해, 2 마일의 교차점 지점의 좌표를 찾는 알고리즘의 일부는 실제로 직선의 선형 방정식으로 만들어집니다.
이제 알고리즘 1과 알고리즘 2를 간단하고 거칠고 비과학적인 방식으로 비교해 봅시다.
1. 최선의 경우 두 알고리즘의 복잡성은 동일합니다.
2. 최악의 경우 알고리즘 1과 알고리즘 2의 계산량은 거의 동일합니다.
3. 그러나 알고리즘 2는 더 많은 "초기 조건"을 제공하므로 평균적으로 알고리즘 2가 더 나을 것입니다.
실제 테스트 후 실제 상황이 실제로 발생합니다.
이전의 두 가지 알고리즘은 기본적으로 일반적이며 대부분의 상황에 대처할 수 있습니다. 그러나 실제로 더 나은 알고리즘이 있습니다.
이것은 내가 최근에 배운 것입니다 (나는 지금 그것을 배웠고 지금 그것을 팔았습니다.
알고리즘 3 : 각 라인 세그먼트의 두 종점이 다른 라인 세그먼트의 양쪽에 있는지 여부를 결정하십시오. 두 줄 세그먼트가있는 직선의 교차점을 찾으면 그렇지 않으면 교차하지 않습니다.
(Huh? 왜 알고리즘 2와 같은 느낌이 있습니까? 실제로 동일하다는 것을 의심하지 마십시오 ...)
소위 알고리즘 3은 실제로 알고리즘 2의 개선 일뿐입니다. 주요 개선 사항은 다음과 같습니다.
점과 선 세그먼트 사이의 위치 관계는 정상적인 투영에 의해 판단되는 것이 아니라 점과 선 세그먼트로 구성된 삼각형의 영역에 의해 판단됩니다.
먼저 삼각형 영역 공식을 검토합시다 : 삼각형 영역의 3 점 a (x, y) b (x, y) c (x, y)는 다음과 같습니다.
<code> var triardrea = ((Ax -Cx) * (by -cy) - (ay- cy) * (bx -cx)) /2; </코드>
평행 사변형의 면적 (2 개의 벡터가 인접한면이기 때문에 2 개의 벡터 포킹 == 두 벡터로 구성되기 때문에 상기 공식은 이해하기 어렵지 않습니다.
또한 벡터에는 방향이 있으므로이 지역에는 방향이 있습니다. 일반적으로 우리는 반 시계 반대 방향을 양수와 시계 방향으로 마이너스로 사용합니다.
개선 된 알고리즘의 핵심 사항은 다음과 같습니다.
"라인 세그먼트 AB 및 점 C"에 의해 형성된 삼각형 영역의 양 및 음성 징후가 "선 세그먼트 AB 및 지점 D"에 의해 형성된 삼각형 영역과 다르면,
그런 다음 점 C와 점 D는 라인 세그먼트 AB의 양쪽에 위치합니다.
아래 그림과 같이 :
그림의 점선으로 표시된 삼각형은 다른 권선 방향 (세면의 정의 순서)을 가지므로 영역의 양수 및 부정적인 기호는 다릅니다.
먼저 코드를 살펴 보겠습니다.
우리는 기호 만 판단하면되므로 앞의 삼각형 영역 공식에서 다음을 2로 나눌 필요가 없습니다.
함수 segmentsintr (a, b, c, d) {// 삼각형 ABC var area_abc = (ax -cx) * (by -cy) - (ay -cy) * (bx -cx)의 2 배. // 삼각형 ABD VAR AREA_ABD = (ax -dx) * (by -dy) - (ay -dy) * (bx -dx); // 영역 기호가 동일하면 두 점이 같은쪽에 교차하지 않습니다 (선 세그먼트의 지점의 경우이 예제는 분리됩니다). if (area_abc*area_abd> = 0) {return false; } // 삼각형 cda var area_cda의 영역의 2 배 = (cx- ax) * (dy -ay) - (cy -ay) * (dx - ax); // 삼각형 CDB 영역의 2 배나 참고 : 여기에는 작은 최적화가 있습니다. 공식으로 영역을 계산할 필요는 없지만 세 가지 알려진 영역을 추가하고 빼서 도출됩니다. var area_cdb = area_cda + area_abc -area_abd; if (area_cda * area_cdb> = 0) {return false; } // 교차 좌표를 계산합니다. var dx = t*(bx- ax), dy = t*(by -ay); 반환 {x : ax + dx, y : ay + dy}; }마지막으로, 교차 좌표를 계산하는 부분은 알고리즘과 동일합니다.
알고리즘 2를 기반으로 알고리즘 3은 계산 단계를 크게 단순화하고 코드가 더 간소화됩니다. 세 가지 알고리즘 중에서 가장 좋다고 말할 수 있습니다. 실제 테스트 결과에 대해서도 마찬가지입니다.
물론, 우리는 JavaScript에서 세 가지 알고리즘의 시간 복잡성은 실제로 일반 계산 (특히 V8 엔진)과 비슷합니다.
테스트 사례에서는 세 가지 알고리즘 사이의 간격을 넓히기 위해 비정상적인 백만 레벨 라인 세그먼트 교차 테스트를 수행했습니다.
요약
그러나 우수성과 학습을 위해 노력하는 태도로 더 나은 알고리즘을 추구하는 것은 항상 긍정적 인 의미를 가지고 있습니다. 위의 것은 JS를 사용하여 라인 세그먼트 교차점을 달성하는 여러 알고리즘입니다. 내용은 그다지 심오하지 않습니다. 모든 사람이 JS를 배우는 것이 도움이되기를 바랍니다.