CGAL交点圆和垂直线(不是线段)

Question

在CGAL中，我需要计算一组直线和一组圆之间的精确交点。从圆（可以有无理半径，但可以有有理平方半径）开始，我应该计算通过每个圆的x_extremel_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:devcgal-4.7includecgalgmpgmpq_type.h
 Line       : 371
 Explanation:
 Refer to the bug-reporting instructions at http://www.cgal.org/bug_report.html

我想不出如何计算交点。还有，有没有更好的方法来计算线条？我知道x_extremel_point函数，但它返回Circular_arc_point点，如果不使用Bounding box，我无法构造直接穿过它们的垂直线。

Answer 1

在您的代码中，您似乎要计算一个圆与穿过该圆极值点的垂直线的交点（我忘记了边界框）。那么（双）交点就是极值点本身。。。更全局地说，你在引言中说，你想计算精确的交集。那么，您当然不应该使用边界框，因为根据定义，边界框会引入一些近似值。

如果我正确理解你的文字，*为了测试你的垂直线与其他圆的交点，你不需要构造线，你只需要比较两个圆的极值点的横坐标，这可以用CGAL圆核来完成。*对于计算具有非有理系数的垂直线（因为其方程的形式为x=+-sqrt（r））与另一个圆的交点，那么CGAL圆核不会给你一个预先准备好的解。这个内核会有所帮助，但您仍然必须手工计算一些东西。如果你不想麻烦，那么你也可以使用一个标准的CGAL内核，将Core:：Expr作为底层的数字类型。它可以做"任何事情"，但速度会慢一些。

Answer 2

为了提高效率，您应该研究潜在的1D问题：将直线和圆投影到X轴上，您有一组点和一组间隔[Xc-R，Xc+R]。

如果L点的排序越来越多，则可以通过二分法定位时间间隔Lg（L）的左边界，并扫描点列表直到右边界。这导致O（Lg（L）.C+I）行为（C圆区间），其中I是报告的交叉点数量。

我想，对于使用活动列表的类似合并的过程，如果区间边界也被排序，你可以降到O（L+C+I）。

对2D的扩展是基本的。