A Python library implementing a method for splitting a polygon into regions
Project description
polysplit
A lightweight library for splitting polygons into regions based on proximity of points.
Overview
Map quantization is the procedure of dividing a continuous map into a number of discrete regions. The simplest approach that has been used for hundreds of years is to overlap the map with a square grid. However, this approach ignores the geographical features of the map, making it suboptimal for certain applications. With this project, I would like to propose a novel algorithm that organically divides any given map into regions based on the relative travel time between different areas.
In its simple form, the proposed algorithm could be applied to a map (a polygon) with intraversible obstacles (holes). It works in 2 stages. In the first stage, the map is overlayed with a fine grid of $N$ points. Then, we calculate the shortest path (around the obstacles) betweeen every pair of points and construct the $N \times N$ distance matrix. In the second stage, we apply the k-medoids algorithm to the set of points, using the matrix from stage I as a distance function, and retrieve a set of $M$ centers. Finally, we construct a Voronoi graph around the centers, creating the regions.
Installation
pip install polysplit
Sample usage
import polysplit
from shapely.geometry import Polygon
# Create a polygon with a hole
outer_coords = [(0, 0), (0, 1), (1, 1), (1, 0)]
hole_coords = [(0.4, 0.4), (0.4, 0.6), (0.6, 0.6), (0.6, 0.4)]
polygon = Polygon(outer_coords, [hole_coords])
# Split the polygon
regions = polysplit.polysplit_main(polygon, k=5, num_points=100, plot=True)
print(regions)
Documentation
You can find the most up-to-date documentation here.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for polysplit-0.1.3-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 6e2de478033aecbef09d8cd9c5539c256f77ee8d20db1ec2b11363a2a7525cb2 |
|
MD5 | d0f0215a3cf615868895908410e09b1c |
|
BLAKE2b-256 | 65db0e5e23669712fb289b2c564aa144ceb7ac681ff336db8420015d69818ffe |