Encountered some issues when using 'voronoi_polygons'

[shiyue-code]

I reported this issue in shapely, but it's an upstream GEOS issue. Can you tell me if this is something that can be optimized or if GEOS can't handle such a large amount of points.

Using voronoi_polygons(road) resulted in a memory usage of over 10 GB and then was forcibly terminated by the OOM killer. The road consists of approximately 4.6 million points forming polygons with holes. However, there were no issues encountered when using from scipy.spatial import Voronoi, and the memory usage was minimal.

Steps to reproduce the problem.

First import the geometry from the ’polygon.wkb‘ file. The file's cloud drive link is file: https://drive.google.com/file/d/14pH9wpJRURtokWLc_rpvo2jykLDSLN0-/view?usp=drive_link

This is the polygon representing a city road.

import shapely

with open("polygon.wkb", "rb") as f:
    borders = shapely.from_wkb(f.read())

Then use the following code to test if it will result in an OOM.

voronoied = voronoi_polygons(borders,only_edges=True) #equivalent to the scipy.spatial.Voronoi

scipy.spatial .Voronoi is ok

from scipy.spatial import Voronoi
points = []
exterior_points = list(borders.exterior.coords)
interior_points = []
for interior in borders.interiors:
    interior_points.extend(list(interior.coords))
points += exterior_points + interior_points
v = Voronoi(np.array(points))

Operating system

No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.3 LTS Release: 22.04 Codename: jammy

Shapely version and provenance

shapely 2.0.3 geos 3.11.1

[JamesParrott]

I can't say there is definitely no issue with Geos, but I wonder if you've just found a better method to solve your particular problem.

scipy.spatial uses QuickHull (from http://www.qhull.org/) whereas I think voronoi_polygons and Geos uses Guibas and Stolfi's Divide and Conquer to find the Delauney Triangulation. Geos uses Graham's Scan to calculate Convex Hulls.