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 

私は交点を計算することができる方法を見つけ出すことはできません。 また、線を計算する良い方法はありますか？私はabotをx_extremal_point関数が知っているがCircular_arc_pointポイントを返し、私は垂直線を構築することはできません直接それらを通過するバウンディングボックスを使用せずに。

Answer 1

あなたのコードでは、円の極点を通る垂線と円の交点を計算しているようです（私は境界ボックスを忘れてしまいます）。さて、（二重）交差点は極端なポイントそのものです... よりグローバルに、導入テキストに正確な交差点を計算したいと言います。定義には近似を導入するバウンディングボックスは使用しないでください。

私が正しくあなたのテキストを理解している場合、 *あなたの垂直線と他の円との交差点をテストするには、線を構築する必要はありません。2つの円の極点の横座標これはCGAL循環カーネルで行うことができます。 *非有理係数を持つ垂線の交点を計算するには（その方程式はx = + -sqrt（r）の形式である）、別の円とすると、CGAL循環カーネルはあらかじめ調理済み溶液。そのカーネルは助けになりますが、手でいくつか計算する必要があります。 気にしたくない場合は、Core :: Exprを基にした数値型の標準CGALカーネルを使用することもできます。それは「何か」をすることができますが、遅くなります。

Answer 2

効率を上げるためには、線と円をX軸に投影すると、1組の点と1組の区間[Xc-R、Xc + R]があります。

L点がますますソートされる場合、二分法で時間Lg（L）の区間の左境界を特定し、右境界まで点のリストをスキャンすることができます。この結果、O（Lg（L）.C + I）の動作（Cの円間隔）が得られます。ここで、Iは報告された交点の数です。

アクティブリストを使用したマージのようなプロセスでは、区間の境界もソートされていれば、O（L + C + I）に下げることができます。

2Dへの拡張は基本です。