오목 폴리곤 정점을 반 시계 방향으로 정렬

Question

오목 폴리곤 경계에있는 점 집합이 있습니다. 이 점들을 꼭짓점으로 갖는 하나의 비 교차 다각형을 찾고 싶습니다. 즉, 오목한 다각형의 정점을 ccw (또는 cw) 방식으로 정렬하고 싶습니다.

다각형이 ccw 또는 cw 방식으로 정렬되었는지 평가하는 방법을 살펴 보았습니다 (교차 곱 계산 및 합계). 그것은 정확하게 내 문제가 아닙니다 : 나는 임의의 순서로 꼭지점을 가지며, 나는 그것들을 폴리곤의 외각에 cw 또는 ccw 갖도록 명령하고 싶습니다.

처음 정점 시퀀스를 생각하고 연속적으로 교차점을 확인했습니다. 초기 점 시퀀스가 ​​[x1, y1; x2, y2; x3, y3; ...]이고 두 번째와 세 번째 점이 교차하면 시퀀스 [x1, y1; x2, y3; x3, y2; ...]

어떤 알고리즘을 생각해 볼 수 있습니까? 뒤에있는 개념은 무엇입니까? 참고 문헌에 힌트가 있습니까?

Regds

Answer 1

내가 문제를 이해하면 제대로, 당신은 그들이 몇 가지 가능성이 오목 다각형의 시계 방향 순서로 표시되도록 점 세트 입력을 주문하고 싶다. 이것은 다음과 같이 해결할 수 있습니다.

하자 P1과 P2는 가장 왼쪽과 가장 오른쪽 포인트합니다. 포인트의 낮은 볼록 선체 S를 찾으십시오. S는 p1, p2 및 p1p2 선 아래에있는 모든 볼록 선체 점을 포함합니다. 이제 나머지 점 (S가 아닌 점)을 x 좌표로 정렬하십시오. 이 정렬 된 순서는 S (낮은 볼록 선체 알고리즘에 의해 생성됨)의 순서와 함께 모든 정점의 원하는 시계 방향을 제공합니다.

Answer 2

다각형을 구성 할 때 정보가 있습니다. 다각형이 내가 생각한 오목한 다각형이 될 수있는 점 집합보다 잘 정의되지 않은 한 사용해야합니다.

예를 들어 정점을 모양 또는 이미지에서 가져온 경우 모양의 채워진 픽셀이 도움이 될 수 있습니다. 한 프로젝트에서 블롭의 경계에 점을 정렬해야하므로 블롭의 테두리 픽셀을 얻습니다 (여러 가지 방법으로 수행 할 수 있음). 그런 다음 순차적으로 배치하는 DFS 스타일 탐색을 사용합니다. 그런 다음 가장자리를 병합하고 분기점에서 의사 결정 알고리즘을 작성했습니다.