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

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

---

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

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의 결합입니다 .

---

     

---

---

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

---

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

First: You need to know where these two shapes overlap. To do this, you could look at every edge in Polygon A and see where it intersects and edge in Polygon B. In this example, there should be two points of intersection.

Then: Make the union shape. You can take all of the vertices in A and B, and also the points of intersection, and then exclude the vertices that contained by the final shape. To find these points, it looks like you could just find any vertex of A that is inside B, and any vertext of B that is inside A.

---

Try gpc.

---

A solution I've seen using BSP trees is described here.

Basically, it describes intersection in terms of a union of the edges of polygon A that are inside polygon B (including partial edges, and calculated using a BSP tree). Then, you can define A / B as ~(~A /\ ~B), where ~ denotes reversing the winding of the polygon, / denotes union and /\ denotes intersection.

---

When grouping countries, I'd hope there be no overlap -- you could take a fairly naive algorithm that looks for shared vertices - a simple view would be to iterate through the points on one polygon, see if it's on any of your other polygons, and shares the same next or previous point to see if there is a match. Then just remove the shared vertex to create your union

---

나는 오늘 같은 문제를 해결해야했고이 lib로 해결책을 찾았습니다 : http://www.cs.man.ac.uk/~toby/alan/software/ .

Java, Obj-C, C #, Lua, python 등을 포함하여 여기 목록에 많은 언어 구현 이 있습니다.

---

나는 같은 문제에 직면했고 다음과 같은 방법으로 문제를 해결했습니다.

Angus Johnson의 Clipper 라이브러리 (버전 6.4.2)의 C ++ 번역을위한 Cython 래퍼 https://github.com/fonttools/pyclipper

pc = pyclipper.Pyclipper()
def get_poly_union(polygons):
    pc.AddPaths(polygons, pyclipper.PT_SUBJECT, True)
    solution = pc.Execute(pyclipper.CT_UNION, pyclipper.PFT_NONZERO, pyclipper.PFT_NONZERO)
    return solution[0]

print_image = image.copy()
solution = get_poly_union(polygons_array) 
#polygons_array=[polygon,polygon,polygon, ...,polygon] and polygon=[point,point,point...,point]

cv2.drawContours(print_image, [np.asarray(solution)], -1, (0, 255, 0), 2)

plt.imshow(print_image)

---

이것은 매우 오래된 질문이지만 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;
}

참고 URL : https://stackoverflow.com/questions/2667748/how-do-i-combine-complex-polygons