c++ - Boost Geometry/intersection() 似乎返回不一致的结果

Question

我有一个适用于 Boost Geometry 的 3D vector 作为 2D 点和环:

BOOST_GEOMETRY_REGISTER_POINT_2D(Vector3, float, cs::cartesian, x, y)
BOOST_GEOMETRY_REGISTER_RING( std::vector< Vector3 > )

然后:

1. 画一些非凸多边形(环)
2. 绘制线段，切割非凸多边形并将其一分为二(较小的通常是三角形)
3. 在线段上镜像较小的 2 个新多边形

结果是两个多边形，它们重叠并且有 1 个切边。

然后我检查两个多边形的交点。在 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

可能是什么原因？在调用 intersection() 之前，我尝试在每个多边形上执行 boost::geometry::correct()，但它没有帮助。我的想法用完了

编辑::

我已经测试过使用 Boost Geometry 类型和双存储类型创建新环是否会有所帮助:

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 ) );
    }
    ...
}

我执行了两次 intersection() 调用，分别针对 polyA、polyB(我的初始浮点 Vector3)和 ringA、ringB。然后，出现不一致:

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，因此发生交集(这是用于 ringA/ringB 交集)。 “0”用于 Vector3——空结果。

EDIT2:

使用具有 float 存储类型的 boost 模型会导致 ringA 和 ringB 调用返回不正确的结果。 我已经确认了这一点。我曾经对 double 不会改变错误的“逻辑”感到困惑，但这是因为意外删除了 correct() 调用。使用 correct() 调用和 ringA/ringB 冗余环的双存储类型，我无法获得空交集。

EDIT3:

以下是 intersection() 返回的 5 种情况:

• 前两个环的空结果 (std::vector< Vector3 >)，
• 当第一次创建 std::vector<> 环(使用 boost::geometry 模型)的双类型拷贝时，size() == 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 )

案例二:

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 )

案例三:

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 )

案例五:

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 );
}

Answer 1

我对您输入的分析:

第二个多边形(从 24.57 开始)是逆时针的。第二组的第二个多边形(从 90.61 开始)也是逆时针的。所以一定要调用 boost::geometry::correct。这会有所作为。

因此，如果我使用 geometry::correct，我会得到以下结果:

1) 第一种组合，使用double: intersection area=12.3854, one geometry, 4 points2)第一次组合，使用float:intersection area=12.3854，一个geometry，4个points(相同)这个结果和SQL Server的结果完全一样

3) 第二种组合，使用double: intersection area=34.7862, one geometry, 4 points4)第二种组合，使用 float :交集面积=34.7862，一个几何体，4个点此结果与 SQL Server 的结果相同。

请注意，在这两种情况下，第二个多边形都在第一个多边形内(在第二种情况下不接触，在第一种情况下它接触 - 根据 SQL Server)。

所以所有的输出看起来都是正确的。您提到:“消除空交叉点”，最近在 Boost.Geometry 中已解决。该修复程序尚未在 1.52 中发布，但会在 1.53 中发布。因此，如果这是特定问题，则必须使用 Boost.Trunk 版本。

但是，这不会导致空输出。