2016-08-15 8 views
1

Я пытаюсь использовать CGAL, чтобы узнать «все точки пересечения» и «пересеченные сегменты для каждой точки пересечения» из списка сегментов в 2D. Я хочу использовать алгоритм Бентли-Оттмана по некоторым причинам. Библиотека CGAL имеет C++ реализацию этого алгоритма под названием Sweepline 2, но с этим я могу найти только точки пересечения. Существует ли какая-либо другая реализация в CGAL? или как я могу решить эту проблему?Найти точку пересечения сегментов и список пересекающихся сегментов для каждой точки пересечения

ответ

0

Edit: Действительно быстро исправить бы просто создать все точки пересечения с использованием развертки по линии 2, цикл через все сгенерированных точек пересечения, и для каждой точки записи пересечения обе координаты оборудования точки и все отрезки, которые содержат, что укажите структуру по вашему выбору.


Быстрое решение (хотя и не самый эффективный) заключается в следующем:

//Probably start off with a struct to store your information 
struct intersection{ 
    //This stores the x and y position of the intersection. 
    int[2] xyCoords; 
    //This stores the segment ids or indexes of the intersection line segments. 
    //For example, if the 1st and 5th line segment intersect, you would store 1 and 5 in here. 
    int[2] segmentIDs; 
} 

Тогда просто создать вектор пересечения структуры, так что вы можете хранить все ваши различных пересечений.

vector<intersection> intersectionVector; 

Тогда просто перебрать все сегменты линии вы имеете в нечто похожее на следующее:

for (int i = 0; i < numSegments; i++){ 
    for (int j = 0; j < numSegments; j++){ 
     //Don't look at the same points.   
     if (i == j) 
      continue; 
     //See below for pseudocode for this part. 
    } 
} 

Теперь, чтобы заполнить в этом блоке, вместо того, чтобы изобретать что-либо просто сослаться на How do you detect where two line segments intersect?.

Как показано в приведенной выше ссылке, вычислите значения r × s и (q-p) × r, где × - векторное поперечное произведение. Оттуда просто используйте if/else блоки для учета четырех случаев (ctrl f для «Теперь есть четыре случая:»), если вы заботитесь о деталях. Если вам просто нужно то, что вы указали в своем вопросе, просто проверьте правильность случая 3. Если он действителен, сохраните индексы ваших сегментов линии, а также координаты x и y в структуре vector/whatever, которую вы используете ,

Единственная дополнительная вещь, которую вам нужно сделать, это использовать вычисление u и применить его к вашему сегменту второй линии из двух проверяемых вами, чтобы сохранить координаты x y пересечения.