我如何“膨胀”一个多边形?也就是说,我想做一些类似的事情:
要求是,新的(膨胀的)多边形的边/点与旧的(原始的)多边形的边/点的距离都是相同的(在示例图片上,它们不是,因为这样它就必须使用弧来膨胀顶点,但让我们暂时忘记这一点;))。
我要找的数学术语实际上是向内/向外多边形偏移。balint指出这一点+1。另一种命名是多边形缓冲。
我的搜索结果:
以下是一些链接:
多边形偏移策略综述 多边形偏移,问题 缓冲多边形数据
我如何“膨胀”一个多边形?也就是说,我想做一些类似的事情:
要求是,新的(膨胀的)多边形的边/点与旧的(原始的)多边形的边/点的距离都是相同的(在示例图片上,它们不是,因为这样它就必须使用弧来膨胀顶点,但让我们暂时忘记这一点;))。
我要找的数学术语实际上是向内/向外多边形偏移。balint指出这一点+1。另一种命名是多边形缓冲。
我的搜索结果:
以下是一些链接:
多边形偏移策略综述 多边形偏移,问题 缓冲多边形数据
当前回答
听起来你想要的是
Starting at a vertex, face anti-clockwise along an adjacent edge. Replace the edge with a new, parallel edge placed at distance d to the "left" of the old one. Repeat for all edges. Find the intersections of the new edges to get the new vertices. Detect if you've become a crossed polygon and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'm not sure whether there's a better way to detect this than just to compare every pair of non-adjacent edges to see if their intersection lies between both pairs of vertices.
生成的多边形位于所需的距离上,与旧多边形距离顶点“足够远”。在一个顶点附近,距离旧多边形d的点的集合,正如你所说,不是一个多边形,所以不能满足所述的要求。
我不知道这个算法是否有名字,网络上的示例代码,或者是一个残酷的优化,但我认为它描述了你想要的东西。
其他回答
你要找的多边形在计算几何中称为内/外偏移多边形,它与直骨架密切相关。
这是一个复杂多边形的几个偏移多边形:
这是另一个多边形的直骨架:
正如在其他评论中指出的那样,取决于你计划“膨胀/收缩”你的多边形的程度,你最终可以得到不同的输出连接。
从计算的角度来看:一旦你有了直线骨架,你应该能够相对容易地构建偏移多边形。开源的CGAL库(非商业免费)有一个实现这些结构的包。请参阅此代码示例使用CGAL计算偏移多边形。
包手册应该给你一个很好的起点,即使你不打算使用CGAL,如何构造这些结构,并包含参考文献的数学定义和属性:
CGAL手册:2D直骨架和多边形偏移
根据@JoshO'Brian的建议,R语言中的rGeos包实现了这个算法。参见rGeos::gBuffer。
这是这里解释的算法的c#实现。它也使用Unity数学库和集合包。
public static NativeArray<float2> ExpandPoly(NativeArray<float2> oldPoints, float offset, int outer_ccw = 1)
{
int num_points = oldPoints.Length;
NativeArray<float2> newPoints = new NativeArray<float2>(num_points, Allocator.Temp);
for (int curr = 0; curr < num_points; curr++)
{
int prev = (curr + num_points - 1) % num_points;
int next = (curr + 1) % num_points;
float2 vn = oldPoints[next] - oldPoints[curr];
float2 vnn = math.normalize(vn);
float nnnX = vnn.y;
float nnnY = -vnn.x;
float2 vp = oldPoints[curr] - oldPoints[prev];
float2 vpn = math.normalize(vp);
float npnX = vpn.y * outer_ccw;
float npnY = -vpn.x * outer_ccw;
float bisX = (nnnX + npnX) * outer_ccw;
float bisY = (nnnY + npnY) * outer_ccw;
float2 bisn = math.normalize(new float2(bisX, bisY));
float bislen = offset / math.sqrt((1 + nnnX * npnX + nnnY * npnY) / 2);
newPoints[curr] = new float2(oldPoints[curr].x + bislen * bisn.x, oldPoints[curr].y + bislen * bisn.y);
}
return newPoints;
}
另一个选择是使用boost::polygon——文档有些缺乏,但你应该会发现resize和bloat方法,以及重载的+=操作符,它们实际上实现了缓冲。例如,增加一个多边形(或一组多边形)的大小可以像下面这样简单:
poly += 2; // buffer polygon by 2
这是另一个解决方案,看看你是否更喜欢这个。
做一个三角测量,不一定是delaunay,任何三角测量都可以。 膨胀每个三角形——这应该是微不足道的。如果你以逆时针的顺序存储三角形,只要将线移动到右手边并做交点。 使用改进的Weiler-Atherton裁剪算法合并它们