다각형 정점을 최소화합니다

Question

모양이 크게 바뀌지 않고 다각형의 정점 수를 줄이기위한 좋은 알고리즘은 무엇입니까?

입력 : 다각형, 예를 들어 마우스의 원시 입력이 너무 많은 포인트 목록으로 표시됩니다.

출력 : 원본과 비슷하게 보이는 Verticies가 훨씬 적은 다각형 : 예를 들어 충돌 감지를 위해 사용할 수있는 것 (반드시 볼록한 것은 아닙니다).

편집 : 이에 대한 솔루션은 그래프에서 가장 잘 맞는 다중 세그먼트 라인을 찾는 것과 유사합니다. 내 알고리즘 책에서 세그먼트로드 최소 제곱이라고합니다.

edit2 : Douglas Peucker 알고리즘은 내가 정말로 원하는 것입니다.

Answer 1

편집 : 오 봐, 다각형 단순화

충돌 감지를 언급했습니다. 당신은 정말로 간단하게 가서 그 주위에 경계 볼록한 선체를 계산할 수 있습니다.

오목한 지역을 걱정했다면 다각형의 중심을 가져 와서 시작할 지점을 선택하여 오목한 선체를 계산할 수 있습니다. 출발점에서 중심 주위에서 회전하여 유지하려는 각 정점을 찾아 경계 선체의 다음 정점으로 할당합니다. 알고리즘의 복잡성은 어떤 정점을 유지 해야하는지 결정하는 방법에 나올 것이지만, 이미 그것을 생각했을 것입니다. 중심에 대한 위치에 따라 모든 정점을 버킷에 버릴 수 있습니다. 양동이가 임의의 정점이 가득 찬 수보다 더 많은 양을 얻으면 분할 할 수 있습니다. 그런 다음 해당 버킷의 정점 평균을 경계 선체에 사용할 수있는 정점으로 가져갑니다. 또는 버킷을 잊어 버리고 중심을 돌아 다니면 마지막 지점에서 주어진 거리 이상의 점을 선택하십시오.

실제로, 당신은 아마 당신의 다각형의 모든 정점을 "포인트의 구름"으로 사용하고 그 주위의 오목한 선체를 계산할 수 있습니다. 알고리즘 링크를 찾을 것입니다. 이것에 대한 최악의 경우는 완전히 볼록한 다각형 일 것입니다.

또 다른 대안은 경계 사각형으로 시작하는 것입니다. 사각형의 각 정점에 대해 지점에서 다각형까지의 거리를 찾으십시오. 가장 먼 정점의 경우 두 개의 정점으로 나누고 일부로 옮기십시오. 정점이나 영역의 일부 비율이 충족 될 때까지 반복하십시오. 나는 이것의 세부 사항에 대해 조금 더 생각해야한다.

자체 상영 다각형의 경우에도 다각형이 실제로 비슷하게 보이는 경우에도 다른 접근법이 필요하지만 충돌 감지에 대해 요청한 이후로는 들리지 않습니다.

이것 게시하다 볼록한 선체 부분에 대한 세부 사항이 있습니다.

Answer 2

거기에는 많은 자료가 있습니다. "메쉬 감소", "메쉬 단순화", "메쉬 최적화"등과 같은 것들에 대한 Google 만