CGAL：为什么半平面用六条射线表示？

Question

我刚刚开始玩平面上的Nef多面体--下面这个简单的程序创建了一个半平面，由一条线来定义 y=0，然后由CGAL资源管理器对这个半平面进行探索。

#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;
    }
  }
}

程序输出。

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

为什么会有这六条射线？

Answer 1

从 文件 对于 explorer:

通过递归组合二元和一元运算，我们可以得到一个非常复杂的直线结构，为了探索这个结构，有一个数据类型Nef_polyhedron_2::Explorer允许只读的探索直线结构。为了探索这个结构，有一个数据类型Nef_polyhedron_2::Explorer，它允许对直线结构进行只读探索。

因此，平面细分是由一个以坐标系原点为中心的、大小为infimaximal的轴平行方块符号化地限定的。所有延伸到无穷大的结构都被这个盒子修剪掉了。线和射线的符号端点都在盒子上。面是圆形封闭的。这里的Infimaximal意味着它的几何延伸总是足够大（但对于我们的直觉来说是有限的）。假设你用一个非线性点接近盒子，那么这个点总是在盒子里面。直线也是如此，它们总是与盒子相交。

假设这些顶点在盒子上，我的最佳猜测是这样的。

这是一个正方形 所以你才会得到这样的对角线： 0, 0 -> -1, 1 和 0, 0 -> 1, 1. 不过我不是专家。

编辑：图纸是倒立的，半平面是 y >= 0，不 y <= 0.

Answer 2

我在回答我自己的问题。根据... 这些 从CGAL在线手册的解释来看，每个二维多面体都是由一个无限大的二维多面体所限定的。框，它由四个无限重构的顶点表示。这些边界顶点有 延长 坐标 (+infinity, +infinity), (+infinity, -infinity), (-infinity, +infinity) 和 (-infinity, -infinity). 这种 非标准 CGAL中的顶点用 射线 - 例如，点 (+infinity, -infinity) 以射线的形式存储，其起始点为原点 (0,0) 和方向 (1,-1).

所以，一个多面体，由单半面组成的 y>0，将有六个非标准顶点--四个顶点属于框架，加上两个顶点，描述线 y=0. 它的所有面都会是这样的。

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)

另外请看CGAL在线手册中的图17.3。