我如何“膨胀”一个多边形?也就是说,我想做一些类似的事情:
要求是,新的(膨胀的)多边形的边/点与旧的(原始的)多边形的边/点的距离都是相同的(在示例图片上,它们不是,因为这样它就必须使用弧来膨胀顶点,但让我们暂时忘记这一点;))。
我要找的数学术语实际上是向内/向外多边形偏移。balint指出这一点+1。另一种命名是多边形缓冲。
我的搜索结果:
以下是一些链接:
多边形偏移策略综述 多边形偏移,问题 缓冲多边形数据
我如何“膨胀”一个多边形?也就是说,我想做一些类似的事情:
要求是,新的(膨胀的)多边形的边/点与旧的(原始的)多边形的边/点的距离都是相同的(在示例图片上,它们不是,因为这样它就必须使用弧来膨胀顶点,但让我们暂时忘记这一点;))。
我要找的数学术语实际上是向内/向外多边形偏移。balint指出这一点+1。另一种命名是多边形缓冲。
我的搜索结果:
以下是一些链接:
多边形偏移策略综述 多边形偏移,问题 缓冲多边形数据
当前回答
谢谢你在这个话题上的帮助,如果有人感兴趣,这里是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 });
}
}
其他回答
你要找的多边形在计算几何中称为内/外偏移多边形,它与直骨架密切相关。
这是一个复杂多边形的几个偏移多边形:
这是另一个多边形的直骨架:
正如在其他评论中指出的那样,取决于你计划“膨胀/收缩”你的多边形的程度,你最终可以得到不同的输出连接。
从计算的角度来看:一旦你有了直线骨架,你应该能够相对容易地构建偏移多边形。开源的CGAL库(非商业免费)有一个实现这些结构的包。请参阅此代码示例使用CGAL计算偏移多边形。
包手册应该给你一个很好的起点,即使你不打算使用CGAL,如何构造这些结构,并包含参考文献的数学定义和属性:
CGAL手册:2D直骨架和多边形偏移
这是另一个解决方案,看看你是否更喜欢这个。
做一个三角测量,不一定是delaunay,任何三角测量都可以。 膨胀每个三角形——这应该是微不足道的。如果你以逆时针的顺序存储三角形,只要将线移动到右手边并做交点。 使用改进的Weiler-Atherton裁剪算法合并它们
谢谢你在这个话题上的帮助,如果有人感兴趣,这里是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 });
}
}
我使用简单的几何:向量和/或三角学
在每个角求中向量和中角。中向量是由边角定义的两个单位向量的算术平均值。中角是边角的一半。 如果你需要扩展(或收缩)你的多边形的数量d从每条边;你应该向外(向内)乘以d/sin(中角)来得到新的角点。 对所有的角重复这个步骤
注意你的方向。使用定义角的三个点进行逆时针测试;找出哪条路是出去,哪条路是进去。
对于这些类型的事情,我通常使用JTS。出于演示目的,我创建了这个使用JSTS (JTS的JavaScript端口)的jsFiddle。你只需要将坐标转换为JSTS坐标:
function vectorCoordinates2JTS (polygon) {
var coordinates = [];
for (var i = 0; i < polygon.length; i++) {
coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y));
}
return coordinates;
}
结果是这样的:
附加信息:我通常使用这种类型的膨胀/收缩(为我的目的做了一点修改)在地图上绘制的多边形上设置半径边界(使用传单或谷歌地图)。您只需将(lat,lng)对转换为JSTS坐标,其他一切都是相同的。例子: