بهینه سازی تشخیص همپوشانی هندسی: فرو رفتن عمیق در نمایه سازی فضایی با پایتون

Summarize this content to 400 words in Persian Lang
پردازش داده‌های مکانی می‌تواند از نظر محاسباتی گران باشد، به‌ویژه زمانی که با مجموعه داده‌های بزرگ سروکار داریم. در این مقاله، رویکردهای مختلف برای تشخیص همپوشانی‌های هندسی در پایتون، با تمرکز بر عملکرد تکنیک‌های مختلف نمایه‌سازی فضایی را بررسی خواهیم کرد.

🎯 چالش تقاطع های هندسی

هنگام کار با داده های مکانی، یکی از وظایف رایج تشخیص همپوشانی ها یا تقاطع ها بین چند ضلعی ها است. یک رویکرد ساده لوحانه در مقایسه هر هندسه با هر هندسه دیگر به سرعت با رشد مجموعه داده ناکارآمد می شود.

🔍 نمایه سازی فضایی چگونه کار می کند

بیایید تفاوت بین رویکردهای نمایه سازی ساده و فضایی را مجسم کنیم:

🐌 رویکرد ساده لوحانه: روش نیروی بی رحم

def check_overlaps_naive(gdf):
errors = [] for i in range(len(gdf)):
for j in range(i + 1, len(gdf)):
geom1 = gdf.iloc[i].geometry
geom2 = gdf.iloc[j].geometry

if geom1.intersects(geom2):
# Process intersection
intersection = geom1.intersection(geom2)
# Add to errors list
return errors

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

⚠️ چرا رویکرد ساده لوحانه توصیه نمی شود:

پیچیدگی زمانی O(n²) است، که در آن n تعداد هندسه ها است
با افزایش اندازه مجموعه داده، عملکرد به طور تصاعدی کاهش می یابد
برای مجموعه داده های بزرگ (هزاران هندسه) غیر عملی می شود

⚡ نمایه سازی فضایی: یک بازی تغییر دهنده عملکرد

نمایه سازی فضایی با ایجاد یک ساختار داده سلسله مراتبی کار می کند که هندسه ها را بر اساس وسعت فضایی آنها سازماندهی می کند. این امکان حذف سریع هندسه‌هایی را فراهم می‌کند که احتمالاً نمی‌توانند قطع شوند و تعداد بررسی‌های دقیق تقاطع را به‌طور چشمگیری کاهش می‌دهد.

1️⃣ STRtree (درخت مرتب سازی-کاشی-بازگشتی)

from shapely import STRtree

def check_overlaps_strtree(gdf):
# Create the spatial index
tree = STRtree(gdf.geometry.values)

# Process each geometry
for i, geom in enumerate(gdf.geometry):
# Query potential intersections efficiently
potential_matches_idx = tree.query(geom)

# Check only potential matches
for j in potential_matches_idx:
if j <= i:
continue

other_geom = gdf.geometry[j] # Detailed intersection test
if geom.intersects(other_geom):
# Process intersection
intersection = geom.intersection(other_geom)
# Record results

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

🔑 مفاهیم کلیدی STRtree:

📦 فضا را به مناطق سلسله مراتبی تقسیم می کند
📏 از مستطیل های حداقل محدود (MBR) استفاده می کند
🚀 امکان فیلتر کردن سریع هندسه های غیر متقاطع را فراهم می کند
📈 پیچیدگی محاسباتی را از O(n²) به O(n log n) کاهش می دهد.

2️⃣ نمایه سازی Rtree

import rtree

def check_overlaps_rtree(gdf):
# Create spatial index
idx = rtree.index.Index()

# Insert geometries with their bounding boxes
for i, geom in enumerate(gdf.geometry):
idx.insert(i, geom.bounds)

# Process geometries
for i, row in enumerate(gdf.itertuples()):
geom1 = row.geometry

# Find potential intersections using bounding boxes
for j in idx.intersection(geom1.bounds):
if j <= i:
continue

geom2 = gdf.iloc[j].geometry
# Detailed intersection test
if geom1.intersects(geom2):
# Process intersection
intersection = geom1.intersection(geom2)

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

🔑 مفاهیم کلیدی RTree:

🌳 هندسه ها را در ساختار درختی متعادل سازماندهی می کند
📦 از سلسله مراتب جعبه محدود برای فیلتر کردن سریع استفاده می کند
⚡ مقایسه های غیر ضروری را کاهش می دهد
🔍 پرس و جوی فضایی کارآمد را ارائه می دهد

📊 تحلیل مقایسه ای

ویژگی
STRtree (مرتب‌سازی-کاشی-درخت بازگشتی)
RTree (درخت متعادل)

پیچیدگی زمانی
O(n log n)
O(n log n)

پارتیشن بندی فضا
مرتب سازی – کاشی – بازگشتی
درخت متعادل

عملکرد
سریعتر
نسبتا کندتر

سربار حافظه
متوسط
کمی بالاتر

📈 نتایج محک

ما این رویکردها را روی مجموعه داده ای از 45746 هندسه چند ضلعی آزمایش کردیم

⚡ معیارهای عملکرد

متریک
STRtree
RTree
رویکرد ساده لوحانه

زمان اجرا
1.3747 ثانیه
6.6556 ثانیه
اجرا نمی شود

هندسه پردازش شده
45746
45746
N/A

نرخ پردازش
~33219 ویژگی در ثانیه
~9718 ویژگی در ثانیه
N/A

🔄 تجزیه و تحلیل همپوشانی

نوع همپوشانی
STRtree
RTree

همپوشانی های عمده (≥20%)
5
5

همپوشانی های جزئی (

def check_overlaps_naive(gdf):
    errors = []
    for i in range(len(gdf)):
        for j in range(i + 1, len(gdf)):
            geom1 = gdf.iloc[i].geometry
            geom2 = gdf.iloc[j].geometry

            if geom1.intersects(geom2):
                # Process intersection
                intersection = geom1.intersection(geom2)
                # Add to errors list
    return errors

from shapely import STRtree

def check_overlaps_strtree(gdf):
    # Create the spatial index
    tree = STRtree(gdf.geometry.values)

    # Process each geometry
    for i, geom in enumerate(gdf.geometry):
        # Query potential intersections efficiently
        potential_matches_idx = tree.query(geom)

        # Check only potential matches
        for j in potential_matches_idx:
            if j <= i:
                continue

            other_geom = gdf.geometry[j]
            # Detailed intersection test
            if geom.intersects(other_geom):
                # Process intersection
                intersection = geom.intersection(other_geom)
                # Record results

import rtree

def check_overlaps_rtree(gdf):
    # Create spatial index
    idx = rtree.index.Index()

    # Insert geometries with their bounding boxes
    for i, geom in enumerate(gdf.geometry):
        idx.insert(i, geom.bounds)

    # Process geometries
    for i, row in enumerate(gdf.itertuples()):
        geom1 = row.geometry

        # Find potential intersections using bounding boxes
        for j in idx.intersection(geom1.bounds):
            if j <= i:
                continue

            geom2 = gdf.iloc[j].geometry
            # Detailed intersection test
            if geom1.intersects(geom2):
                # Process intersection
                intersection = geom1.intersection(geom2)