Voronoi edges example

179 Views Asked by At

I have 4 line segments:

0 0 2 0 // 1st line segment
2 0 2 1 // 2nd line segment
2 1 0 1
0 1 0 0

and I wrote some CGAL code to print the Voronoi edges. However, infinite vertex is being printed for some vertices, as indicated in this example. However, our hw wants the output to be like this:

0 0 -1 0 // here I am printing 0 0 infinite vertex
0 0 0 -1
0 1 -1 1
2 1 3 1
2 0 2 -1
0 1 0.5 0.5
0 1 0 2
2 0 3 0
2 0 1.5 0.5
1.5 0.5 2 1
1.5 0.5 0.5 0.5
2 1 2 2
0 0 0.5 0.5

For example (Each oriented Voronoi edge (horizontal segment in the figure below) is defined by four sites A, B, C and D.), for the 1st edge, I know that the situation looks like this:

       \                     /
        \         B         /
         \                 /
       C  -----------------  D
         /                 \
        /         A         \
       /                     \

where:

A = poiint 0 0
B = line segment 0 1 0 0
C = infinite vertex
D = line segment 0 0 2 0

What should be done (conceptually) for C to be converted in -1 0?


Edit:

  The sites A and B define the (oriented) bisector on which the
  edge lies whereas the sites C and D, along with A and B define
  the two endpoints of the edge. These endpoints are the Voronoi
  vertices of the triples A, B, C and B, A, D.
  If one of these vertices is the vertex at infinity the string
  "infinite vertex" is printed; the corresponding Voronoi edge is
  actually a stright-line or parabolic ray.
1

There are 1 best solutions below

0
On BEST ANSWER

Here's what a correct Voronoi tesselation looks like:

enter image description here