आकार

Question

के साथ बहुभुज चौराहे का तेज़ तरीका मेरे पास बड़ी संख्या में बहुभुज (~ 100000) हैं और नियमित ग्रिड कोशिकाओं के साथ अपने अंतरंग क्षेत्र की गणना करने का एक स्मार्ट तरीका खोजने का प्रयास करें।

वर्तमान में, मैं बहुभुज और ग्रिड कोशिकाओं को आकार (उनके कोने निर्देशांक के आधार पर) का उपयोग कर बना रहा हूं। फिर, एक साधारण फॉर-लूप का उपयोग करके मैं प्रत्येक बहुभुज के माध्यम से जाता हूं और इसकी तुलना पास के ग्रिड कोशिकाओं से करता हूं।

बहुभुज/ग्रिड कोशिकाओं को चित्रित करने के लिए बस एक छोटा सा उदाहरण।

from shapely.geometry import box, Polygon 
# Example polygon 
xy = [[130.21001, 27.200001], [129.52, 27.34], [129.45, 27.1], [130.13, 26.950001]] 
polygon_shape = Polygon(xy) 
# Example grid cell 
gridcell_shape = box(129.5, -27.0, 129.75, 27.25) 
# The intersection 
polygon_shape.intersection(gridcell_shape).area 

:

वास्तव में इस के आसपास 0.003 सेकंड के साथ एक व्यक्ति बहुभुज/ग्रिड सेल कॉम्बो के लिए काफी तेजी से होता है (btw ग्रिड कोशिकाएं आयाम 0.25x0.25 और अधिकतम पर बहुभुज 1x1 है)। हालांकि, इस कोड को बड़ी मात्रा में बहुभुजों पर चलाया जा रहा है (प्रत्येक व्यक्ति दर्जनों ग्रिड कोशिकाओं को छेड़छाड़ कर सकता है) मेरी मशीन पर लगभग 15+ मिनट (ग्रिड कोशिकाओं को छेड़छाड़ करने की संख्या के आधार पर 30+ मिनट तक) लेता है जो स्वीकार्य नहीं है। दुर्भाग्य से, मुझे नहीं पता कि ओवरलैप के क्षेत्र को पाने के लिए पॉलीगॉन चौराहे के लिए कोड लिखना संभव है। क्या आपके पास कोई टिप हैं? क्या आकार देने का कोई विकल्प है?

Answer 1

Rtree का उपयोग करने पर विचार करें ताकि यह पता लगाने में मदद मिल सके कि बहुभुज कोशिकाएं कितनी ग्रिड कोशिकाओं को छेड़छाड़ कर सकती हैं। इस तरह, आप लूप/लॉन्स की सरणी के साथ उपयोग किए जाने वाले लूप को हटा सकते हैं, जो शायद धीमा हिस्सा है।

संरचना इस तरह अपने कोड कुछ:

from shapely.ops import cascaded_union 
from rtree import index 
idx = index.Index() 

# Populate R-tree index with bounds of grid cells 
for pos, cell in enumerate(grid_cells): 
    # assuming cell is a shapely object 
    idx.insert(pos, cell.bounds) 

# Loop through each Shapely polygon 
for poly in polygons: 
    # Merge cells that have overlapping bounding boxes 
    merged_cells = cascaded_union([grid_cells[pos] for pos in idx.intersection(poly.bounds)]) 
    # Now do actual intersection 
    print poly.intersection(merged_cells).area 

Answer 2

यह उपलब्ध The Shapely User Manual की तरह दिखता है बल्कि पुराना हो चुका है, लेकिन 2013/2014 के बाद से, सुडौल वर्ग STRtree साथ strtree.py पड़ा है। मैंने इसका इस्तेमाल किया है और ऐसा लगता है कि यह अच्छी तरह से काम करता है।

यहाँ docstring से एक टुकड़ा है:

STRtree एक आर-वृक्ष कि क्रमबद्ध-टाइल पुनरावर्ती कलन विधि का उपयोग बनाया जाता है। STRtree प्रारंभिक पैरामीटर के रूप में ज्यामिति वस्तुओं का एक अनुक्रम लेता है। प्रारंभ करने के बाद क्वेरी ऑब्जेक्ट का उपयोग उन वस्तुओं पर स्थानिक क्वेरी बनाने के लिए किया जा सकता है।

>>> from shapely.geometry import Polygon 
>>> polys = [ Polygon(((0, 0), (1, 0), (1, 1))), Polygon(((0, 1), (0, 0), (1, 0))), Polygon(((100, 100), (101, 100), (101, 101))) ] 
>>> s = STRtree(polys) 
>>> query_geom = Polygon(((-1, -1), (2, 0), (2, 2), (-1, 2))) 
>>> result = s.query(query_geom) 
>>> polys[0] in result 
True