CGAL: Почему полуплоскость представлена ​​шестью лучами? - PullRequest
Новая
       76

CGAL: Почему полуплоскость представлена ​​шестью лучами?

1 голос
/ 16 июня 2020

Я только начал играть с многогранниками Нефа на плоскости - простая программа ниже создает полуплоскость, определяемую линией 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

Почему эти шесть лучей?

Ответы [ 2 ]

2 голосов
/ 16 июня 2020

Из документации для explorer:

Путем рекурсивного составления двоичных и унарных операций можно получить очень сложную прямолинейную структуру. Для исследования этой структуры существует тип данных Nef_polyhedron_2 :: Explorer, который позволяет исследовать прямолинейную структуру только для чтения. происхождение нашей системы координат. Коробка обрезает все структуры, простирающиеся до бесконечности. У линий и лучей есть символы c конечных точек на прямоугольнике. Лица закрыты по кругу. Infimaximal здесь означает, что его геометрическая c протяженность всегда достаточно велика (но конечна для нашей интуиции). Предположим, вы приближаетесь к коробке с аффинной точкой, тогда эта точка всегда находится внутри коробки. То же самое и с прямыми линиями; они всегда пересекают прямоугольник.

Предполагая, что эти вершины находятся на прямоугольнике, я могу предположить следующее: диаграмма

Это квадрат, поэтому вы получаете диагональные лучи, такие как 0, 0 -> -1, 1 и 0, 0 -> 1, 1. Хотя я не эксперт.

Редактировать: рисунок перевернут, полуплоскость y >= 0, а не y <= 0.

0 голосов
/ 20 июня 2020

Я отвечаю на свой вопрос. Согласно этим пояснениям из онлайн-руководства 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)

Также см. Рисунок 17.3 из онлайн-руководства CGAL. ​​

...