효율적인 알고리즘을 찾는 가장 가까운 라인 (수직 거리로 정의)을 임의의 지점으로 신속하게 찾으십시오.

Question

i는 공지 된 시작점과 끝점으로 2D에 큰 선 집합이 있으며, 그 모서리의 가장 가까운 (수직 거리에 의해 정의 된) (또는 시작 및 끝점을 지나서 가장자리의 확장)을 찾고 싶습니다.) 임의의 지점에.

지금까지 수행 한 가장 좋은 것은 각 라인을 따라 샘플 포인트 세트를 생성하고 KD- 트리를 사용하여 점에서 가장 가까운 이웃 문제를 해결하는 것입니다. 즉, 쿼리 지점으로 가장 가까운 라인 샘플 지점을 찾으십시오.그러나 이것은 정확하지 않고 긴 줄에 많은 수의 샘플이 필요합니다.

이걸 보았습니다. 가장 가까운 가장자리에 대한 알고리즘점에 대한 감지 (모든 방향으로)

스윕 방법과 적은 수의 유한 길이에 의존합니다.

Answer 1

모든 라인은 각 다각형 영역 이 유한 수의 라인 세그먼트 또는 광선에 의해 바인딩되는 평면 세분화 을 정의합니다. 처음에는 쿼리 지점을 포함한 (아마도 무한한) 지역을 찾아야합니다. 그런 다음이 시점에서 최소 거리의 경계선을 선택할 수 있습니다.

포인트 위치 문제점 로그 복잡성이있는 시간. 일부 계층 적 데이터 구조는 일반적으로 모든 쿼리 지점에 대해 이송 될 수 있으며 $ O (log (n)) $에 의해 트래버스 경로의 길이가 제한되는 것으로 판명되었습니다. , 여기서 $ n $ 은 영역의 수입니다. @pseudyonym은 이진 공간 파티셔닝 (BSP) 를 사용할 수도 있습니다. BSP TREE (BSP TREE) 또한 쿼리 지점을 포함하는 영역을 효율적으로 찾을 수있는 계층 적 데이터 구조 (이진 트리)입니다. 이 BSP 접근법에 대해 문제가 잘 어울리는 것처럼 보입니다.

죄송합니다. $ o (n) $ 경계 세그먼트 / 광선으로 지역을 얻을 수 있습니다. 여기서 $ n $ 은 줄 수입니다. 이 어려움을 극복하기 위해 각 지역을 voronoi 다이어그램 일반화 된 voronoi 다이어그램 및 광선. 이러한 세련된 영역의 총 수가 $ o (n ^ 2) $ 에 의해 제한 될 것이라는 것을 쉽게 알 수 있습니다. 이는 여전히 가장 가까운 라인에 대한 로그 복잡성을 제공합니다 검색. 그러나 평균적으로 많은 경계 세그먼트 / 광선이있는 이러한 영역은 모든 지역의 작은 부분을 구성 할 수 있습니다. 따라서 평균적으로 영역 경계를 반복하여 가장 가까운 경계 세그먼트 / 레이를 신속하게 선택할 수 있습니다.

---

기하학적 구조의 일반적인 속성에 대해 더 많이 알고 싶다면 이 위키 페이지.

Answer 2

귀하의 목표를 오해했을 수 있습니다. 가장자리가 2 명의 특정 지점으로 정의 되더라도 모서리가 계속해서 계속 진행됩니까?나는 거리가 수직 거리에 의해 정의된다고 말하기 때문에 그렇게한다.이 경우 어떻게 이것에 대해서도 -

1. 각 라인 세그먼트에 대해 각도를 계산하십시오.
2. 라인 세그먼트에 수직 인 각도로 임의의 점을 통과하는 가상의 라인을 그립니다.
3. 라인 세그먼트와 새로운 상상의 라인 간의 교차점을 찾아 해당 지점과 임의의 지점 사이의 거리를 찾으십시오.가장 낮은 거리를 유지하십시오.

라인이 무한히 길지 않으면 거리를 확인할 때 min (시작점까지의 거리, 거리에서 끝점까지 거리)