불규칙 다각형을위한 효율적인 패킹 알고리즘

Question

불규칙한 다각형을 직사각형과 직각 삼각형으로 줄이는 패킹 알고리즘을 찾고 있습니다. 알고리즘은 가능한 한 적은 수의 형상을 사용하려고 시도해야하며 구현이 비교적 쉽습니다 (도전의 어려움을 감안할 때). 또한 가능한 경우 삼각형에 비해 직사각형을 선호해야합니다.

가능한 경우이 질문에 대한 대답은 제안 된 알고리즘에서 사용 된 일반적인 경험적 방법을 설명해야합니다.

정점이 100 개 미만인 불규칙한 다각형의 경우 결정적으로 실행되어야합니다.

목표는 평신도를위한 불규칙한 다각형의 "감각적 인"고장을 만드는 것입니다.

솔루션에 적용된 첫 번째 경험적 방법은 다각형이 규칙적인지 또는 불규칙한지를 결정합니다. 정다각형의 경우, 우리는 정기적으로 폴리곤에 대한 내 비슷한 게시물에 설명 된 방법 사용 : Efficient Packing Algorithm for Regular Polygons

alt text http://img401.imageshack.us/img401/6551/samplebj.jpg

Answer 1

이 최적의 대답을 줄 것인지 모르겠어요,하지만 그것은 것 이상 답을주십시오 :

1. 주어진 다각형에 대해 델라 네이 삼각 측량을 계산하십시오. 이를 수행하는 표준 알고리즘이 100 개 이하의 정점에서 매우 빠르게 실행됩니다 (예 : this library here. 참조). Delaunay 삼각 측량을 사용하면 길고 얇은 삼각형이 너무 많이 없어야합니다.
2. 가장 큰 각도에서 반대쪽으로 고도를 떨어 뜨려 비 직각 삼각형을 두 개의 직각 삼각형으로 나누십시오.
3. 직사각형을 결합 할 수있는 삼각형을 검색하십시오 : 빗변을 공유하는 두 개의 일치하는 직각 삼각형 (미러 이미지가 아닙니다). 불규칙한 다각형이 처음부터 많은 직각을 가지지 않는 한 일반적인 경우에는 너무 많지 않을 것이라고 생각합니다.

필자가 작성해야 할 세부 사항은 많이 있지만 필자는 Delaunay 삼각 측량으로 시작한다고 생각할 것입니다. 비행기에서의 델라 네이 삼각 측량은 효율적으로 계산할 수 있으며 일반적으로 상당히 자연 스럽습니다.

우리가 임시 휴리스틱 스빌에 있기 때문에 다른 답변에서 논의되는 욕심 많은 알고리즘 외에도 일종의 분열과 정복 전략을 고려해야합니다. 예를 들어 모양이 볼록하지 않은 경우 가능한 한 반사 각도를 양분하는 것과 비슷한 방식으로 반사 정점에서 다른 정점으로 반복적으로 자르기하여 볼록한 모양으로 나눕니다. 일단 모양을 볼록한 조각으로 나눈 다음, 볼록 조각을 멋진 "기초"조각으로 나눈 다음, 적어도 한면이 끝 부분에 두 개의 예각 또는 직각이있는 조각으로 나누는 것을 고려해 보겠습니다. 어떤 조각에 그러한 "기초"가 없다면 조각의 지름을 따라 2로 나눌 수 있어야하며 각각에 "기본"이있는 두 개의 새로운 조각을 얻을 수 있어야합니다 (제 생각 엔). 이것은 사다리꼴 사다리꼴 인 볼록 다각형을 다루는 문제를 줄여야하며, 거기에서 욕심 많은 알고리즘은 잘해야합니다. 나는이 알고리즘이 당신이 다소 사다리꼴 조각들에 도달 할 때까지 원래의 모양을 아주 자연스럽게 세분 할 것이라고 생각합니다.

Answer 2

정말 재미있는 문제로 들리기 때문에이 시간을 갖고 싶습니다.

첫 번째 생각 (위의 다이어그램을 보면)은 같은 방향으로 회전하는 2 개의 인접한 직각을 찾는 것입니다.직사각형이 도움이되는 모든 경우를 포착하지는 않지만 사용자의 관점에서 볼 때 명백한 사례입니다 (바깥 쪽 사각형 모서리 = 사각형이어야합니다).

직각의 인접한 쌍을 찾았 으면 짧은 다리의 길이를 취하고 하나의 직사각형이 있습니다. 왼쪽에서 타일까지 다각형에서 이것을 빼고 반복하십시오. 제거 할 외부 사각형이 더 이상 없을 때는 일반적인 타일링 작업 (Peter 's answer great)을 사용하십시오.

면책 조항 :이에 오는 '불규칙한 다각형'의 첫 번째 예제없는 점에서