[math] 복잡한 다각형을 어떻게 결합합니까?

Program / 글쓴이

두 개의 다각형이 주어지면 :

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

합집합 (결합 다각형)은 어떻게 계산할 수 있습니까?

여기에 이미지 설명 입력

Dave의 예 에서는 SQL 서버를 사용하여 유니온을 생성하지만 코드에서 동일한 작업을 수행해야합니다. 실제 수학을 노출하는 모든 언어로 된 수학 공식 또는 코드 예제를 찾고 있습니다. 국가를 동적으로 지역으로 결합하는지도를 만들려고합니다. 여기에 관련 질문을했습니다. 지리적 형태 그룹화

답변

이것은 아주 좋은 질문입니다. 얼마 전에 C #에서 동일한 알고리즘을 구현했습니다. 알고리즘은 두 다각형의 공통 윤곽을 구성합니다 (즉, 구멍없이 결합을 구성합니다). 여기있어.

골

1 단계. 다각형을 설명하는 그래프를 만듭니다.

입력 : 첫 번째 다각형 (n 포인트), 두 번째 다각형 (m 포인트). 출력 : 그래프. 정점-다각형 교차점.

교차로를 찾아야합니다. 두 다각형 [O (n * m)]의 모든 다각형면을 반복하고 교차점을 찾습니다.

  • 교차점이 없으면 정점을 추가하고 가장자리에 연결하기 만하면됩니다.

  • 교차점이 발견되면 길이별로 시작점까지 정렬하고 모든 꼭지점 (시작, 끝 및 교차점)을 추가 한 다음 (이미 정렬 된 순서대로) 가장자리에 연결합니다.
    그래프

2 단계. 구성된 그래프 확인

그래프를 만들 때 교차점을 찾지 못한 경우 다음 조건 중 하나가 있습니다.

  1. Polygon1에 polygon2가 포함됨-polygon1 반환
  2. Polygon2에는 polygon1이 포함되어 있습니다-polygon2 반환
  3. Polygon1과 polygon2는 교차하지 않습니다. 다각형 1과 다각형 2를 반환합니다.

3 단계. 왼쪽 아래 꼭지점을 찾습니다.

최소 x 및 y 좌표 (minx, miny)를 찾습니다. 그런 다음 (minx, miny)와 다각형 점 사이의 최소 거리를 찾으십시오. 이 지점은 왼쪽 하단 지점이됩니다.

왼쪽 하단 지점

4 단계. 공통 윤곽을 만듭니다.

왼쪽 하단 지점에서 그래프를 횡단하고 다시 들어갈 때까지 계속합니다. 처음에는 모든 모서리를 방문하지 않은 것으로 표시합니다. 반복 할 때마다 다음 지점을 선택하고 방문한 것으로 표시해야합니다.

다음 점을 선택하려면 시계 반대 방향으로 최대 내부 각도가있는 모서리를 선택합니다.

두 벡터를 계산합니다 : 현재 가장자리에 대해 vector1과 다음 방문하지 않은 각 가장자리에 대해 vector2 (그림 참조).

벡터의 경우 다음을 계산합니다.

  1. 스칼라 곱 (내적). 벡터 사이의 각도와 관련된 값을 반환합니다.
  2. 벡터 곱 (교차 곱). 새로운 벡터를 반환합니다. 이 벡터의 z 좌표가 양수이면 스칼라 곱은 시계 반대 방향으로 직각을 제공합니다. 그렇지 않으면 (z 좌표가 음수 임) 벡터 사이의 각도를 스칼라 곱에서 360 각도로 계산합니다.

결과적으로 최대 각도를 가진 가장자리 (및 해당 다음 정점)를 얻습니다.

전달 된 각 정점을 결과 목록에 추가합니다. 결과 목록은 유니온 폴리곤입니다.
벡터

비고

  1. 이 알고리즘을 사용하면 여러 다각형을 병합하여 다각형 쌍을 반복적으로 적용 할 수 있습니다.
  2. 많은 베 지어 곡선과 선으로 구성된 경로가있는 경우 먼저이 경로를 병합해야합니다.

답변

이것은 도전적이지만 잘 이해되고있는 주제이며 종종 “폴리곤에 대한 정규화 된 부울 연산”이라는 이름으로 사용됩니다. 아래 그림 ( Alan Murta의 클리핑 라이브러리에서 ) 을 포함하는 이 MathOverflow 답변을 볼 수 있습니다
. 분홍색 합집합은 OP의 결합입니다 .

 
 
 
BooleanOps

답변

어떤 점이 내부 에 있는지 확인 해야합니다 . 이러한 점을 제거한 후 “외부”점 집합을 다른 점에 삽입 할 수 있습니다. 삽입 지점 (예 : 오른쪽 그림에서 화살표가있는 위치)은 입력 세트에서 지점을 제거해야하는 지점입니다.

답변

좋은 질문! 나는 전에 이것을 시도한 적이 없지만 지금 시도해 볼 것입니다.

첫째 :이 두 모양이 겹치는 부분을 알아야합니다. 이렇게하려면 다각형 A의 모든 가장자리를보고 교차하는 위치와 다각형 B의 가장자리를 볼 수 있습니다.이 예에서는 두 개의 교차점이 있어야합니다.

그런 다음 : 결합 모양을 만듭니다. A와 B의 모든 정점과 교차점을 가져온 다음 최종 모양에 포함 된 정점을 제외 할 수 있습니다. 이 점을 찾으려면 B 내부에있는 A의 정점과 A 내부에있는 B의 정점을 찾을 수있는 것처럼 보입니다.

답변

gpc 시도하십시오 .

답변

BSP 트리를 사용하여 본 솔루션이 여기 에 설명되어 있습니다 .

기본적으로 다각형 B 내부 에있는 다각형 A 의 가장자리 (부분 가장자리 포함, BSP 트리를 사용하여 계산) 의 결합으로 교차를 설명합니다 . 그런 다음 A  /  B 를 ~ (~ A  / \ ~ B ) 로 정의 할 수 있습니다 . 여기서 ~는 다각형의 권선 반전을 나타내고 /는 합집합을 나타내고 / \는 교차를 나타냅니다.

답변

이것은 매우 오래된 질문이지만 Boost의 Union_ 함수가 저에게 효과적 이었습니다.

아래 스 니펫을 참조하세요.

#include <iostream>
#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>

#include <boost/foreach.hpp>


int main()
{
    typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;

    polygon green, blue;

    boost::geometry::read_wkt(
        "POLYGON((0 0, 0 10, 10 10, 10 0, 0 0))", green);

    boost::geometry::read_wkt(
        "POLYGON((5 5, 5 15, 15 15, 15 5, 5 5))", blue);

    std::vector<polygon> output;
    boost::geometry::union_(green, blue, output);

    int i = 0;
    std::cout << "green || blue:" << std::endl;
    BOOST_FOREACH(polygon const& p, output)
    {
        std::cout << i++ << ": " << boost::geometry::area(p) << std::endl;

        for (int i = 0; i < p.outer().size(); i++)
        {
            std::cout << p.outer().at(i).x() << " " << p.outer().at(i).y() << std::endl;
        }
    }



    return 0;
}