2 차원 불규칙한 모양을 일반적인 primatives로 줄이기

Question

알고리즘을 찾고 있는데 불규칙한 polgygons를 분석하고이를 프리미티브 (사각형, 사각형, 사다리꼴)로 줄이기 위해 & 테스트 방법을 시도했습니다. 재귀 적으로 모양을보고 일반적인 폴리곤에 가장 적합한 것을 결정하는 방법.

검은 형상이 불규칙한 다각형이고 청색 안에 맞는 원하는 regualar를 도시 화상을 취입

참조. 왼쪽 예제는 직선이어야하지만 가장 큰 모양에 맞을 수있는 직사각형을 찾는 경우이기 때문입니다. 다각형은 크기가 정해지지 않을 것입니다. (단 두 가지면이 32 개 미만이라고 가정 해 봅시다) 제가 바라는 것은 폴리곤을 여러 개의 레거 어 (legualar)로 분해 할 수 있다는 것입니다.

슬프게도, 나는 앞으로 나아갈 수있는 최선의 방법을 알고 있기 때문에이 시점에서 코드를 작성하지 않았습니다. 스크립트는 순수 JavasScript로 수행됩니다. 이것은 숙제가 아닙니다 :)

Answer 1

우선, 다각형이 볼록인지 오목인지 확인해야합니다. 후자라면, 여러 볼록 다각형을 "함께 넣어"따로 처리해야합니다. (폴리곤을 여러 개의 작은 폴리곤으로 자르는 커다란 가위 쌍을 상상해 보는 것은 쉽습니다.) 이 작업이 끝나면 하나의 다각형 또는 여러 개의 다각형이 있습니다.

각 다각형에 대해 다각형의 중점을 계산하면 (P (i), P ((i + 1) mod n), G는 사소한 양식 인 삼각형을 형성합니다. 이 삼각형들은 당신의 문제를 해결할 것입니다.

4 개의 각도로 모양이 필요한 경우 4 개의 연속 지점이 4 개의 각도 모양을 형성합니다. 그러나이 방법을 사용하면 메인 폴리곤의 중간에 더 작은 각도의 작은 폴리곤이 남게되어 처리해야합니다.