지도상의 점을 다각형으로 변환

Question

지도 상에 수천 점이 있습니다. 포인트는 사람이 움직일 때마다 주기적으로 측정되는 값이므로 각 포인트의 위치는 윈도우 내에서 임의적이지만 데이터를 보면 촬영 된 경로를 볼 수 있습니다. 데이터를 빠르게 렌더링하기 위해 클러스터 된 점을 다각형으로 변환하고 대신 그려 봅니다. 줌 레벨에 맞는 폴리곤 디테일을 선택하여 손실 된 세부 사항을 처리 할 수 ​​있습니다.

그런 일을하기위한 빠른 알고리즘이 있습니까?

Answer 1

다각형을 나타 내기 원하십니까? 이동 된 경로의 영역 (즉, 경계 만)을 덮는 닫힌 영역에서와 같이 다각형을 의미합니까? 또는 방문한 모든 지점 사이의 정확한 선분 세그먼트 다각형? 후자는 포인트보다 많은 그림을 그리는 것이 더 빠를 것입니다. 포인트를 가진만큼 많은 코너를 가진 다각형 일 것입니다.

사람이 도시의 일부를 다루는 배달 드라이버와 같은 지역을 돌아 다니다 보면 그 지점의 볼록한 선체로 "덮힌 지역"을 근사시킬 수 있습니다. 데이터 세트에 N 점이 있으면 닫힌 볼록 다각형이며 3과 N 코너 사이에 있습니다.

정의

http://mathworld.wolfram.com/ConvexHull.html

알고리즘

http://en.wikipedia.org/wiki/Convex_hull_algorithms

당신이 경로보다는 약간 덮여 지역의 근사치를 확인하려면, 당신은 항상 원유를 만들 수 LOD 알고리즘은 (말하자면) 매 7 포인트마다, 매 5 포인트마다, 매 3 포인트마다 그리기 사용자가 더 확대 할 때 nts. 보다 정교한 LOD 알고리즘은 점 p0과 점 p1에서 시작하여 점을 통과하는 방향을 사용하고 점선에서 점 p2까지의 거리를 볼 수 있습니다. p2가 라인에 충분히 가깝다면 건너 뛴다. 그리고 p3가 조사된다. 여행 방향이 충분히 크게 변경된 경우 마지막 두 점을 현재 코스로 표시하고 반복합니다. 허용되는 방향 변경은 LOD 매개 변수로 점 수를 결정합니다. 이 알고리즘은 경로의 "중요"점 (방향이 변경되는 지점)을 근사값으로 계산합니다.

Answer 2

정확한 경로를 알고있는 것은 불가능하다고 생각하지만 특정 지점에 가장 가까운 지점이 경로의 다음 지점이라고 가정하는 것은 상당히 합리적입니다. 어떤 크기의 폴리곤을 다루고 있는지 잘 모르겠지만 궁극적으로지도상의 어떤 점이 현재 점에 가장 가까운 점인지 그리고 그 점이 다각형의 다음 점이 될 것이라고 계산할 것입니다. 다각형이 매우 큰 경우 정확성을 보장하기 위해 점 사이의 큰 원형 거리를 계산해야합니다.