Круг пересечения CGAL и вертикальные линии (не сегменты)

В CGAL мне нужно вычислить точную точку пересечения между набором прямых и набором кругов. Исходя из кругов (которые могут иметь иррациональный радиус, но рациональный squared_radius), я должен вычислить вертикальную линию, проходящую через x_extremal_points каждого круга (не сегмент, а линии) и вычислить точку пересечения каждого круга с каждой линией.Круг пересечения CGAL и вертикальные линии (не сегменты)

Я использую CircularKernel и Circle_2 для кругов и Line_2 для линий. Вот пример того, как я вычисляю круги и линии, и как я проверяю, пересекаются ли они.

int main() 
{ 

    Point_2 a = Point_2(250.5, 98.5); 
    Point_2 b = Point_2(156, 139); 

    //Radius is half distance ab 
    Circular_k::FT aRad = CGAL::squared_distance(a, b); 

    Circle_2 circle_a = Circle_2(a, aRad/4); 

    Circular_arc_point_2 a_left_point = CGAL::x_extremal_point(circle_a, false); 
    Circular_arc_point_2 a_right_point = CGAL::x_extremal_point(circle_a, true); 

    //for example use only left extremal point of circle a 
    CGAL::Bbox_2 a_left_point_bb = a_left_point.bbox(); 

    Line_2 a_left_line = Line_2(Point_2(a_left_point_bb.xmin(), a_left_point_bb.ymin()), 
           Point_2(a_left_point_bb.xmin(), a_left_point_bb.ymax())); 

    if (do_intersect(a_left_line, circle_a)) { 
     std::cout << "intersect"; 
    } 
    else { 
     std::cout << " do not intersect "; 
    } 

    return 0; 
}

Этот поток поднимается это исключение:

CGAL error: precondition violation! 
Expression : y != 0 
File  : c:\dev\cgal-4.7\include\cgal\gmp\gmpq_type.h 
Line  : 371 
Explanation: 
Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html

Я не могу понять, как я могу вычислить точки пересечения. Кроме того, есть ли лучший способ вычислить линии? Я знаю функцию x_extremal_point, но возвращает точку Circular_arc_point, и я не могу построить вертикальную линию, проходящую через них напрямую, без использования поля Bounding.

источник

2016-04-08 Cers

Я думаю, вы не можете построить линию из одной точки, это то, что говорится: 'a_left_point_bb' - вырожденный ящик. Что вы хотели сделать? Вертикальная линия через 'a_left_point'? – BeyelerStudios

ой! это вырожденная коробка: /! Да, мне нужна вертикальная линия через a_left_point. Затем мне нужно пересечь его со всеми кружками в наборе (в примере есть только circle_a), чтобы получить все точки interesection. (вид sweepline alg), используя Line_2 (Point_2 (a_left_point_bb.xmin(), a_left_point_bb.ymin()), Point_2 (a_left_point_bb.xmin(), 0)); оно работает. Есть ли лучший способ вычислить его?как получить точки пересечения? – Cers

вы можете вместо этого использовать 'Line_2 (a_left_point, Point_2 (a_left_point.x(), a_left_point.y() + 1))' избегая случая, когда 'a_left_point' имеет значение ay' 0' – BeyelerStudios

В вашем коде вы, кажется, вычисляете пересечение круга с вертикальной линией, проходящей через экстремальную точку круга (я забываю ограничительную рамку). Ну, тогда (двойное) пересечение является самой экстремальной точкой ... Более глобально, вы говорите в своем тексте введения, что вы хотите вычислить точные пересечения. Тогда вы, конечно, не должны использовать ограничивающие прямоугольники, которые по определению вводят некоторое приближение.

Если я правильно понял ваш текст, * для проверки пересечения ваших вертикальных линий с другими кругами, вам не нужно строить линии, вам нужно всего лишь сравнить абсциссы экстремальных точек двух кругов , которые вы можете делать с круговым ядром CGAL. * для вычисления пересечения вертикальной линии с нерациональными коэффициентами (так как ее уравнение имеет вид x = + -sqrt (r)) с другим кругом, то круговое ядро CGAL не даст вам предварительно приготовленную решение. Это ядро поможет, но вы все равно должны вычислить несколько вещей вручную. Если вы не хотите беспокоиться, вы также можете просто взять стандартное ядро CGAL с Core :: Expr в качестве базового типа номера. Он может «ничего», но он будет медленнее.

источник

2016-04-11 09:05:52

. Что мне действительно нужно, это пересечение интервалы (по координате y) между вертикальной линией и каждым кругом. Вертикальные линии вычисляются исходя из экстремальных точек круга (крайнего левого и правого) и точек пересечения между каждой парой кругов. Здесь я раскрываю первый шаг моей процедуры, т. Е. Вычисление вертикальных линий, проходящих через экстремальную точку. Если с ограничивающей рамкой я теряю точность, как я могу получить вертикальную линию, проходящую через Circular_arc_point_2 a_left_point? спасибо – Cers

Эта вертикальная линия имеет уравнение x = x_a_left_point. Если вам нужны диапазоны y, то, как я уже сказал, вы можете вычислить все, что вам нужно, с (стандартным) ядром CGAL (например, CGAL :: Cartesian) с Core :: Expr. –

и x_a_left_point = x_a + - sqrt (r_a). Это позволяет вам построить строку, см. Строку Line_2 в ядре CGAL. –

Для повышения эффективности вы должны рассмотреть лежащую в основе проблему 1D: проецируя линии и круг по оси X, у вас есть набор точек и набор интервалов [Xc-R, Xc + R].

Если точки L больше отсортированы, вы можете найти левую границу интервала времени Lg (L) с помощью дихотомии и отсканировать список точек до правой границы. Это приводит к поведению O (Lg (L) .C + I) (интервалы окружности C), где I - количество сообщенных пересечений.

Я предполагаю, что с помощью процесса слияния с использованием активного списка, если границы интервалов также отсортированы, вы можете опускать до O (L + C + I).

Расширение 2D является элементарным.

источник

2016-04-11 14:05:15

Круг пересечения CGAL и вертикальные линии (не сегменты)

ответ

Смежные вопросы