logo标签列表

凸包距离

pythonscipydistanceconvex-hull
3

我一直在寻找一种计算到凸包/多边形距离的方法，使得如果点在凸包内部，则距离为正，如果在外部则为负。例如，给定一个凸包和一组点，能否计算出正/负距离？

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

# Original points, hull and test points
points = np.random.rand(30, 2)   # 30 random points in 2-D
hull = ConvexHull(points)
newpoints = np.random.rand(30, 2)   # 30 random points in 2-D

# Plot original points, hull and new points
plt.plot(points[:,0], points[:,1], 'ro')
plt.plot(points[hull.vertices,0], points[hull.vertices,1], 'r--', lw=2)
plt.plot(newpoints[:,0], newpoints[:,1], 'go')

所以我希望能够计算每个绿色点的有符号距离。非常感谢您的时间！！
更新，使用来自(http://www.fundza.com/vectors/point2line/index.html) 的代码可以计算无符号距离：
from scipy.spatial import ConvexHull
import matplotlib.pyplot as plt
import numpy as np
from vectors import *

# Original points, hull and test points
points = np.random.rand(30, 2)   # 30 random points in 2-D
hull = ConvexHull(points)
newpoints = np.random.rand(30, 2)   # 30 random points in 2-D



def pnt2line(pnt, start, end):
    line_vec = vector(start, end)
    pnt_vec = vector(start, pnt)
    line_len = length(line_vec)
    line_unitvec = unit(line_vec)
    pnt_vec_scaled = scale(pnt_vec, 1.0/line_len)
    t = dot(line_unitvec, pnt_vec_scaled)    
    if t < 0.0:
        t = 0.0
    elif t > 1.0:
        t = 1.0
    nearest = scale(line_vec, t)
    dist = distance(nearest, pnt_vec)
    nearest = add(nearest, start)
    return (dist, nearest)



pt_dist = []
for p_idx in range(30):
    pt = newpoints[p_idx,:]
    dist_list = []
    for v_idx in range(len(hull.vertices)):
        v1 = hull.vertices[v_idx - 1]
        v2 = hull.vertices[v_idx]
        start = points[v1]
        end = points[v2]
        temp = pnt2line(pt, start, end)
        dist_list.append(temp[0])
    pt_dist.append(min(dist_list))


# Plot original points, hull and new points
plt.plot(points[:,0], points[:,1], 'ro')
plt.plot(points[hull.vertices,0], points[hull.vertices,1], 'r--', lw=2)
plt.plot(newpoints[:,0], newpoints[:,1], 'go')
for p_idx in range(30):
    pt = newpoints[p_idx,:]
    dist = pt_dist[p_idx]
    distLabel = "%.2f" % dist
    plt.annotate(distLabel,xy=pt)

(Note modified vector.py code to 2d):
import math

def dot(v,w):
    x,y = v
    X,Y = w
    return x*X + y*Y

def length(v):
    x,y = v
    return math.sqrt(x*x + y*y)

def vector(b,e):
    x,y = b
    X,Y = e
    return (X-x, Y-y)

def unit(v):
    x,y = v
    mag = length(v)
    return (x/mag, y/mag)

def distance(p0,p1):
    return length(vector(p0,p1))

def scale(v,sc):
    x,y = v
    return (x * sc, y * sc)

def add(v,w):
    x,y = v
    X,Y = w
    return (x+X, y+Y)
你尝试过什么？我只看到你在绘图，如果你展示一下你所尝试的，我们可以帮助你。 - PepperoniPizza
我在网上找到了一些代码，可以让我计算无符号距离（来自这里：http://www.fundza.com/vectors/point2line/index.html），将在原文中发布... - user3685329
2个回答
1

感谢您的建议！如果我从http://geospatialpython.com/2011/01/point-in-polygon.html中包含一个Python点在多边形函数，我的完整代码将变为：

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

def pnt2line(pnt, start, end):
    line_vec = vector(start, end)
    pnt_vec = vector(start, pnt)
    line_len = length(line_vec)
    line_unitvec = unit(line_vec)
    pnt_vec_scaled = scale(pnt_vec, 1.0/line_len)
    t = dot(line_unitvec, pnt_vec_scaled)    
    if t < 0.0:
        t = 0.0
    elif t > 1.0:
        t = 1.0
    nearest = scale(line_vec, t)
    dist = distance(nearest, pnt_vec)
    nearest = add(nearest, start)
    return (dist, nearest)

def point_in_poly(x,y,poly):

    n = len(poly)
    inside = False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xints = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xints:
                        inside = not inside
        p1x,p1y = p2x,p2y

    return inside



# Original points, hull and test points
points = np.random.rand(30, 2)   # 30 random points in 2-D
hull = ConvexHull(points)
newpoints = np.random.rand(30, 2)   # 30 random points in 2-D



pt_dist = []
for p_idx in range(30):
    pt = newpoints[p_idx,:]
    dist_list = []
    for v_idx in range(len(hull.vertices)):
        v1 = hull.vertices[v_idx - 1]
        v2 = hull.vertices[v_idx]
        start = points[v1]
        end = points[v2]
        temp = pnt2line(pt, start, end)
        dist_list.append(temp[0])

    #Check point is within polygon
    inside =  point_in_poly(pt[0],pt[1],points[hull.vertices])
    if (inside == True):
        dist_temp = -1. * min(dist_list)
    else:
        dist_temp = min(dist_list)          

    pt_dist.append(dist_temp)


# Plot original points, hull and new points
plt.plot(points[:,0], points[:,1], 'ro')
plt.plot(points[hull.vertices,0], points[hull.vertices,1], 'r--', lw=2)
plt.plot(newpoints[:,0], newpoints[:,1], 'go')
for p_idx in range(30):
    pt = newpoints[p_idx,:]
    pt[1] = pt[1] + 0.01 
    dist = pt_dist[p_idx]
    distLabel = "%.2f" % dist
    plt.annotate(distLabel,xy=pt)

根据上述修改后的Vectors.py文件，得到以下图表：

Output plot

哪个看起来正确。谢谢！
1
您可以始终将此正距离乘以点是否在多边形内计算的真/假结果。我通常喜欢使用绕数算法（仅因为我从复变角度理解它） - 但计算交叉也可以很好地工作。
谢谢您的建议，我相信这是成功的，我会发布答案。 - user3685329
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接