search

CGAL / cgal

The public CGAL repository, see the README below
https://github.com/CGAL/cgal#readme
Other
4.98k stars 1.39k forks source link

Reading Hyperbolic Delaunay Triangulations #6869

Closed maxkatzmann closed 2 years ago

maxkatzmann commented 2 years ago

Issue Details

Hi everyone, thanks for taking the time to look into my issue. I'm trying to use CGAL to compute hyperbolic Delaunay triangulations and am under the impression that I'm doing something wrong as it seems like one edge of the triangulation is not returned.

Here's the instance that I'm interested in. Points A-J are the sites and the remaining points are intersections that I added when drawing the relevant parts of the Voronoi diagram.

To me it looks like E and H are in neighboring Voronoi cells and should therefore be connected by an edge in the Delaunay triangulation. However, the following code yields the edges of the triangulation that I would expect, except for E-H. I tried to follow the CGAL example code for computing hyperbolic Delaunay triangulations in ht2_example.cpp and wonder whether I'm missing something when reading the edges of the triangulation.

Source Code

Source Code CMake File

Here's the output of

cmake -DCMAKE_BUILD_TYPE=Release .
make
./cgal_util

Environment

I hope that the report lists what is expected. If more information is needed, I'm happy to provide it. Thanks again for taking the time!

MaelRL commented 2 years ago

Thanks for the bug report, it'll be fixed in https://github.com/CGAL/cgal/pull/6883.

Screenshot from 2022-09-26 16-49-01

maxkatzmann commented 2 years ago

Thank you very much for the quick response! I'm looking forward to working with the updated code!

lrineau commented 2 years ago

Thank you very much for the quick response! I'm looking forward to working with the updated code!

Thanks @maxkatzmann for your bug report. It is now fixed, in the master branch of CGAL. It will not be backported to any CGAL version 5.5.x, because the fix requires a breaking change of the API (see commit 8a1e8b16ce023f53d33174f94a78f050373bd14f). CGAL-5.6 is planned for June 2023. Meanwhile, you should use CGAL from its master branch.