Boost Geometry に 2D ポイントおよびリングとして適用された 3D ベクトルがあります。
BOOST_GEOMETRY_REGISTER_POINT_2D(Vector3, float, cs::cartesian, x, y)
BOOST_GEOMETRY_REGISTER_RING( std::vector< Vector3 > )
それで：
- いくつかの非凸多角形を描画します ( ring )
- 非凸多角形を切断して2つに分割する線分を描きます（小さい方はほとんどの場合三角形になります）
- 新しい 2 つのポリゴンの小さい方を線分にミラーリングします。
その結果、2 つのポリゴンが重なり合い、接線エッジが 1 つあります。
次に、2 つのポリゴンの交差を確認します。15% のケースでは、交差の結果は空です。これは驚くべきことです (小さい方のポリゴンの面積は 1.0f..10.f になる可能性があるため、コーナー ケースではありません)。
std::deque< Polygon > output;
bg::intersection(bigger_Polygon, mirrored_over_cutting_lineseg_Polygon, output);
// output.size() == 0 in 15% of cases
その理由は何ですか？交差点（）を呼び出す前に、各ポリゴンでboost::geometry::correct()を実行しようとしましたが、役に立ちませんでした。アイデアが尽きた
編集：：
Boost Geometry タイプと double storage タイプを使用して新しいリングを作成すると役立つかどうかをテストしました。
void my_intersection( std::vector<Vector3>& polyA, std::vector<Vector3>& polyB, std::deque< ... > & output ) {
typedef bg::model::d2::point_xy<double> point_type;
bg::model::ring< point_type > ringA;
bg::model::ring< point_type > ringB;
for( int i = 0; i < (int) polyA.size(); i ++ ) {
bg::append( ringA, bg::make< point_type >( polyA[i].x, polyA[i].y ) );
}
for( int i = 0; i < (int) polyB.size(); i ++ ) {
bg::append( ringB, bg::make< point_type >( polyB[i].x, polyB[i].y ) );
}
...
}
polyA と polyB (最初の float Vector3) と ringA と ringB に対して、intersection() 呼び出しを 2 回行います。次に、不一致が表示されます。
A[6]( 58.20822143554688 100.0000076293945 , 89.18041229248047 100.0000076293945 , 100.0000076293945 93.08255767822266 , 100 80 , 64.98564147949219 80 , 58.20822143554688 100.0000076293945 )
B[4]( 89.18040466308594 100 , 100 93.08255004882812 , 93.72125244140625 90.17939758300781 , 89.18040466308594 100 )
INFO: ------ 1 vs 0 ------ INCONSISTENCY
「1」は、出力両端キューの size() == 1 であるため、交差が発生することを意味します (これはリング A/リング B 交差の場合です)。「0」は Vector3 の場合です -- 結果は空です。
EDIT2：
floatストレージ タイプでブースト モデルを使用すると、ringA および ringB 呼び出しに対しても正しくない結果が返されます。私はこれを確認しました。double がエラーの「ロジック」を変更しないことに混乱したことがありますが、それは correct() 呼び出しを誤って削除したためです。正しい()呼び出しとリングA/リングB冗長リングの二重ストレージタイプでは、空の交差点を取得できませんでした。
EDIT3：
ここでは、intersection() が返す 5 つのケースを示します。
- 最初の 2 つのリングの空の結果 (std::vector< Vector3 >)、
- 最初に std::vector<> リングの double 型のコピーを作成するときの size() == 1 の正しい結果 (boost::geometry モデルを使用)。
ケース 1:
A[6]( 58.20822143554688 100.0000076293945 , 89.18041229248047 100.0000076293945 , 100.0000076293945 93.08255767822266 , 100 80 , 64.98564147949219 80 , 58.20822143554688 100.0000076293945 )
B[4]( 89.18040466308594 100 , 100 93.08255004882812 , 93.72125244140625 90.17939758300781 , 89.18040466308594 100 )
ケース 2:
A[10]( 0 100 , 66.90238189697266 99.99999237060547 , 70.97279357910156 80 , 40 80 , 40 60 , 28.31221580505371 60 , 20 67.16078948974609 , 20 80 , 0 80 , 0 100 )
B[4]( 28.31221961975098 60.00000381469727 , 20.00000762939453 67.16079711914062 , 27.08192825317383 68.22066497802734 , 28.31221961975098 60.00000381469727 )
ケース 3:
A[10]( 0 100 , 72.89675903320312 100 , 73.80842590332031 80 , 40 80 , 40 60 , 26.65167617797852 60 , 20 65.58068084716797 , 20 80 , 0 80 , 0 100 )
B[4]( 26.65167999267578 60.00000381469727 , 20.00000381469727 65.5806884765625 , 25.49577522277832 66.55047607421875 , 26.65167999267578 60.00000381469727 )
ケース 4:
A[6]( 47.28099060058594 99.99999237060547 , 95.71660614013672 100 , 100 97.21295166015625 , 100 80 , 68.72442626953125 80.00000762939453 , 47.28099060058594 99.99999237060547 )
B[4]( 95.71659851074219 99.99999237060547 , 99.99998474121094 97.21293640136719 , 97.45189666748047 96.08384704589844 , 95.71659851074219 99.99999237060547 )
ケース 5:
A[6]( 57.69097518920898 100 , 91.16551208496094 100 , 99.99999237060547 92.9193115234375 , 100 80 , 64.8609619140625 80 , 57.69097518920898 100 )
B[4]( 91.16550445556641 99.99999237060547 , 99.99998474121094 92.9193115234375 , 93.08920288085938 91.37748718261719 , 91.16550445556641 99.99999237060547 )
EDIT4：
これは、交差線 (x0,y0)-(x1,y1) でポリゴンをミラーリングするために使用する関数です。正接エッジはこの関数を使用して作成されます。ミラーリング後、ポイントは同じ場所に着地します。
Vector3 mirror_point( Vector3 p, float x0, float y0, float x1, float y1 ) {
float dx = x1 - x0;
float dy = y1 - y0;
float a = ( dx * dx - dy * dy ) / ( dx * dx + dy * dy );
float b = 2.0f * dx * dy / ( dx * dx + dy * dy );
float x2 = a * ( p.x - x0 ) + b * ( p.y - y0 ) + x0;
float y2 = b * ( p.x - x0 ) - a * ( p.y - y0 ) + y0;
return Vector3( x2, y2, p.z );
}