사각형이있는 직선형 다각형 (구멍 포함) 채우기

Question

NP 문제입니다.

그러나 가장 작은 수의 사각형이 필요하지 않습니다. 그냥 "다소"좋은 알고리즘.

그래서 문제가 있습니다. 나는 1의를 작성해야 http://en.wikipedia.org/wiki/Connected-component_labeling#mediaviewer/File%3aScreenshot-Pixel_Region_%28Figure_1%29.png

:

나는이 비슷한 진 픽셀 매트릭스를 가지고있다. 나는 픽셀 단위로 그릴 수 없다. 내가 계획 한 것은 영역을 직사각형으로 덮고 직사각형을 채우는 것입니다.

누군가 나를 도울 수 있습니까?

Answer 1

문제는 2D 경우 다항식이지만 3D에서는 NP 완성입니다. 이것은이 paper에 표시됩니다.

알고리즘의 아이디어는 2 차원 그래프의 경우 문제를 2 차원 그래프의 최대 매칭으로 줄이는 것입니다 (정점은 가능한 절단입니다.) page 또는이 presentation을 살펴보십시오.