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

Question

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

Я использую 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, и я не могу построить вертикальную линию, проходящую через них напрямую, без использования ограничительной рамки.

Answer 1

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

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

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

Расширение до 2D элементарно.

Answer 2

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

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