다각형 목록에서 내부 고리 빼기

debugcn 에 게시 Dev

KarateKid

대부분의 다각형 (> 10 ^ 6)이 교차하지 않지만이 다각형 중 일부는 다른 다각형의 구멍입니다 (~ 10 ^ 3 케이스). 여기에 문제를 설명하는 이미지가 있습니다. 더 작은 다각형은 더 큰 다각형의 구멍이지만 둘 다 다각형 목록에서 독립적 인 다각형입니다.

이제 어떤 다각형이 구멍인지 효율적으로 결정하고 구멍을 빼고 싶습니다. 즉, 완전히 다른 다각형 안에있는 더 작은 다각형을 빼고 "정리 된"다각형 목록을 반환합니다. 한 쌍의 구멍과 부모 다각형은 다음과 같이 변환해야합니다 (기본적으로 부모에서 구멍을 뺍니다).

Stackoverflow 및 gis.stackexchange.com에는 유사한 질문이 많이 있지만 실제로이 문제를 해결하는 질문을 찾지 못했습니다. 다음은 몇 가지 관련 질문입니다. 1. https://gis.stackexchange.com/questions/5405/using-shapely-translating-between-polygons-and-multipolygons 2. https://gis.stackexchange.com/questions/319546 / converting-list-of-polygons-to-multipolygon-using-shapely

다음은 샘플 코드입니다.

from shapely.geometry import Point
from shapely.geometry import MultiPolygon
from shapely.ops import unary_union
import numpy as np

#Generate a list of polygons, where some are holes in others; 
def generateRandomPolygons(polygonCount = 100, areaDimension = 1000, holeProbability = 0.5):
    pl = []
    radiusLarge = 2 #In the real dataset the size of polygons can vary
    radiusSmall = 1 #Size of holes can also vary

    for i in range(polygonCount):
        x, y = np.random.randint(0,areaDimension,(2))
        rn1 = np.random.random(1)
        pl.append(Point(x, y).buffer(radiusLarge))
        if rn1 < holeProbability: #With a holeProbability add a hole in the large polygon that was just added to the list
            pl.append(Point(x, y).buffer(radiusSmall))
    return pl

polygons = generateRandomPolygons()
print(len(pl))

출력은 다음과 같습니다.

이제 구멍이 제거 된 새 다각형 목록을 어떻게 만들 수 있습니까? Shapely는 하나의 폴리곤을 다른 폴리곤에서 빼는 기능을 제공 하지만 ( 차이 ) 폴리곤 목록에 대해 유사한 기능 이 있습니까 ( unary_union 과 비슷 하지만 겹침이 제거되는 위치)? 구멍이 무엇인지 효율적으로 결정한 다음 더 큰 다각형에서 빼는 다른 방법은 무엇입니까?

마이크 와트

문제는 어떤 것이 "구멍"인지 모른다는 것입니다. 그렇죠? "어떤 다각형이 구멍인지 효율적으로 결정"하려면 rtree 를 사용 하여 교차 검사 속도를 높일 수 있습니다 .

from rtree.index import Index

# create an rtree for efficient spatial queries
rtree = Index((i, p.bounds, None) for i, p in enumerate(polygons))
donuts = []

for i, this_poly in enumerate(polygons):
    # loop over indices of approximately intersecting polygons
    for j in rtree.intersection(this_poly.bounds):
        # ignore the intersection of this polygon with itself
        if i == j:
            continue
        other_poly = polygons[j]
        # ensure the polygon fully contains our match
        if this_poly.contains(other_poly):
            donut = this_poly.difference(other_poly)
            donuts.append(donut)
            break  # quit searching

print(len(donuts))

이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.

침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제

에서 수정2021-04-5

몇 마디 만하겠습니다

0리뷰

로그인참여 후 검토

Related 관련 기사

기사

다각형 목록에서 내부 고리 빼기

다각형 목록에서 내부 고리 빼기

다른 내부에 사각형 그리기

Google지도를 사용하여 다각형 내부에 더 작은 다각형 그리기

도형 내부에 각도 호 그리기 [가파른 각도]

직사각형, 원형 및 다각형 내부에 마커 채우기

정사각형과 십자형의 내부와 주변에서 (x, y)를 찾기위한 알고리즘

Swing GUI Java의 패널 내에서 다각형 그리기

부울 그리드에서 다각형 찾기

R의 목록 내에서 행렬 목록 빼기

PIL을 사용하여 사각형 내부에 선 그리기

다각형에서 삼각형 목록 가져 오기

다각형 내에 단면 선 그리기

MYSQL은 내부 조인에서 빼기로 열을 업데이트합니다.

Sketchup API 뷰 클래스에서 오목 다각형 그리기

Android : 목록 조각에서 목록보기 외부를 클릭합니다.

(기본) R의 그룹 내에서 빼고 곱하기

VBO 내부의 OpenGL 분리 다각형

geo_polygon이 다중 다각형 내부에있는 경우 Elasticsearch 쿼리

Unity Coroutine 내부에서 이벤트를 기다리고 계십니까?

다른 여러 다각형의 특정 반경 내에서 다각형 찾기

내부에 dict가있는 목록에서 datafram하고 싶습니다.

nats 목록에서 기본형 정리

영역 내에서 삼각형을 찾기위한 알고리즘

목록 목록의 각 목록에서 고유 한 요소 가져 오기

XAML 내부에 도형 그리기?

목록 목록에서 목록 빼기

linq.js에서 목록 내부 목록에 대한 쿼리가 필요합니다.

다각형 그리기 순서 문제

더 큰 정삼각형 내부에 정삼각형 그리드 / 메시 만들기

Google지도에 다각형 그리기