Open shiyue-code opened 5 months ago
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.
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.
Then use the following code to test if it will result in an OOM.
scipy.spatial .Voronoi is ok
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