Forem: Denny Danuwijaya

Optimizing Geometric Overlap Detection: A Deep Dive into Spatial Indexing with Python

Denny Danuwijaya — Wed, 18 Dec 2024 05:35:09 +0000

Spatial data processing can be computationally expensive, especially when dealing with large datasets. In this article, we'll explore different approaches to detecting geometric overlaps in Python, focusing on the performance of various spatial indexing techniques.

🎯 The Challenge of Geometric Intersections

When working with geospatial data, one common task is detecting overlaps or intersections between polygons. A naive approach of comparing every geometry with every other geometry quickly becomes inefficient as the dataset grows.

🔍 How Spatial Indexing Works

Let's visualize the difference between naive and spatial indexing approaches:

🐌 Naive Approach: The Brute Force Method

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

⚠️ Why Naive Approach is Not Recommended:

Time complexity is O(n²), where n is the number of geometries

Performance degrades exponentially with increasing dataset size

Becomes impractical for large datasets (thousands of geometries)

⚡ Spatial Indexing: A Performance Game-Changer

Spatial indexing works by creating a hierarchical data structure that organizes geometries based on their spatial extent. This allows for quick elimination of geometries that cannot possibly intersect, dramatically reducing the number of detailed intersection checks.

1️⃣ STRtree (Sort-Tile-Recursive Tree)

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 Key Concepts:

📦 Divides space into hierarchical regions
📏 Uses Minimum Bounding Rectangles (MBR)
🚀 Allows rapid filtering of non-intersecting geometries
📈 Reduces computational complexity from O(n²) to O(n log n)

2️⃣ Rtree Indexing

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 Key Concepts:

🌳 Organizes geometries in a balanced tree structure
📦 Uses bounding box hierarchies for quick filtering
⚡ Reduces unnecessary comparisons
🔍 Provides efficient spatial querying

📊 Comparative Analysis

Feature	STRtree (Sort-Tile-Recursive Tree)	RTree (Balanced Tree)
Time Complexity	O(n log n)	O(n log n)
Space Partitioning	Sort-Tile-Recursive	Balanced Tree
Performance	Faster	Relatively Slower
Memory Overhead	Moderate	Slightly Higher

📈 Benchmark Results

We tested these approaches on a dataset of 45,746 polygon geometries

⚡ Performance Metrics

Metric	STRtree	RTree	Naive Approach
Execution Time	1.3747 seconds	6.6556 seconds	Not run
Geometries Processed	45,746	45,746	N/A
Processing Rate	~33,219 features/sec	~9,718 features/sec	N/A

🔄 Overlap Analysis

Overlap Type	STRtree	RTree
Major Overlaps (≥20%)	5	5
Minor Overlaps (<20%)	23	23
Total Overlaps	28	28

💾 Memory Consumption

Stage	Memory Usage
Initial Memory	145.1 MB
Peak Memory	330.9 MB
Memory Increase	~185.8 MB

💡 Recommendations

Use Spatial Indexing: Always use spatial indexing for large datasets
Prefer STRtree: In our benchmark, STRtree outperformed RTree
Consider Dataset Size: For small datasets (<1000 geometries), a naive approach might be acceptable

🎯 When to Use Each

STRtree

📊 Large, uniformly distributed datasets
⚡ When speed is critical
🌍 Geospatial applications with many geometries

RTree

🔄 Datasets with complex spatial distributions
🎯 When precise spatial indexing is needed
🔍 Applications requiring flexible spatial queries

🛠️ Practical Takeaways

💡 Key Points to Remember

Always benchmark with your specific dataset

Consider memory constraints

Use spatial indexing for large geometric datasets

Profile and optimize based on your specific use case

🎉 Conclusion

Spatial indexing is crucial for efficient geometric intersection detection. By using techniques like STRtree, you can dramatically reduce computational complexity and processing time.

💡 Pro Tip: Always profile and benchmark your specific use case, as performance can vary based on data characteristics.

Thank you for reading! If you found this article helpful, please consider giving it a ❤️ and sharing it with others who might benefit from it.

Clustering Nest.js

Denny Danuwijaya — Mon, 08 Feb 2021 05:16:36 +0000

Server Clustering is a method of turning multiple computer servers into a cluster, which is a group of servers that acts like a single system. Its different with Load Balancer. Load Balancing is about the distribution of workloads across multiple computing resources, such as computers, server clusters, network links, etc.

In general, the cluster maximizes the processor performance of the server. If you have 8core processor, you can make it all work as cluster or you just need 2core, you can set it up.

This time, I will talk about how to create clusters for nestjs. As you know, Nestjs is a framework that can be relied on to build applications such as Rest API. I won't go into detail about the concept but will get straight to how it works.

Installation

For Nestjs Installation, you can look in the documentation. After you made it all, create app-cluster.service.ts in src/ directory.



import * as cluster from 'cluster';
import * as os from 'os';
import { Injectable } from '@nestjs/common';

const numCPUs = os.cpus().length;

@Injectable()
export class AppClusterService {
    static clusterize(callback: Function): void {
        if(cluster.isMaster){
            console.log(`Master server started on ${process.pid}`);
            for (let i = 0; i < numCPUs; i++) {
                cluster.fork();
            }
            cluster.on('exit', (worker, code, signal) => {
                console.log(`Worker ${worker.process.pid} died. Restarting`);
                cluster.fork();
            })
        } else {
            console.log(`Cluster server started on ${process.pid}`)
            callback();
        }
    }
}

Then, you can called it in main.ts in src/ directory.




import { NestFactory } from '@nestjs/core';
import { AppModule } from './app.module';
import { AppClusterService } from './app_cluster.service';

async function bootstrap() {
  const app = await NestFactory.create(AppModule);
  await app.listen(3000);
}

//Call app-cluster.service.ts here.
AppClusterService.clusterize(bootstrap);

Now, run you app using nodemon or pm2. I used PM2 to run the project. pm2 start dist/main.js -i max. -i max as a sign of how many cores we will use. If max, that means all we will use. Or you just change the max with specified number. (Note: run npm run build to generate dist directory.)

a. Using max resources.

b. Using specified resources. e.g 4

If either worker crashes or dies, it will be automatically moved to the live worker as the server prepares a new worker to replace the crashed worker.

Github Repo : https://github.com/danudenny/nestjs-cluster

I want to discuss further about this, maybe there is a statement from me that is wrong or maybe there is a suggestion to be more effective and efficient.

NestJS multi .env using 'nestjs-easyconfig'.

Denny Danuwijaya — Mon, 11 Jan 2021 07:14:48 +0000

Environment variables commonly used in many programming language as a variable which used to save such information like database credentials, caching credentials, and many more. With environment variables, we can call a variables easily.

In this tutorial, i will explain how to make multiple environment variables and consume it to another service / controller using 'nestjs-easyconfig' with NestJS framework. You can find out full documentation about Nestjs here.

Installation

I assumed you have a nestjs project, or you can make fresh project using nestjs cli nest new <project_name>. If all ready to setup, we can install nestjs-easyconfig using npm i nestjs-easyconfig.

Next step is create environment directory in root directory. and create two different .env files .env.production and .env.development. In this case, we can separate 2 different environment, which is the credentials is totally different each others. If you only have one environment, don't use this method! Simply use one .env and put it in root directory.

Write your credentials in all .env files on environtment folder. For example, i will write my credentials in .env.development and .env.production



DB_HOST=localhost
DB_USERNAME=postgres
DB_PASSWORD=postgres
DB_NAME=database_name
DB_PORT=5432
PORT=3002
NODE_ENV=development



DB_HOST=localhost
DB_USERNAME=postgres
DB_PASSWORD=postgres
DB_NAME=database_name
DB_PORT=5432
PORT=3001
NODE_ENV=production

You can choose which environment to use using .env files in root directory.



NODE_ENV=development



NODE_ENV=production

Configuration

Create config folder in src directory. Then create service file easyconfig.service.ts.



//easyconfig.service.ts

import { Injectable, OnModuleInit } from "@nestjs/common";
import { EasyconfigService } from "nestjs-easyconfig";
import * as dotenv from 'dotenv';
import * as fs from 'fs';

@Injectable()
export class EasyConfiguration implements OnModuleInit {
    constructor(private easyConfigService: EasyconfigService) {}

    onModuleInit() {
        return this.easyConfigService.get('envConfig');
    }
}

Add easyconfig module in app.module.ts and call easyconfig service in app.module.ts providers.



//app.module.ts

import { Module } from '@nestjs/common';
import { ConfigModule } from '@nestjs/config';
import { EasyconfigModule } from 'nestjs-easyconfig';
import { AppController } from './app.controller';
import { AppService } from './app.service';
import { EasyConfiguration } from './configs/easyconfig.service';
require('dotenv').config();

@Module({
  imports:  [EasyconfigModule.register({path: `environment/.env.${process.env.NODE_ENV}`, safe: true})],
  controllers: [AppController],
  providers: [AppService, EasyConfiguration],
})
export class AppModule {}

Simply change your .env in root folder to select which environment to use.
Source Code.