0

我在 boost::geometry 中有许多多边形，并且想从一个多边形中找到与第一个多边形具有最长公共边界的特定邻居。多边形完全相互接触，因此boost::geometry::disjoint返回 false，但以下代码始终返回周长 0：

typedef boost::geometry::model::d2::point_xy<double>      boost_pnt;
typedef boost::geometry::model::polygon<boost_pnt>        boost_poly;

boost_poly otherPol = ...;
boost_poly thisPol  = ...;

if(! boost::geometry::intersection(thisPol, otherPol, out))
    return -1;

float perimeter = 0;
BOOST_FOREACH(boost_poly const& p, out)
{
    perimeter += boost::geometry::perimeter(p);
}
return perimeter;

我怎样才能找到共同的“边界”，即两个多边形的接触长度？

4

2 回答 2

1

我不是数学家，也不知道 boost::geometry 库，所以我应该试一试。:-)

您需要将多边形 1 中的每个线段与多边形 2 中的每个线段进行比较。因此，在每次比较中，我们有两条线段，A 和 B

首先，我将比较两条线段的单位向量，如果它们相等或完全相反，则线是平行的。

如果线是平行的，我将采用由 A 的一个点和 B 的一个点定义的线段（在任何一种情况下都无关紧要），并计算其单位向量。如果该单位向量等于（或正好相反）上面的单位向量，则线段在同一条无限线上。

如果是这种情况，我们可以很容易地找到线段的哪些端点（如果有的话）位于另一个端点内部。即：如果 A.point1 在 B.point1 的上方和左侧，而 B.point2 在 A.point1 的上方和左侧，则 A.point1 位于线段 B 上。（帮助绘制它。）

请注意，其中一条线段可能完全位于另一条线段之内——因此，如果 A 完全位于 B 之内，则 B 的两个端点都不会位于 A 之内。

在 A 完全位于 B 内的情况下，这些段的共享边界当然是 A 的长度。

否则，找出 A 中的一点和 B 中的一点之间的最大长度，然后从 A 和 B 的长度之和中减去该长度。

boost::geometry 中任何有帮助的特性，你都应该使用！:-)

（请注意，我已经说了很多“等于”，我们当然会处理浮点运算，所以相等是一个稍微灵活的术语。）

于 2013-11-04T17:33:58.463 回答
0

我相信在多边形接触但不重叠的情况下，操作geometry::intersection将生成一个空容器，out但仍会返回true。这本质上是对触摸的定义：内部没有交叉。

由于 Boost.Geometry 适用于内饰，因此您无法从中获得更多收益。

您真正想要的是将您的多边形视为 CGAL 库定义为Nef 多边形。CGAL 提供了一个 API，它允许您将 Nef 多边形作为两个 Nef 多边形的交集。如果操作数相互接触，结果将是一条折线。

但是不要屏住呼吸，Nef 操作比 Boost.Geometry 更慢，API 更复杂；通过自己实现该功能，您可能会获得更好的结果。

于 2013-11-17T01:53:07.793 回答