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

在您的代码中，您似乎计算了一个圆与通过该圆的极值点的垂直线的交点(我忘记了边界框)。好吧，那么(双)交叉点本身就是极值点。更广泛地说，你在引言文本中说你想要计算精确的交叉点。那么你当然不应该使用边界框，因为根据定义它引入了一些近似值。

如果我没理解错的话，*为了测试垂直线与其他圆的交集，你不需要构造这些线，你只需要比较两个圆的极值点的横切，这可以用CGAL循环内核来做。*为了计算一条具有无理系数的垂直线与另一个圆的交集(因为它的方程的形式是x= +-sqrt(r))，那么CGAL循环内核将不会给你一个预先煮熟的解决方案。内核将会有所帮助，但您仍然需要手动计算一些东西。如果您不想麻烦，那么您也可以只使用Core::Expr作为底层number类型的标准CGAL内核。它可以做“任何事”，但它会更慢。

Answer 2

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

如果对L个点进行递增排序，则可以通过二分法定位时间Lg(L)中某一区间的左界，并扫描点列表直到右界。这将导致O(Lg(L).C + I)行为(C圆间隔)，其中i是报告的交叉点数量。

我猜想，对于使用活动列表的类似合并的过程，如果间隔界限也是排序的，那么您可以将其降低到O(L +C+ I)。

对2D的扩展是基本的。