정점의 가장자리 (다각형)를 찾는 최고의 알고리즘

Question

나는 많은 정점 배열이 있고, 그 중 일부는 가장자리이며, 일부는 중복 (모양 내부)이며 제거하고 싶습니다.

내가 생각할 수있는 가장 간단한 알고리즘은 다른 사람들이 형성된 모양에 부딪 치면 하나씩 확인하는 것입니다. 그러나 매우 느린 알고리즘이어야합니다.

나는 가장자리에서 하나를 선택하는 것에 대해 생각하고 (예마다 원점에서 가장 먼 곳)이 시작에서 가장 긴 경로를 계산합니다 ... 가장자리 경로를 가져와야합니까?

어떠한 제안?

Answer 1

다면체 알고리즘을 사용한 트릭은 입력 및 원하는 출력에 맞는 트릭을 선택하는 것입니다. 다면체를 나타내는 방법이 둘 이상이고 표현 사이를 변환하는 데 비용이 많이들 수 있기 때문입니다. 이 경우, 당신은 포인트로 시작하고 정점으로 끝나기를 원합니다. 그레이엄 스캔 알고리즘의 정점을 계산하기위한 알고리즘 볼록한 선체 트릭을 수행해야하지만 2D 케이스를 지나서 확장하는 데 약간의 노력이 필요할 수 있습니다. O (O)n 로그 n) 입력 정점 수에서.

Answer 2

다각형이 무엇인지 알 수있는 가장 좋은 알고리즘이 무엇인지 모르겠지만, 당신이 찾고있는 다각형을 "볼록한 선체"라고합니다.

이를 검색하면 일치하는 알고리즘을 찾아야합니다.

Answer 3

볼록한 선체 계산 기하학의 더 연구 된 문제 중 하나입니다. Graham 스캔은 더 간단한 것 중 하나입니다 볼록한 선체 알고리즘, 그러나 확실히 유일한 사람은 아닙니다. 선물 랩핑 알고리즘, Jarvis 'March라고도 불리는 것은 내가 아는 가장 간단한 것입니다. Stony Brook 알고리즘 저장소 C 및 C ++에 볼록한 선체 알고리즘의 여러 구현이 있습니다. 행동의 기하학 주로 볼록한 선체의 응용 프로그램을 보여줍니다. 여기에 모음이 있습니다 저 차원 그리고 임의의 차원 볼록한 선체 계산 프로그램.