我如何“膨胀”一个多边形?也就是说，我想做一些类似的事情:
要求是，新的(膨胀的)多边形的边/点与旧的(原始的)多边形的边/点的距离都是相同的(在示例图片上，它们不是，因为这样它就必须使用弧来膨胀顶点，但让我们暂时忘记这一点;))。
我要找的数学术语实际上是向内/向外多边形偏移。balint指出这一点+1。另一种命名是多边形缓冲。
我的搜索结果:
以下是一些链接:
多边形偏移策略综述 多边形偏移，问题 缓冲多边形数据
当前回答
你要找的多边形在计算几何中称为内/外偏移多边形，它与直骨架密切相关。
这是一个复杂多边形的几个偏移多边形:
这是另一个多边形的直骨架:
正如在其他评论中指出的那样，取决于你计划“膨胀/收缩”你的多边形的程度，你最终可以得到不同的输出连接。
从计算的角度来看:一旦你有了直线骨架，你应该能够相对容易地构建偏移多边形。开源的CGAL库(非商业免费)有一个实现这些结构的包。请参阅此代码示例使用CGAL计算偏移多边形。
包手册应该给你一个很好的起点，即使你不打算使用CGAL，如何构造这些结构，并包含参考文献的数学定义和属性:
CGAL手册:2D直骨架和多边形偏移
其他回答
每条线都应该将平面分割为“内部”和“轮廓”;你可以用常用的内积法求出来。
将所有的线向外移动一段距离。
考虑所有相邻直线对(直线，不是线段)，求交点。这些是新的顶点。
清除新顶点通过删除任何交叉部分。我们这里有几个案子
(a)个案一:
0--7 4--3
| | | |
| 6--5 |
| |
1--------2
如果你把它除以1，你会得到这个:
0----a----3
| | |
| | |
| b |
| |
| |
1---------2
7和4重叠。如果你看到这个，你去掉这个点和中间的所有点。
(b)情况2
0--7 4--3
| | | |
| 6--5 |
| |
1--------2
如果你把它乘以2，你会得到这个:
0----47----3
| || |
| || |
| || |
| 56 |
| |
| |
| |
1----------2
为了解决这个问题，对于直线的每一段，你必须检查它是否与后面的段重叠。
(c)情况3
4--3
0--X9 | |
| 78 | |
| 6--5 |
| |
1--------2
除以1。这是情况1的一般情况。
(d)情况4
与case3相同，但支出2。
实际上，如果你能处理情况4。所有其他的情况都是一些特殊的情况有一些直线或顶点重叠。
在情况4中，你保留一个顶点的堆栈。当你发现与后一条线重叠的线时，你就推，当你得到后一条线时，就弹出。就像你在凸船体中做的一样。
非常感谢安格斯·约翰逊的快船库。 在clipper主页http://www.angusj.com/delphi/clipper.php#code上有很好的代码示例用于做剪贴的东西 但是我没有看到多边形偏移的例子。所以我想，如果我发布我的代码，也许对某些人是有用的:
public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
{
List<Point> resultOffsetPath = new List<Point>();
List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
foreach (var point in originalPath)
{
polygon.Add(new ClipperLib.IntPoint(point.X, point.Y));
}
ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset();
co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon);
List<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
co.Execute(ref solution, offset);
foreach (var offsetPath in solution)
{
foreach (var offsetPathPoint in offsetPath)
{
resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y)));
}
}
return resultOffsetPath;
}
你要找的多边形在计算几何中称为内/外偏移多边形，它与直骨架密切相关。
这是一个复杂多边形的几个偏移多边形:
这是另一个多边形的直骨架:
正如在其他评论中指出的那样，取决于你计划“膨胀/收缩”你的多边形的程度，你最终可以得到不同的输出连接。
从计算的角度来看:一旦你有了直线骨架，你应该能够相对容易地构建偏移多边形。开源的CGAL库(非商业免费)有一个实现这些结构的包。请参阅此代码示例使用CGAL计算偏移多边形。
包手册应该给你一个很好的起点，即使你不打算使用CGAL，如何构造这些结构，并包含参考文献的数学定义和属性:
CGAL手册:2D直骨架和多边形偏移
谢谢你在这个话题上的帮助，如果有人感兴趣，这里是c++的代码。测试过了，很管用。如果你给offset = -1.5，它会缩小多边形。
typedef struct {
double x;
double y;
} Point2D;
double Hypot(double x, double y)
{
return std::sqrt(x * x + y * y);
}
Point2D NormalizeVector(const Point2D& p)
{
double h = Hypot(p.x, p.y);
if (h < 0.0001)
return Point2D({ 0.0, 0.0 });
double inverseHypot = 1 / h;
return Point2D({ (double)p.x * inverseHypot, (double)p.y * inverseHypot });
}
void offsetPolygon(std::vector<Point2D>& polyCoords, std::vector<Point2D>& newPolyCoords, double offset, int outer_ccw)
{
if (offset == 0.0 || polyCoords.size() < 3)
return;
Point2D vnn, vpn, bisn;
double vnX, vnY, vpX, vpY;
double nnnX, nnnY;
double npnX, npnY;
double bisX, bisY, bisLen;
unsigned int nVerts = polyCoords.size() - 1;
for (unsigned int curr = 0; curr < polyCoords.size(); curr++)
{
int prev = (curr + nVerts - 1) % nVerts;
int next = (curr + 1) % nVerts;
vnX = polyCoords[next].x - polyCoords[curr].x;
vnY = polyCoords[next].y - polyCoords[curr].y;
vnn = NormalizeVector({ vnX, vnY });
nnnX = vnn.y;
nnnY = -vnn.x;
vpX = polyCoords[curr].x - polyCoords[prev].x;
vpY = polyCoords[curr].y - polyCoords[prev].y;
vpn = NormalizeVector({ vpX, vpY });
npnX = vpn.y * outer_ccw;
npnY = -vpn.x * outer_ccw;
bisX = (nnnX + npnX) * outer_ccw;
bisY = (nnnY + npnY) * outer_ccw;
bisn = NormalizeVector({ bisX, bisY });
bisLen = offset / std::sqrt((1 + nnnX * npnX + nnnY * npnY) / 2);
newPolyCoords.push_back({ polyCoords[curr].x + bisLen * bisn.x, polyCoords[curr].y + bisLen * bisn.y });
}
}
我想我可以简单地提到我自己的多边形裁剪和偏移库- Clipper。
虽然Clipper主要是为多边形裁剪操作而设计的，但它也做多边形偏移。该库是用Delphi、c++和c#编写的开源免费软件。它有一个非常无限制的Boost许可证，允许它在免费软件和商业应用程序中免费使用。
多边形偏移可以使用三种偏移样式之一-方形，圆形和斜切。
2022年8月: Clipper2现在已经正式发布，它取代了Clipper(又名Clipper1)。
