首页 文章

使用GPC或Clipper计算多边形交叉区域

提问于
浏览 次
1

我有一个二维粒子系统，其中粒子表示为椭圆 . 我需要计算椭圆 - 椭圆重叠区域，但这是一个难以分析的问题Ellipse-Ellipse Overlap . 我现在将我的省略号表示为20-gons，因此它们是"polygonized"并且我使用 Boost.Geometry 进行必要的计算 .

但是，很多时候，我从 Boost.Geometry ： boost.geometry overlay invalid input exception 得到一个例外 . 我搜索并发现这是 boost.Geometry 的已知错误，并且从版本1.53开始没有修复 . 即使是关于即将发布的v1.54的文档也没有说明解决这个问题 .

我偶然发现了Clipper和GPC - General Polygon Clipper Library . 它们似乎做我想要的，但它们只输出布尔结果 . 有谁知道是否有办法输出这些库的计算交叉点的面积？我想由于交叉点作为某种多边形存储在内存中，我可以使用三角测量或其他方法来计算区域 . 任何指针都会非常感激！

在Linux Mint 14下的Win7 x64，MinGW和Qt 4.8.1下，MSVC 2010和2012中的 Boost overlay 异常是一致的 .

c++ geometry polygons boost-geometry

3 回答

  • 0

    您可以将票证提交到Boost票务系统吗？包括给出无效输入异常的几何对的样本？该错误可能有多种原因，或者它确实无效，或者它是库中的错误 . 其中一些问题每1.54修正一次 .

    回复于
  • 0

    看来你对Clipper和GPC的错误“他们只输出布尔结果” . 两个库都计算交叉多边形 - 例如，查看Clipper页面上带有图片的代码片段 .

    回复于
  • 2

    在Angus的Clipper与其他库的基准测试中，他有一个多边形区域计算方法 . 我用它并修改了他的椭圆方法 . 结果如下：

    void Ellipse2Poly(double theta, double A1, double B1, double H1, double K1, Poly& p)
{ 
    const double pi = 3.1415926535898, tolerance = 0.125;
    const int n = 30;
    double step = pi/(double)n;
    double a = A1; // Long semi-axis length
    double b = B1; // short semi-axis length
    double xc = H1; // current X position
    double yc = K1; // current Y position
    double sintheta = sin(theta);
    double costheta = cos(theta);
    double t = 0;
    p.resize(2*n+1);
    for (int i = 0; i < 2*n+1; i++)
    {
        p[i].x = xc + a*cos(t)*costheta - b*sin(t)*sintheta;
        p[i].y = yc + a*cos(t)*sintheta + b*sin(t)*costheta;
        t += step;
    }
}

    面积计算是：

    double OverlapArea(Poly poly1, Poly poly2)
{
    Poly clip;
    Polys polys_poly1, polys_poly2, polys_clip;
    polys_poly1.resize(1);
    polys_poly2.resize(1);
    polys_clip.resize(1);
    polys_poly1[0] = poly1;
    polys_poly2[0] = poly2;
    polys_clip[0] = clip;
    Polygons clipper_polys_poly1, clipper_polys_poly2, clipper_polys_clip;
    LoadClipper(clipper_polys_poly1,polys_poly1);
    LoadClipper(clipper_polys_poly2,polys_poly2);
    ClipType op = ctIntersection;
    Clipper cp;
    cp.AddPolygons(clipper_polys_poly1,ptSubject);
    cp.AddPolygons(clipper_polys_poly2,ptClip);
    cp.Execute(op,clipper_polys_clip,pftEvenOdd,pftEvenOdd);
    if(clipper_polys_clip.size() != 0)
    {
        UnloadClipper(polys_clip,clipper_polys_clip);
        return Area(polys_clip[0]);
    }
    else
        return 0.0;
}

    它比_1384765慢，但非常稳定 . 我一夜之间运行它2 * 10 ^ 5步，它没有崩溃 . 花了6小时12分钟，而Boost需要大约4小时，但我很高兴 .

    EDIT:

    我重写了其他一些功能，所以比较对Clipper不公平！对于相同的配置和100K时间步长，Clipper在2小时36分钟内完成了操作，我觉得非常好！ Boost将在大约2小时15分钟内完成相同的操作，所以我发现它们在这些长跑中非常可比！

    回复于

相关问题