search

libgeos / geos

Geometry Engine, Open Source
https://libgeos.org
GNU Lesser General Public License v2.1
1.16k stars 351 forks source link

`voronoi_polygons` results in "IllegalArgumentException: point array must contain 0 or >1 elements" #1123

Open theroggy opened 2 months ago

theroggy commented 2 months ago

For a specific polygon, when using the shapely function voronoi_polygons with only_edges=True on it, this leads to the following error: "IllegalArgumentException: point array must contain 0 or >1 elements".

This function basically only calls GEOSVoronoiDiagram_r with flag GEOS_VORONOI_ONLY_EDGES.

Tested using shapely 2.0.4 and GEOS 3.12.1 and GEOS 3.12.2.

The input polygon looks like this, so it is not super complicated (128 points):

image

Python script to reproduce, including the polygon as wkt:

from matplotlib import pyplot as plt
import shapely
import shapely.plotting as plotter

wkt = "POLYGON ((116.28333282694416 40.00080645611787, 116.28339197890558 40.000688451583976, 116.28344990480007 40.00057289298457, 116.28360281358535 40.000353086732694, 116.28387467568555 40.000076798205235, 116.28398132163106 39.999984181062196, 116.28398135868984 39.99998412391061, 116.2839814280179 39.999984088530866, 116.28404774551952 39.99992632109312, 116.28430367280144 39.99973825519397, 116.2843944123716 39.99967212217683, 116.28439441919758 39.9996721136192, 116.28439443069314 39.99967210882053, 116.28463443069316 39.99949710897383, 116.28463443483709 39.99949710377589, 116.284634441818 39.99949710086081, 116.28478354181797 39.99938835095605, 116.28478452931236 39.99938711189437, 116.28478616133688 39.99938637400061, 116.2848432113369 39.99934182403832, 116.28484328133382 39.99934172907095, 116.28484340375283 39.99934167339791, 116.28536844023414 39.99892957589323, 116.28551412651535 39.998815789637646, 116.28671405430087 39.9979184903838, 116.28670472229507 39.99793948740504, 116.28670000042321 39.997954711301944, 116.28666000042324 39.99817471133864, 116.28665931852157 39.99817946595933, 116.28659950254068 39.998747717832735, 116.28654978328663 39.999055977253725, 116.28654958182572 39.99905731597655, 116.2863595818257 40.000417316151555, 116.28635990014789 40.00041887486223, 116.28635923019162 40.000420366725315, 116.28634990781505 40.00052291288156, 116.28631777843181 40.00061930106655, 116.28625700012654 40.00068007941316, 116.28608583743564 40.00079989341281, 116.28586472769199 40.0008352710125, 116.28581492013079 40.00085454218105, 116.28578436403508 40.00089030865483, 116.28578198787234 40.000922841672555, 116.28622980044125 40.000922841672555, 116.28640948500247 40.000797062591985, 116.28642234265145 40.00078631995827, 116.28650234265145 40.0007063200171, 116.2865212141385 40.00067653372378, 116.28656121413852 40.000556533759706, 116.2865643049646 40.00054184029621, 116.28657416607889 40.00043336804856, 116.2867638597298 39.9990755610446, 116.2868137518696 39.998766229821996, 116.28681342564228 39.99876444174787, 116.28681421663467 39.99876274101585, 116.28687396559599 39.9981951259485, 116.28691211944891 39.9979852798008, 116.28694592702394 39.9979092127861, 116.28717328212629 39.99758572569767, 116.28770982361726 39.99718367558446, 116.28803871622819 39.99694342851578, 116.28804256069155 39.99694047467563, 116.28820416069156 39.9968098747843, 116.28820483969291 39.996808915495194, 116.28820603435094 39.99680832117699, 116.28853443435095 39.996528921403076, 116.28854422828272 39.99651922949903, 116.28873422828268 39.996299229645814, 116.28873838666239 39.996294003640394, 116.28886716595927 39.99611778304137, 116.28886885672262 39.99611267991918, 116.28887300000302 39.9961084793765, 116.28891800000302 39.996023479415136, 116.28891813369742 39.99602265434311, 116.28891877096947 39.99602198137401, 116.2890037709695 39.995851981447544, 116.28906377094216 39.995731981554115, 116.28907377092894 39.99571198158917, 116.28907461076832 39.99570581783317, 116.28907834652075 39.99570032100081, 116.28913334652074 39.99551032105057, 116.28913332575151 39.99550995607025, 116.28913354234619 39.99550963060107, 116.28913618971484 39.995500100076356, 116.28871861814577 39.995500100076356, 116.28868327007278 39.99561321394175, 116.28868333812096 39.995615157397644, 116.28868223193071 39.995616907134206, 116.28867735650314 39.995636408848874, 116.28865864951372 39.995706560076194, 116.28863652499982 39.995759658929096, 116.28858848152777 39.99585266334279, 116.28858835558802 39.99585349838607, 116.28858771901345 39.99585418306149, 116.28855603931748 39.99591922924854, 116.28841372756791 39.99611846581413, 116.28807334709794 39.99645884653334, 116.28752056358519 39.996875399018236, 116.2875201460702 39.99687594261553, 116.28751943577669 39.99687626153862, 116.28690018035714 39.9973569047347, 116.28510277044172 39.99869817054737, 116.28510123969627 39.998700141436885, 116.28509871044673 39.99870136837376, 116.28502023318882 39.998766617425794, 116.28458069199121 39.99913071456925, 116.28453059839013 39.99917203810803, 116.28430825082552 39.999351683967355, 116.2841644596424 39.99946076702761, 116.28407430768047 39.999529147992746, 116.28364060672135 39.99984225977975, 116.28363912355066 39.99984409959511, 116.28363670957856 39.99984522040944, 116.28353702037447 39.99992491080807, 116.28353701753682 39.999924913076114, 116.2835370147544 39.99992491530034, 116.28345382555025 39.99999140568792, 116.28344318971158 40.00000135336017, 116.28324318971158 40.00022135351222, 116.28323654181176 40.0002296745823, 116.28307593146019 40.00046028506514, 116.28307168325652 40.00046712235719, 116.28299168325651 40.00061273277705, 116.28291168322463 40.000758343254944, 116.28290497374033 40.00077563474906, 116.2828701089502 40.000922841672555, 116.28328466738583 40.000922841672555, 116.28333282694416 40.00080645611787))"
poly = shapely.from_wkt(wkt)
print(f"{poly.is_valid=}")
# poly.is_valid=True

plotter.plot_polygon(poly)
plt.show()

shapely.voronoi_polygons(poly, only_edges=True)
# shapely.errors.GEOSException: IllegalArgumentException: point array must contain 0 or >1 elements

reference to original issue: https://github.com/pygeoops/pygeoops/issues/95

theroggy commented 1 month ago

In the mean time GEOS 3.12.2 became available via conda, and the error is still the same.

theroggy commented 1 month ago

I encountered a remark somewhere that voronoi creation can fail if there are points too close to each other.

So, when I first apply shapely.remove_repeated_points (=GEOSRemoveRepeatedPoints) with tolerance 1e-6 the error is gone.

Possibly a clearer error could be thrown to point the user in that direction?