沿多边形边界点的随机抽样

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