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

Question

我刚开始在平面上玩 Nef 多面体 - 下面的简单程序创建了一个半平面，由一条线 y=0 定义，然后 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;
    }
  }
}

程序输出：

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

从 documentation 到 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.

假设这些顶点在盒子上，我最好的猜测是：

它是一个正方形，所以这就是为什么你会得到像 0, 0 -> -1, 1 和 0, 0 -> 1, 1 这样的对角线的原因。不过我不是专家。

编辑：绘图是颠倒的，半平面是 y >= 0，而不是 y <= 0。

Answer 2

我正在回答我自己的问题。根据 CGAL 在线手册的 these 解释，每个 2D 多面体都由一个无限大的 frame 包围，由四个无限远的顶点表示。这些边界顶点有扩展坐标(+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。

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

CGAL: Why is halfplane represented by six rays?

c++

computational-geometry

cgal