Search code examples
c++cgalvoronoi

CGAL::Voronoi_diagram_2 rounding to integers incorrectly


I am attempting to create a Voronoi diagram from line segments with the following code.

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Segment_Delaunay_graph_Linf_filtered_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_Linf_2.h>
#include <CGAL/Voronoi_diagram_2.h>
#include <CGAL/Segment_Delaunay_graph_adaptation_traits_2.h>
#include <CGAL/Segment_Delaunay_graph_adaptation_policies_2.h>

using Traits=CGAL::Segment_Delaunay_graph_Linf_filtered_traits_2<CGAL::Exact_predicates_inexact_constructions_kernel>;
using DelaunayGraph=CGAL::Segment_Delaunay_graph_Linf_2<Traits>;
using AdaptationTraits=CGAL::Segment_Delaunay_graph_adaptation_traits_2<DelaunayGraph>;
using AdaptationPolicy=CGAL::Segment_Delaunay_graph_degeneracy_removal_policy_2<DelaunayGraph>;
using VoronoiDiagram=CGAL::Voronoi_diagram_2<DelaunayGraph,AdaptationTraits,AdaptationPolicy>;
using VoronoiSite=AdaptationTraits::Site_2;
using VoronoiPoint=VoronoiSite::Point_2;

int main(int argc, char** argv)
{
  VoronoiDiagram vd;

  VoronoiPoint pt0(0.0, 0.0), pt1(5.0, 0.0), pt2(2.0, 2.0), pt3(4.0, 4.0);

  vd.insert(VoronoiSite::construct_site_2(pt0, pt1));
  vd.insert(VoronoiSite::construct_site_2(pt2, pt3));

  int c = 0;
  for (auto it = vd.edges_begin(); it != vd.edges_end(); it++)
  {
    std::cout << "Edge #" << c++ << std::endl;
    if (it->has_source())
        std::cout << "\t" << it->source()->point();
    else
        std::cout << "\tInfinity";
    std::cout << std::endl;
    if (it->has_target())
        std::cout << "\t" << it->target()->point();
    else
        std::cout << "\tInfinity";
    std::cout << std::endl;
  }
  return 0;
}

The output starts with

Edge #0
    0 2
    Infinity
Edge #1
    6 2
    Infinity
Edge #2
    5 1.66667
    Infinity
...

This is my custom visualization of what it looks like.

I expect Edge #1 to be the edge that is equidistant to (4, 4) and (5, 0), however the point (6, 2) is NOT equidistant to those two points. I expect that point to be roughly (5.7, 2.3).

Based on edge 2, I know that ALL the numbers are not integers, but it seems like some of them are being rounded or something. To be clear, I very likely lack some very basic CGAL/Kernel knowledge. I tried swapping in the Cartesian<double> kernel, but that did not change the result.


Solution

  • To follow up on Marc's comment, I needed to change the definitions at the top. The result that works is

    #include <iostream>
    #include <CGAL/Simple_cartesian.h>
    #include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
    #include <CGAL/Segment_Delaunay_graph_2.h>
    #include <CGAL/Voronoi_diagram_2.h>
    #include <CGAL/Segment_Delaunay_graph_adaptation_traits_2.h>
    #include <CGAL/Segment_Delaunay_graph_adaptation_policies_2.h>
    
    using CartesianKernel=CGAL::Simple_cartesian<double>;
    using Traits=CGAL::Segment_Delaunay_graph_filtered_traits_2<CartesianKernel,CGAL::Field_with_sqrt_tag>;
    using DelaunayGraph=CGAL::Segment_Delaunay_graph_2<Traits>;
    using AdaptationTraits=CGAL::Segment_Delaunay_graph_adaptation_traits_2<DelaunayGraph>;
    using AdaptationPolicy=CGAL::Segment_Delaunay_graph_degeneracy_removal_policy_2<DelaunayGraph>;
    using VoronoiDiagram=CGAL::Voronoi_diagram_2<DelaunayGraph,AdaptationTraits,AdaptationPolicy>;
    using VoronoiSite=AdaptationTraits::Site_2;
    using VoronoiPoint=VoronoiSite::Point_2;