커다란 정점 배열이 있습니다. 그 중 일부는 가장자리이고, 일부는 중복되어 있으며, 그 중 일부를 제거하려고합니다.가장 좋은 알고리즘은 꼭지점의 가장자리 (다각형)를 찾습니다.
내가 생각할 수있는 가장 단순한 알고리즘은 다른 사람들이 만든 모양을 하나 하나 맞췄습니까? 그러나 매우 느린 알고리즘이어야합니다.
가장자리에서 하나를 선택하고 (예 : 원점에서 가장 멀리 떨어진 것)이 시작부터 가장 긴 경로를 계산하는 방법에 대해 생각해 보았습니다. 가장자리 경로를 가져야합니다.
의견이 있으십니까?
다면체 알고리즘의 트릭은 다면체를 표현하는 방법이 여러 가지 이상이고 표현 간의 변환이 비용이 많이 들기 때문에 입력과 원하는 출력에 맞는 것을 선택하는 것입니다. 이 경우 점으로 시작하여 꼭지점으로 끝내기를 원하므로 convex hull의 정점을 계산하는 알고리즘 Graham scan이 트릭을 수행해야합니다. 2 차원의 경우를 확장하는 데 다소 시간이 걸릴 수 있습니다. 입력 정점의 개수는 O (n log n)입니다.
그레이엄 스캔은 기본적으로 볼록한 선체를 제공합니다. – shoosh
그 폴리곤을 찾는 가장 좋은 알고리즘이 무엇인지 모르겠지만 찾고있는 폴리곤을 "볼록 헐"이라고합니다.
검색하면 일치하는 알고리즘을 찾아야합니다.
저는 볼록한 선체를 찾고 있다고 생각하지 않습니다. 왜냐하면 그는 자신의 꼭지점에 의해 형성된 다각형의 가장자리를 원하기 때문입니다. 볼록 선체는 그가 원할지도 모르는 것들조차 배제 할 것입니다. – sykora
"일부는 중복되어 (모양 안에 있음) 제거하고 싶습니다." – Timbo
나는 가장자리를 줄이려고하지 않고있다 ... 나는 그 중 일부가 중복 된 정점 컬렉션에서 다각형을 만드는 방법을 찾고있다. – fabiopedrosa
The Convex Hull은 전산 기하학의 더 많은 연구 문제 중 하나입니다. 그레이엄 스캔은 더 단순한 것 중 하나입니다 convex hull algorithms,하지만 단 한 가지는 아닙니다. Jarvis의 March이라고도하는 The Gift-wrapping Algorithm은 내가 아는 가장 간단한 것입니다. The Stony Brook algorithm repository에는 C 및 C++에서 볼록한 선체 알고리즘의 여러 구현이 있습니다. Geometry in Action은 주로 볼록한 선체의 적용을 보여줍니다. 다음은 low-dimensional과 arbitrary-dimensional 볼록 선체 계산 프로그램입니다.
모든 점을 포함하는 _a_ polygon을 원하십니까? 아니면 모든 점을 포함하는 _ 가장 작은 (면적 기준) 다각형을 원하십니까? – sykora
@sykora, 모든 점을 덮는 다각형. 그레이엄 스캔이 유효 해 보입니다. 감사. – fabiopedrosa