CGAL: Why is halfplane represented by six rays?

user_2961540 0
Viewed 68

I've just started playing with Nef polyhedrons on the plane - the simple program below creates a halfplane, defined by a line y=0, and then this halfplane is explored by the CGAL Explorer.

#include <iostream>

#include <CGAL/Exact_integer.h>
#include <CGAL/Extended_cartesian.h>
#include <CGAL/Nef_polyhedron_2.h>

using Kernel = CGAL::Extended_cartesian<CGAL::Exact_integer>;
using Polyhedron = CGAL::Nef_polyhedron_2<Kernel>;
using Line = Polyhedron::Line;

using std::cout;
using std::endl;

int main()
{
  const Polyhedron p(Line(0, 1, 0), Polyhedron::INCLUDED);  
  const auto ex = p.explorer();
  for (auto it = ex.vertices_begin(); it != ex.vertices_end(); ++it)
  {
    if (ex.is_standard(it))
    {
      cout << "Point: " << ex.point(it) << endl;
    }
    else
    {
      cout << "Ray:   " << ex.ray(it) << endl;
    }
  }
}

The program output:

Ray:   0 0 -1 -1
Ray:   0 0 -1 0
Ray:   0 0 -1 1
Ray:   0 0 1 -1
Ray:   0 0 1 0
Ray:   0 0 1 1

Why these six rays?

cgal computational-geometry c++
2 Answers

From the documentation for the explorer:

By recursively composing binary and unary operations one can end with a very complex rectilinear structure. To explore that structure there is a data type Nef_polyhedron_2::Explorer that allows read-only exploration of the rectilinear structure.

Therefore the planar subdivision is bounded symbolically by an axis-parallel square box of infimaximal size centered at the origin of our coordinate system. All structures extending to infinity are pruned by the box. Lines and rays have symbolic endpoints on the box. Faces are circularly closed. Infimaximal here means that its geometric extend is always large enough (but finite for our intuition). Assume you approach the box with an affine point, then this point is always inside the box. The same holds for straight lines; they always intersect the box.

Assuming that these vertices are on the box, my best guess is this: diagram

It's a square, so that's why you get the diagonal rays like 0, 0 -> -1, 1 and 0, 0 -> 1, 1. I'm not an expert though.

Edit: drawing is upside-down, the halfplane is y >= 0, not y <= 0.

user_88873130

I'm answering my own question. According to these explanations from the CGAL online manual, each 2D polyhedron is bounded by an infinitely large frame, which is represented by four infinitely remoted vertices. These boundary vertices have extended coordinates (+infinity, +infinity), (+infinity, -infinity), (-infinity, +infinity) and (-infinity, -infinity). Such non-standard vertices in CGAL are represented by rays - for example, the point (+infinity, -infinity) is stored as a ray with beginning in the origin (0,0) and direction (1,-1).

So, a polyhedron, consisting of the single halfplane y>0, will have six non-standard vertices - four ones will belong to the frame, plus two ones, describing the line y=0. All its faces will look like this:

face 0, marked by 0
* no outer face cycle

face 1, marked by 0
* outer face cycle:
frame halfedge:    (0 0 -1 0) => (0 0 -1 -1)
frame halfedge:    (0 0 -1 -1) => (0 0 1 -1)
frame halfedge:    (0 0 1 -1) => (0 0 1 0)
internal halfedge: (0 0 1 0) => (0 0 -1 0)

face 2, marked by 1
* outer face cycle:
frame halfedge:    (0 0 -1 1) => (0 0 -1 0)
internal halfedge: (0 0 -1 0) => (0 0 1 0)
frame halfedge:    (0 0 1 0) => (0 0 1 1)
frame halfedge:    (0 0 1 1) => (0 0 -1 1)

Also please see the Figure 17.3 from the CGAL online manual.

user_29615400
Related