파티션 2D는 각각 K 개의 이웃 점을 갖는 N 개의 영역을 가리 킵니다

Question

2D 공간에서 점들의 집합을 가지고 있다면, K 개의 이웃 점을 포함하는 N 개의 "영역"으로 그 점들을 나눌 수있는 알고리즘이 있습니까?

예를 들어,이 20 개의 점이 5 개의 점마다 4 개의 그룹으로 묶여 있다고 가정합니다. 만족스러운 해결책은 다음과 같습니다

동기 부여 : 나는 visualization that loads lots of images into the browser을 최적화하기 위해 노력하고있어. 페이지로드시 매우 낮은 해상도의 이미지를로드하고 사용자가 해당 지역을 확대 할 때 이미지의 해상도를 높일 계획입니다. 물론 공간을 양자화해야합니다. 사용자가 위 샘플의 중간으로 스크롤하면 4 개 그룹 각각에 대해 고해상도 이미지를 가져와야합니다. 알고리즘은 다음과 같이 할 수 있습니다

console.log('stackoverflow wants code for posts with codepen links') 

Answer 1

:

계산 일정한 정도의 스패닝 트리 : (이론 컴퓨터 과학 사이트에서) this solution이 짧고 간단 마지막 단계에 대한

- get a triangulation of the points (for example: Delaunay Triangulation): D 
- get a planar graph from D: G 
- Then partition G into connected subgraphs with equal size k 

T를 그래프의 뿌리, 뿌리, 그리고 지금 탐욕스럽게 대략 크기 r의 하위 트리를 찾아, 추출하고 반복합니다. 당연히, 일정한 스패닝 트리가 없다면, 위의 스타 예제는이 알고리즘이 실패 할 수 있음을 보여줍니다.