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