c++ - 用GPC或者Clipper计算多边形相交面积

  显示原文与译文双语对照的内容

我有一个 2D 粒子系统,其中粒子被表示为椭圆。 需要计算椭圆椭圆重叠区域,但这是一个很难解析的问题椭圆椭圆重叠。 现在我将椭圆表示为 20 -gons,所以它们是"polygonized",我使用 Boost.Geometry 进行必要的计算。

但是,通常,我从 Boost.Geometry 获得了一个异常: boost.geometry overlay invalid input exception 在version中,我发现这是一个已知的Bug,并且没有版本1的修复。 甚至关于即将发布的v1.54的文档也没有提到修复这个问题。

我偶然发现了裁剪器和 GPC - 通用多边形裁剪库 。 他们似乎做我想要的,但是他们只输出布尔结果。 有人知道是否有办法用这些库输出计算过的交叉口的面积? 我猜,由于交叉存储在内存中作为一种多边形,我可以使用三角或者它的他方法来计算区域。 任何指针都会非常感激 !

,异常在,和 Boost overlay 下的MSVC 2010和 2012下一致,MINGW 和 Qt 4.8.1在 Linux Mint 14下。

时间: 原作者:

你似乎对Clipper和 GPC"但是,他们只输出布尔结果。"有错。 两个库都计算相交多边形- 例如在Clipper页上查看带有图片的代码 Fragment 。

原作者:

你能把票提交到 Boost system? 包含给出无效输入异常的几何对示例? 错误可能有几个原因,可能是无效的,或者是库中的Bug 。 这些问题中的一些是每 1.54.

在它的他图书馆的for中,他有一种多边形面积计算方法。 我使用了这个方法修改了他的椭圆法。 结果如下:


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 慢,但非常稳定。 我每晚 overnight 2 *10^5 时间运行它,并没有崩溃。 它花了 6h 12分钟,而升级将占用,但我很高兴。

编辑:

我重写了一些其他函数,所以比较对Clipper是不公平的 ! 对于相同的配置和 100K 个时间步,Clipper完成了 2h 分钟的操作,我觉得很不错 ! Boost将在大约 2h 15分钟内完成相同的操作,所以我发现它们在这些长期运行中非常相似 !

原作者:
...