점이 포함 된 보로 노이 다이어그램에서 다각형을 효율적으로 찾습니다.

Question

Voronoi diagram에 이미지를 투영합니다. 이미지의 검은 색이 아닌 각 픽셀에 대해 다이어그램에서 해당 다각형을 찾고 색을 지정합니다. (The site, to get an idea what I mean.) 수 백 개의 다각형을 사용하면 무차별 대입이 가능합니다. 수천 가지가 있지만 그렇지 않습니다.

질문 : 포인트가 포함 된 폴리곤을 효율적으로 검색하려면 어떻게해야합니까? 폴리곤 분포 또는 크기에 대한 가정없이 일반적인 경우에 관심이 있습니다.

두 기존 답변 (내가 발견) 관련 :

Finding out if a point is inside a voronoi cell 그것은 우아 보로 노이 다각형이 볼록 있다는 사실을 활용합니다. 따라서 가운데가 가장 가까운 다각형도 포함 폴리곤이어야합니다. 불행히도 최소값을 결정하기 위해 여전히 모든 다각형이 검색됩니다. 그것은 규모가 조정되지 않는 것입니다.

Finding the polygon in a 2D mesh which contains a point 2d 간격 트리를 언급합니다. (이 경우 slides on the topic에 따르면 세그먼트 트리 여야합니다.) 그러나 보로 노이 다이어그램의 한 가지 속성은 세그먼트 트리가 이러한 가정을하지는 않지만 다각형이 겹치지 않는 것입니다. 따라서 실제로 이러한 나무가 최상의 옵션 (?)이라면,이 가정을 포함하는 접근법이 더 효율적으로 사용할 수 있습니까?

D3을 사용하여 클라이언트 측 JavaScript로 구현하므로 알고리즘, 라이브러리 또는 모델링 변경에 관심이 있습니다. 예를 들어 MySQL 또는 MongoDB과 같은 공간 데이터베이스가 도움이되지 않습니다.

---

내가 지금까지 시도한 것 : 내가 할 수있는 가정에 의존하는 충분히 효율적인 색인을 만들었습니다. 아래를 참조하십시오.

내 구체적인 경우에 대한 해결책은 기본적으로 다각형의 중심점 해시입니다. 다이어그램은 균일 한 크기의 격자로 분할

1. :

   인덱스 구축.

2. 각 다각형은 중심점으로 셀에 지정됩니다.

주어진 지점을 포함하는 다각형을 검색 할 때 :

1. 가 포인트의 셀을 결정한다.
2. 이 셀의 모든 다각형이 테스트됩니다.
3. 일치하는 것이 없으면 다각형이 발견 될 때까지 주변 셀을 너비 우선 검색합니다. 폴리곤이 균일하게 분포되어
   1. : 나는 몇 가지 가정을하기 때문에

   이, 작동합니다. 즉 균일 한 격자가 좋습니다. 균일 한 격자는 좌표를 변환하여 점에 대한 셀을 결정할 수있게합니다.

4. 다각형은 볼록합니다. 이것은 중심점이 실제로 해당 영역의 대부분에 있음을 의미합니다.
5. 다각형의 크기는 대체로 같습니다. 평균 폴리곤 크기에 가까운 셀 크기를 선택하면 직접 셀 또는 인접 셀 중 하나가 원하는 다각형과 연결될 가능성이 높습니다.
6. 기본적으로 항상 그 점을 포함하는 다각형이 있습니다. (즉, 모든 셀을 검색 할 때 시간이 낭비됩니다.)

정확하게 사용 사례로 작동하지만 일부 제한을 완화하고 싶습니다. 이 질문은 가능한 경우 가정 1과 3을 버리는 것에 관한 것입니다. (2와 4는 Voronoi 다이어그램을위한 것입니다.)

Answer 1

만약 이것이 순수하게 기하학적 인 문제가 아니라면, 나는 lookup 비트 맵으로 갈 것입니다. 색상의 정수 ID를 사용하여 모든 폴리곤을 2 차 비트 맵 (캔버스)에 페인팅하면됩니다. poly의 id를 찾으려면 해당 위치의 픽셀 색상을 확인하면됩니다. 한 위치 - 한 페치. 초고속이지만 기하학적으로 완벽하지 않아야합니다. 조회 비트 맵의 ​​크기를 조정하여 정확도를 높일 수 있습니다.