2

大家好(第一次在这里发帖,所以我希望我没有做任何可怕的错误)......

我试图在 Python 中随机生成一组具有 3 到2l个边的凸多边形,这样每个多边形的每一边都平行于l预定线之一。如果有人知道这样做的方法(有或没有像 CGAL 或 Shapely 这样的计算几何包的帮助),那就太棒了。

我从一个包含2l个角度的列表开始(每条线的方向,以及每条线的方向 + 平行边的 pi)。对于我制作的每个多边形,我从这个列表中随机选择 3 到2l个角度,按升序排序,使得没有一个角度与其前一个角度的差异超过 pi,以确保这些角度能够定义一个多边形。但是,在那之后,我无法确保我生成的多边形保持凸面,并且只包含与我选择的线平行的边。我的代码目前如下所示:

def generate(l, n, w, h):
    """Generate n polygons with sides parallel to 
    at most l vectors in a w x h plane."""
    L = []
    polygons = []
    while len(L) < 2*l:
        i = random.uniform(0, math.pi)
        if i != math.pi and not i in L:
            L.append(i)
            L.append(i+math.pi)
    L.sort()
    while len(polygons) < n:
        Lp = list(L)
        rm = random.randint(0, 2*l-3)
        #Filter out rm lines, if possible
        for i in range(rm):
            i = random.randint(0, len(Lp)-1)
            for j in range(i, len(Lp)) + range(0, i):
                nxt = Lp[(j+1)%len(Lp)]
                prv = Lp[(j-1)%len(Lp)]
                if prv < nxt < prv+math.pi or nxt < (prv+math.pi)%(2*math.pi)-1e-14 < prv:
                    del Lp[j]
                    break

        # Choose a "center point, then generate a polygon consisting of points
        # a fixed distance away in the direction perpendicular to each angle.
        # This does not work however; resulting polygons may have sides not 
        # parallel to one of the original lines.
        cx, cy = random.uniform(-w/2,w/2), random.uniform(-h/2,h/2)
        points = []
        r = random.uniform(10,100) 
        for theta in Lp:
            # New point is r away from "center" in direction
            # perpendicular to theta
            x = cx + r * math.sin(theta)
            y = cy - r * math.cos(theta)
            points.append(polygon.Vector(x,y))     
        polygons.append(polygon.Polygon(points))
    return polygons
4

1 回答 1

0

问题在于角度的选择。你必须尊重两个约束。

第一个约束凸多边形的角度之和是180*(n-2)度数,其中n是凸多边形的边数 [ src ]。

第二个约束给定两条线,您的角度有两种选择: 角度选择

您必须选择绿色角度。您的描述中您的选择标准不是很清楚,因此我无法确定是否有错误。要选择好的角度,我认为最简单的事情就是考虑每条线的方向矢量。计算u最后一行的方向向量(指向新行)。计算v,新线的方向向量。如果(u^v) > 0,v的方向不正确,那么您要取-v. 否则,如果(u^v) < 0,v方向正确。细节 : u^v = u.x*v.y -u.y*v.x

所以这导致了我们的第二个约束。考虑u一侧u_next的方向向量和下一侧的方向向量,我们有u^u_next < 0

我认为第二个约束就足够了。我们不需要第一个(但了解一般知识仍然很好)。

怎么办这是我将为您的问题做的事情:

  1. 选择一条随机线。计算方向向量u0,例如u0.x > 0。用 u初始化listDV方向向量列表。注:如果u.x = 0,则选择uu.y > 0
  2. While( listDV.last^listDV.first < 0) {选择一条随机线,计算方向向量ulistDV.last^u < 0,将 u 推入listDV}。
  3. 丢弃 的最后一个向量listDV

所以现在你有一个方向向量列表,它们与你的线平行。该列表形成一个凸多边形。

接下来将是创建多边形。如果您需要这方面的帮助,请告诉我!

于 2013-08-12T10:09:14.387 回答