바운드 영역 내에서 점 집합과의 총 거리를 최대화하는 점 찾기

Question

점 집합이 p 인 경우 b 범위 내에서 가능한 한 멀리있는 p 영역을 경계하는 점을 찾고 싶습니다. p 내의 모든 지점에서

이것은 이웃을 피하는 최선의 방법이 아닌 경우, Craig Reynolds' Boids에 따른 몰목 시뮬레이션에서 이웃 회피를 구현하는 것과 관련이 있습니다.

편집 : p 주위에 경계 상자 내에서 유지하면서 은 즉, 내가, 지금까지의 다른 지점에서 p 가능한 한있는 임의의 점을 발견하고 싶습니다.

바운딩 상자로 솔루션은 위와 아래 지점 사이에있는 y 좌표와 왼쪽 지점과 오른쪽 지점 사이에있는 x 좌표가 있어야한다는 의미입니다.

더 추상적으로 질문을 드리 자면, M 단위의 가장 가까운 이웃을 유지하려는 에이전트의 대상을 찾는 방법으로이 알고리즘을보고 있는데, 그 중 m 단위보다 가까이 있지는 않습니다. 이 알고리즘에 의해 반환 된 솔루션은 가장 가까운 이웃 사이의 거리가 가장 큰 점을 반환해야합니다.

이것은 2D 평면에 있습니다.

Answer 1

(다른) 에이전트에 대한 보로 노이 다이어그램의 교차점 중 하나에 솔루션이 있어야하는 것처럼 들립니다. 따라서 알고리즘 적 해결책은 보로 노이 다이어그램을 만들고, 교차점을 반복하고, 가장 가까운 거리까지 가장 가까운 거리를 선택하는 것입니다.

Answer 2

필자는 가장 먼 지점이 상자 경계 또는 두 개의 가장 가까운 지점 사이의 같은 거리에 있어야한다고 생각합니다. 그렇지 않은 경우에는 두 지점을 더 가깝게 만들기 위해 약간 이동해야합니다. 이것은 다이어그램의 한 줄에 표시됩니다. 그 선을 따르는 방향 중 하나는 두 점에서 더 멀리 이동하므로 한 점에서 다른 선이 그 선에 결합 할 때까지 이동할 수 있습니다. 그러므로 나는 그것이 경계 나 또는 http://en.wikipedia.org/wiki/Voronoi_diagram의 교차점 중 하나에있을 것을 기대한다. Voronoi 다이어그램의 선이 경계와 교차하는 경계 모서리와 Voronoi 다이어그램의 교차점을 확인하여 가장 먼 점을 찾을 수 있습니다. 이 방법으로하지 않더라도 Voronoi 다이어그램은 가장 가까운 이웃을 다른 방법으로 찾는 방법으로 유용 할 수 있습니다. 다양한 지점과 경계가 작동 할 수 있습니다.