CGAL: пересечение отрезка и многоугольника?

У меня есть набор многоугольников, и я хочу проверить пересечение между ним и сегментом. Я проверил руководство, но не могу найти подходящую функцию. Пересечения между точками, линиями, отрезками, треугольниками, плоскостями действительно существуют. И пересечение полигонов тоже есть. У меня вопрос:

  1. Есть такая функция?
  2. Если нет, значит ли это, что мне нужно разбить многоугольники на сегменты и сделать пересечение между этими сегментами? (Причина, по которой я не хочу этого делать, состоит в том, что я думал, что CGAL на самом деле может использовать этот способ для пересечения многоугольников. Почему нет такой функции для пересечения линии и многоугольника?) Или есть что-то лучше способ сделать это?

cgal computational-geometry
person Ivan Xiao    schedule 01.07.2011    source источник

Ответы (1)


arrow_upward
6
arrow_downward

Самый простой способ - создать объект Polygon_set_2, который может содержать несколько многоугольников. Чтобы проверить пересечение внешнего многоугольника с помощью этого набора, вы просто применяете метод do_intersect.

Например:

typedef CGAL::Polygon_set_2<Kernel, std::vector<Kernel::Point_2>> Polygon_set_2;
Polygon_set_2 ps;
Polygon_2     poly;
Polygon_2     line; // line is a polygon defined by 2 points

ps.insert(poly);
bool intersect = ps.do_intersect(line);

Подробнее о polygon_set_2:

Надеюсь понятно, Кирилл

person kirilsolo    schedule 24.07.2011
comment
Ой, я не понимал, что многоугольник может содержать только две точки. Кажется работает! - person Ivan Xiao; 25.07.2011
comment
это ps.insert (poly); ps.insert (строка); ? - person sabbir; 16.06.2015
comment
Я получаю эту ошибку: Пояснение: Сама граница многоугольника перекрывается. - person sabbir; 22.06.2015
comment
Это не работает для меня. Ошибка для меня - линия Polygon_2; имеет только два очка. Там написано. Пояснение: граница многоугольника перекрывается. Как только я добавляю к этой строке третью точку, все работает. ЛЮБОЕ РЕШЕНИЕ ???? - person sabbir; 22.06.2015
comment
Да, с CGAL 4.7 это точно не работает. вызов do_intersect() с использованием многоугольника только с двумя точками завершается ошибкой с сообщением о том, что граница многоугольника перекрывается. и Многоугольник не простой. - person drewish; 02.04.2016
comment
Polygon_set_2 работает с многоугольниками с дырками? Например, добавьте прямоугольник (без отверстий, хранящихся в Polygon_with_holes) и добавьте вторые прямоугольники (без пересечений). Как это сделать? Как проверить is_simple многоугольники с отверстиями и как проверить ориентацию - person Eliasz Łukasz; 13.11.2017
comment
Любое решение для этого? - person huddie96; 24.05.2019
comment
Я решил эту проблему, перебирая края многоугольника и пересекая каждое ребро само по себе. Это медленно и не работает с сегментом, полностью содержащимся в многоугольнике, но в моем случае это сработало. - person madlaina; 21.08.2020