python - 沿多边形边界随机采样点

Question

我试图在由任意数量的点组成的多边形边界上随机采样点。多边形由一组 x,y 坐标组成。我想保留多边形的原始顶点并添加随机采样点，并尽可能保留多边形的形状。如本例所示，给定一个原始多边形(蓝色顶点，左侧)，我想要一个随机采样的多边形，其中 N=25 个点沿原始多边形的边界(红色顶点，右侧)。

下面的代码是我尝试使用样条插值来执行此操作，但插值的结果最终会显着扭曲多边形的形状(使其更圆)，尤其是当多边形的顶点数量较少时首先。

def single_parametric_interpolate(obj_x_loc,obj_y_loc,numPts=50):
    '''
    Interpolate a single given bounding box obj_x_loc,obj_y_loc
    return a new set of coordinates interpolated on numPts 
    '''
    tck, u =splprep(np.array([obj_x_loc,obj_y_loc]),s=0,per=1)
    u_new = np.linspace(u.min(),u.max(),numPts)
    new_points = splev(u_new, tck,der=0)
    return new_points

有没有更好的方法来进行这种类型的采样，而不会扭曲多边形的最终形状？

Answer 1

您可以计算多边形的周长 p(计算边长)。选择一个角，在 [0,p[ 中获取一个随机数 r 然后沿着周边“走”这个长度 r 例如逆时针方向并在此处放置一个点。

def single_parametric_interpolate(obj_x_loc,obj_y_loc,numPts=50):
    n = len(obj_x_loc)
    vi = [[obj_x_loc[(i+1)%n] - obj_x_loc[i],
         obj_y_loc[(i+1)%n] - obj_y_loc[i]] for i in range(n)]
    si = [np.linalg.norm(v) for v in vi]
    di = np.linspace(0, sum(si), numPts, endpoint=False)
    new_points = []
    for d in di:
        for i,s in enumerate(si):
            if d>s: d -= s
            else: break
        l = d/s
        new_points.append([obj_x_loc[i] + l*vi[i][0],
                           obj_y_loc[i] + l*vi[i][1]])
    return new_points