[BUG]: clipping when getting polygon from Voronoi tessellation hangs for certain configurations

[rubenseyer]

Describe the bug

I want to perform a Voronoi tessellation of a periodic window, but I'm solving this by making mirror copies of points where necessary and then clipping my polygons to the original bounding box. Thus, in an edge case, the resulting set of points can lie on a triangle (up to floating point precision). Some of these configurations seem to hang for me when attempting to get the clipped polygons.

Reproducer

using DelaunayTriangulation
using Random: seed!

seed!(123) # randomness is not relevant here, but just to be sure
pts = [(0.1,0.2), (1.1,0.2), (0.1,1.2)]
D = triangulate(pts)
V = voronoi(D)
bbox = (0., 1., 0., 1.)
get_polygon_coordinates(V, 3, bbox)  # hangs

I expect to obtain the clipped polygons rather than the code hanging.

Environment information

Julia Version 1.10.2
Commit bd47eca2c8a (2024-03-01 10:14 UTC)
Build Info:
  Official https://julialang.org/ release
Platform Info:
  OS: Linux (x86_64-linux-gnu)
  CPU: 12 × 12th Gen Intel(R) Core(TM) i5-1245U
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-15.0.7 (ORCJIT, alderlake)
Threads: 1 default, 0 interactive, 1 GC (on 12 virtual cores)
Environment:
  JULIA_EDITOR = code
  JULIA_NUM_THREADS = 

Status `~/xyz/Project.toml`
  [927a84f5] DelaunayTriangulation v1.6.0

[DanielVandH]

Thanks for the report. Away from the computer but can you check to see what DelaunayTriangulation.validate_triangulation(tri) returns for that triangulation? (D being tri in your case)

…

On Fri, 18 Oct 2024, 3:02 pm Ruben Seyer, ***@***.***> wrote: *Describe the bug* I want to perform a Voronoi tessellation of a periodic window, but I'm solving this by making mirror copies of points where necessary and then clipping my polygons to the original bounding box. Thus, in an edge case, the resulting set of points can lie on a triangle (up to floating point precision). Some of these configurations seem to hang for me when attempting to get the clipped polygons. *Reproducer* using DelaunayTriangulationusing Random: seed! seed!(123) # randomness is not relevant here, but just to be sure pts = [(0.1,0.2), (1.1,0.2), (0.1,1.2)] D = triangulate(pts) V = voronoi(D) bbox = (0., 1., 0., 1.)get_polygon_coordinates(V, 3, bbox) # hangs I expect to obtain the clipped polygons rather than the code hanging. *Environment information* Julia Version 1.10.2 Commit bd47eca2c8a (2024-03-01 10:14 UTC) Build Info: Official https://julialang.org/ release Platform Info: OS: Linux (x86_64-linux-gnu) CPU: 12 × 12th Gen Intel(R) Core(TM) i5-1245U WORD_SIZE: 64 LIBM: libopenlibm LLVM: libLLVM-15.0.7 (ORCJIT, alderlake) Threads: 1 default, 0 interactive, 1 GC (on 12 virtual cores) Environment: JULIA_EDITOR = code JULIA_NUM_THREADS = Status `~/xyz/Project.toml` [927a84f5] DelaunayTriangulation v1.6.0 — Reply to this email directly, view it on GitHub <#206>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AWZPH4APRAFMKS4TDNWVONTZ4EIFTAVCNFSM6AAAAABQGAZNJKVHI2DSMVQWIX3LMV43ASLTON2WKOZSGU4TONRQGYZTONY> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[DanielVandH]

Can you try #207 and see if it fixes your use case? Your MWE works now

   Random.seed!(123)
    pts = [(0.1, 0.2), (1.1, 0.2), (0.1, 1.7)]
    tri = triangulate(pts)
    vorn = voronoi(tri, clip=true, clip_polygon=(
        [(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0)], [1, 2, 3, 4, 1]
 ))

but I'm not 100% sure about in general depending on what triangles you're encountering.

[rubenseyer]

Thanks for the quick response (and sorry I didn't run that in time for you earlier)!
You correctly inferred that I meant a (possibly up to numerics) right triangle 😅
I stress-tested your fix with the outer generating code and it doesn't hang any more for me, so I consider this fixed for my purposes. Now I just have to convince Makie to bump their compat bounds from 1.0 so I can actually install the new version in the rest of the environment.

[DanielVandH]

Great! I will make a new release with the fix.

Now I just have to convince Makie to bump their compat bounds from 1.0 so I can actually install the new version in the rest of the environment.

It should be all up to date on Makie's side as well. You probably have an outdated environment (use ]st --outdated to see what might be holding it back).

Unless you mean that 1.0 is making v1.6.1 of this package not able to be installed? That shouldn't be how it works - 1.0 means any versions in [1.0, 2.0) (i.e. just excluding 2.0).