GEOSConstrainedDelaunayTriangulation_r loops forever on a valid polygon

[nraynaud]

I have a polygon that seems to make GEOSConstrainedDelaunayTriangulation_r() loop forever while reserving more and more memory.
isValid() returns true

je actual library I used is LibGEOS.jl v0.6.12
the underlying GEOS version seems to be GEOS_jll.jl (v3.10.2+0)

it happened on a macbook pro: 'Darwin 21.4.0 Darwin Kernel Version 21.4.0: Fri Mar 18 00:45:05 PDT 2022; root:xnu-8020.101.4~15/RELEASE_X86_64 x86_64'

here is a quick Julia demonstration:

        # this function seems to cause a memory leak in the C part.
        wkt = "POLYGON ((1.7862685046962532 0.2923021911868067, 1.7728389809573666 0.2627438719792648, 1.746100000000001 0.2334000000000009, 1.7150804631420686 0.2161586105737922, 1.6759 0.209, 0.3241 0.209, 0.2840389403162291 0.2165244534091589, 0.26281199593527 0.2271117271007482, 0.2451970039279606 0.2409124780256404, 0.220203873371505 0.2753019366857534, 0.2119959512407714 0.2984989878101932, 0.209 0.3233, 0.209 1.6759, 0.2114712418577923 1.6990146526776198, 0.2178177033571282 1.7193153375833403, 0.2407676132817306 1.7547086448098228, 0.2571000000000007 1.7690000000000003, 0.2775992176450858 1.7808316429453195, 0.3030606643061082 1.7889360141633408, 0.324 1.791, 1.676 1.791, 1.715794594594594 1.7835675675675677, 1.7371880040647283 1.7728882728992528, 1.755414722418766 1.7584861946606423, 1.7697324306821693 1.7419033500911634, 1.7821822966428729 1.7193153375833379, 1.7885287581422071 1.699014652677622, 1.7908999998269444 1.6775046880767683, 1.7909999998269444 0.3230046880767684, 1.7862685046962532 0.2923021911868067), (0.691 0.9229754642711925, 0.691 0.7011541640387603, 0.6936627376889104 0.6937321576162595, 0.7020245357288075 0.691, 0.9238458359612397 0.691, 0.9312678423837405 0.6936627376889104, 0.934 0.7020245357288075, 0.934 0.9238458359612397, 0.9313372623110896 0.9312678423837405, 0.9229893209534975 0.9339991155309167, 0.6990442469761068 0.9339012801993407, 0.693329984148253 0.9309041524224672, 0.691 0.9229754642711925), (0.6953392867391299 1.067444033745615, 0.9259557530238928 1.0660987198006593, 0.9315698728030161 1.0689552959301913, 0.9339991155309167 1.0770106790465024, 0.9339012801993407 1.3009557530238929, 0.9315721240202081 1.3060497565109876, 0.9229893209534982 1.3089991155309166, 0.6990442469761072 1.3089012801993407, 0.6934301271969839 1.3060447040698087, 0.691 1.2983866353711833, 0.691 1.0758139687976573, 0.6953392867391299 1.067444033745615), (1.3031380819680736 0.6915341696737235, 1.3089993838262433 0.7013965510439816, 1.3089012068069301 0.9261237482521002, 1.30633726231109 0.93126784238374, 1.2986034489560137 0.9339993838262434, 1.0738762517478988 0.9339012068069299, 1.0687321576162598 0.9313372623110899, 1.0659999999999998 0.923589585046487, 1.0659999999999998 0.7011541640387645, 1.0689552959301913 0.6934301271969839, 1.0770245357288075 0.691, 1.3031380819680736 0.6915341696737235), (1.0690958475775336 1.068329984148252, 1.076410414953513 1.0659999999999998, 1.2991860312023409 1.0659999999999998, 1.3065698728030166 1.0689552959301918, 1.3090000000000002 1.0770245357288104, 1.3090000000000002 1.2988458359612356, 1.3063372623110892 1.306267842383741, 1.2986034489560183 1.3089993838262433, 1.0738762517478997 1.3089012068069301, 1.068732157616259 1.3063372623110892, 1.0660006161737567 1.2986034489560183, 1.0660987931930699 1.0738762517478997, 1.0690958475775336 1.068329984148252))"
        poly = LibGEOS.readgeom(wkt)
        @show "before tri"
        @show LibGEOS.isValid(poly)
        LibGEOS.GEOSConstrainedDelaunayTriangulation_r(LibGEOS._context.ptr, poly.ptr)
        @show "after tri"

the console result is:

julia> @time include("tmp.jl")
"before tri" = "before tri"
LibGEOS.isValid(poly) = true
^C^C^C^CKilled: 9

[dr-jts]

I tried this example in 3.11 and 3.10 using geosop, and it worked correctly in both versions. On an Intel Mac Air.

bin/geosop -a data.wkt -f wkt constrainedDelaunay

So not sure what might be happening in your environment. Is that an M1 machine?

[nraynaud]

@dr-jts thanks for showing me the CLI

sadly my experience match yours:
`$ geosop
geosop - GEOS 3.11.0
Executes GEOS geometry operations
Usage:
geosop [OPTION...] opName opArg

-a arg source for A geometries (WKT, WKB, file, stdin,
stdin.wkb)
-b arg source for B geometries (WKT, WKB, file, stdin,
stdin.wkb)
--alimit arg Limit number of A geometries read
-c, --collect Collect input into single geometry
-e, --explode Explode results into component geometries
-f, --format arg Output format (wkt, wkb or txt)
-h, --help Print help
-p, --precision arg Sets number of decimal places in output coordinates
-r, --repeat arg Repeat operation N times
-t, --time Print execution time
-v, --verbose Verbose output

$ time geosop -a ~/Desktop/tri.wkt constrainedDelaunay

real 0m0.005s
user 0m0.003s
sys 0m0.001s
`

I guess I have more homework to do.

Sorry for the wasted time, I was earnest, I had left really little julia in the equation.

[dr-jts]

As you say, there can't be much Julia in front of GEOS, so this does seem odd. Not sure how to narrow it down more.

[nraynaud]

Sorry for coming back, it seems to be a duplicate of #574
it did not cause any problem in geosop either.

[dr-jts]

Is it possible the GEOS lib being used by Julia does not have the fix for that issue?

[nraynaud]

yes, the PR #575 says "first appeared in 3.11.0beta1" and the version string I have is

julia> LibGEOS.GEOSversion()
"3.10.2-CAPI-1.16.0"

it's a bit late here, in my tomorrow, I'll try to wrap a more recent version.

[dr-jts]

@nraynaud Sounds like this should be closed?

[nraynaud]

I confirm its a duplicate of #574 , bumping the version makes the problem disappear.
Thanks for your nice library.