沿多边形边界随机采样点 [英] random sampling of points along a polygon boundary

问题描述

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

I am trying to randomly sample points on a polygon boundary made of arbitrary number of points. The polygon consist of a set of x,y coordinates. I would like to keep the original vertices of the polygon as well as add the randomly sampled points, and preserve the shape of the polygon as much as possible. As shown in this example, given an orginal polygon (blue vertices, left), I want a randomly sampled polygon with N=25 points along the original polygon's boundary (red vertices, right).

下面的代码是我尝试使用样条插值进行的操作，但是插值的结果最终会严重扭曲多边形的形状(使其更圆)，尤其是在多边形的顶点数量很少的情况下.首先.

The code below is my attempt at using a spline interpolation to do this, but the results from the interpolation ends up significantly distorting the shape of the polygon (making it rounder), especially if the polygon has a small number of vertices to begin with.

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

有没有更好的方法来进行这种采样，而不会扭曲多边形的结果形状?

Is there a better way to do this type of sampling that would not distort the resulting shape of the polygon?

推荐答案

您可以计算多边形的周长 p (将边长加起来).选择一个角落，在 [0，p []中获得一个随机数 r ，然后沿周长遍历"此长度 r ，例如逆时针方向放置一个点.

You can calculate the perimeter p of the polygon (sum up the side lengths). Choose one corner, get a random number r in [0,p[ and then "walk" this length r along the perimeter in e.g. counter-clockwise orientation and put a point there.

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

这篇关于沿多边形边界随机采样点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！