1

我有一个 2D 粒子系统，其中粒子表示为椭圆。我需要计算椭圆 - 椭圆重叠区域，但这是一个很难分析的问题Ellipse-Ellipse Overlap。我现在将我的椭圆表示为 20 边形，以便它们被“多边形化”并且我正在使用Boost.Geometry它来进行必要的计算。

Boost.Geometry但是，很多时候，我从:中得到一个例外boost.geometry overlay invalid input exception。我搜索发现这是boost.Geometry1.53 版本的一个已知错误并且没有修复。甚至即将发布的 v1.54 的文档也没有说明解决此问题的任何内容。

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

Boost overlay例外情况在 MSVC 2010 和 2012 下的 Win7 x64、MinGW 和 Qt 4.8.1 下的 Linux Mint 14 下是一致的。

4

3 回答 3

2

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

于 2013-05-15T17:39:40.487 回答
0

您可以向 Boost 票证系统提交票证吗？包括给出无效输入异常的几何对样本？该错误可能有多种原因，要么确实无效，要么是库中的错误。其中一些问题在 1.54 中已修复。

于 2013-05-15T14:59:12.220 回答
0

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

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

编辑：

我重写了一些其他的函数，所以这个比较对 Clipper 是不公平的！同样的配置和 100K 的时间步长，Clipper 在 2h 36min 内完成了操作，我觉得非常好！Boost 将在大约 2 小时 15 分钟内完成相同的操作，因此我发现它们在这些长时间运行中非常具有可比性！

于 2013-05-17T09:22:19.793 回答