교차하는 직사각형의 집합이 주어지면 경계 다각형을 찾기위한 표준 알고리즘이 있습니까? (직사각형의 합집합과 정확히 같은 영역을 경계로하는 다각형) 직사각형은 두 직교 축을 따라 변하는 동일한 방법으로 모든 방향을 향하는 것으로 가정 할 수 있습니다.여러 사각형에 대한 경계 (오목) 다각형?
검색 할 때 볼록한 경계 다각형에 대한 알고리즘을 찾았지만, 여기서 실제로는 영역 만 포함하는 것을 선호합니다. 오각형 일 가능성이 큽니다.
(즉,이 경계 다각형의 내부에 포함하는 사각형은 완전히 확인 영역을 둘러싸합니다.)
직사각형의 결합을 계산해야하는 경우, 이는 계산 기하학에서 일반적으로 "병합"연산으로 알려져 있습니다. 일반적으로 스윕 라인 알고리즘으로 구현됩니다.
스윕 라인 방식은 일반적으로 상당한 초기 투자가 필요합니다. 스윕 라인 엔진 구현. 완료되면 엔진을 즉시 "merge", "and", "or", "diff"등과 같이 입력 지오메트리에 대한 모든 집합 지향 연산을 쉽게 구현할 수 있습니다.
http://en.wikipedia.org/wiki/Boolean_operations_on_polygons
한편 대한 구현 스윕 라인 엔진 축 중심 (isothetic) 형상이 다소 간단한 작업이다. 방대한 입력을 처리해야하는 상황, 즉 직사각형의 수가 상대적으로 많을 때 최상의 방법입니다. 다른 답변에서 언급 된 다양한 엣지 - 트래버 설 기반 접근법은 상대적으로 작은 입력에서만 잘 작동합니다.
이것은 실제로 문제를 해결할 때 가장 유용한 답이었습니다. 내가 원하는 것을하기 위해 기존의 알고리즘을 찾지는 못했지만 [몇 가지 다른 변형] (http://community.topcoder.com/tc?module)을보고 스윕 라인 접근 방식을 적용하는 것은 비교적 간단했습니다. = 정적 & d1 = 자습서 & d2 = lineSweep). 감사! – starwed
그것을 할 수있는 표준 방법이 있는지 잘 모르겠지만, 그것이 나에게 발생 바운딩 폴리곤의 꼭지점은 사각형의 모서리와 그 변이 교차하는 점이며, 사각형 내에있는 점을 제외합니다.
포인트를 주문하려면 세트에서 한 포인트부터 시작하십시오. 그것은 두 개의 모서리의 교차점이거나 모서리입니다. 따라서 적어도 두 개의 모서리에있을 수 있습니다. 다음 지점으로 갈 때까지 가장자리 중 하나를 따라 이동하십시오. 내부 포인트를 이미 제거했기 때문에 내부에서 끝나기 전에 항상 다른 꼭지점을 공격합니다.
한 모서리의 모서리가 다른 모서리의 모서리를 따르는 경우 모서리에서 한 경로가 사각형의 내부로 이어 지므로주의해야합니다. 따라서 추적 할 오른쪽 모서리를 선택하는 몇 가지 요소가 있습니다. 그러나 그들이 내부에 있기 때문에 제외시킨 점수 목록을 유지한다면 제외 된 지점으로가는 것이 잘못된 방향이라는 것을 알고 있습니다.
편집 더 자세히 명시하겠습니다.
(1) 모든 직사각형의 모든면에서 시작하십시오. 교차점을 계산하고 가장자리를 분할하십시오.
(2) 세그먼트 목록이 있습니다. 모든 세그먼트의 끝점을 확인하여 사각형의 내부에 있는지 확인하십시오.
(3) 다른 끝점이있는 하나 이상의 세그먼트의 끝점 인 외부 끝점 중 하나를 가져옵니다. 외부 끝점. 엔드 포인트에서 다른 외부 엔드 포인트로 선을 그립니다.
(4) 외부 종점은 다른 외부 종단점이있는 다른 세그먼트의 종단점이어야합니다. 해당 외부 끝점에 선을 그립니다.
(5) 시작한 끝점으로 돌아갈 때까지 반복하십시오.
** ** 직사각형의 교차점 **? 또는 사각형의 ** 노조 **? 경계 다각형은 합집합이됩니다. 그러나 어떤 이유로 당신은 교차로에 대해서 이야기합니다. BTW, 당신의 직사각형은 동심원입니까? – AnT
@AndreyT 그래, 나는 조합을 의미했다. 단지 멍청한 두뇌 방귀다. 그리고 직사각형 (따라서 노동 조합)은 모두 이성적입니다. – starwed