凸包面积的增量

Question

我想使用凸包绘制一组点的周围线条。但是，我希望面积比最小凸包大。如何实现这一点。附注：我正在使用scipy.spatial实现的ConvexHull，但它只能找到点集周围的最小面积。

- Laurynas Stašys

---

你正在寻找的操作在地理信息系统中被称为“缓冲”（buffering）。然而，看起来scypi并不支持它，正确地处理它也不是一件简单的事情。因此，如果您能使用GDAL（或类似工具），就可以轻松解决问题了。 链接 - dhke

Answer 1

from scipy.spatial  import ConvexHull
import matplotlib.pyplot as plt
import numpy as np
import math

def PointsInCircum(eachPoint,r,n=100):
    return [(eachPoint[0] + math.cos(2*math.pi/n*x)*r,eachPoint[1] + math.sin(2*math.pi/n*x)*r) for x in range(0,n+1)]


def bufferPoints (inPoints, stretchCoef, n):
    newPoints = []
    for eachPoint in inPoints:
        newPoints += PointsInCircum(eachPoint, stretchCoef, n)
    newPoints = np.array(newPoints)
    newBuffer = ConvexHull (newPoints)

    return newPoints[newBuffer.vertices]


if __name__ == '__main__':
    points = np.array([[-2,3], [2,4], [-2,-2], [2,-1], [1,-1], [-0.5, 0.5]])
    plt.scatter(points[:,0], points[:,1])
    plt.show()
    convh = ConvexHull(points)#Get the first convexHull (speeds up the next process)

    stretchCoef = 1.2
    pointsStretched = bufferPoints (points[convh.vertices], stretchCoef, n=10)
    plt.scatter(points[:,0], points[:,1])
    plt.scatter(pointsStretched[:,0], pointsStretched[:,1], color='r')
    plt.show() 

所以我更新了上面的代码。它围绕第一组ConvexHull顶点创建一个点圆，并创建一个新的ConvexHull。

这是该代码的输出绘图视图

- danwintsch

Answer 2

以下是一种解决您纸上问题的想法：

from scipy.spatial  import ConvexHull
import matplotlib.pyplot as plt
import numpy as np

if __name__ == '__main__':
    points = np.array([[-2,3], [2,4], [-2,-2], [2,-1], [1,-1], [-0.5, 0.5]])
    plt.scatter(points[:,0], points[:,1])
    plt.show()
    convh = ConvexHull(points)

    stretchCoef = 1.2
    pointsStretched = points[convh.vertices]*stretchCoef
    plt.scatter(points[:,0], points[:,1])
    plt.scatter(pointsStretched[:,0], pointsStretched[:,1], color='r')
    plt.show()

pointsStretched会为您的新凸包找到新的点。 使用拉伸系数在这里起作用，因为您在凸包的每个顶点上都有不同象限的点，但我认为您已经知道如何解决这个问题了。一种方法是在拉伸后的凸包中找到点，这些点沿着与初始点相同的向量。

- Dennis C Furlaneto

---

这是一个不错的解决方案。但它也会将距离原点较远的点/边界相对地向外移动更远。从图中看，似乎需要一个等距缓冲区。当然，多边形的确切缓冲区通常不再是一个多边形。 - dhke

非常正确dhke，感谢您指出这一点。为了解决这个问题，可以更改此算法以计算每个点的不同缩放系数，其中计算以边框的大小作为输入。 - Dennis C Furlaneto