라인 경로의 교차점 찾기

Question

두 개의 끝점을 공유하는 베 지어 곡선이 있습니다. 이 곡선들 각각은 도로의 가장자리와 비슷하게 좌우 양쪽에 "확장"을 가지고 있습니다. 확장은 베 지어 곡선을 근사하는 선분으로 구성됩니다.

베 지어 곡선의 공유 끝점에 대한 이러한 경로의 가장 가까운 교차점을 찾고 싶습니다.

Here is a diagram I've drawn of the problem

각 라인 경로는 각각의 라인을 교차와 가장 가까운 교차점이 실시간으로 실행해야 주어진 매우 느려질 수 있습니다 유지, 100 개 이상의 정점을 가지고있다.

나는 교차점을 확인하기 전에 라인에서 경계 구 교차 테스트를 실행하여 약간 속도가 빨라졌지만 여전히 빠르지는 않습니다. 내 다음 접근 방식은 일종의 quadtree 구조를 사용하는 것입니다.

나는 Bentley-Ottmann algorithm을 찾았지만, 내가 필요로하지 않는 한 세트의 라인에서 모든 교차점을 찾는 것을 다루는 것으로 보인다. 또한 베 지어 곡선 교차 알고리즘을 찾았지만 이미 가지고있는 선분으로 세분화해야합니다.

이 문제에 유용한 알고리즘이나 최적화 방법에 대한 아이디어가 있습니까?

Answer 1

확장 폭 Aw 및 Bw를 갖는 두 개의 곡선 A 및 B가 주어지면, 공유 노드 N으로부터 A를 따라 거리 Bw 인 점 A '를 찾는다. 마찬가지로 공유 노드 N으로부터 B를 따라 거리 Aw 인 점 B'를 찾는다. 이제 점 N, A '및 B'가 주어지면, 다른 세 개의 노드와 평행 사변형을 형성하는 네 번째 점 N '을 찾으십시오. 이 점 N '은 교차점입니다.