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，则选择u如u.y > 0。
  2. While( listDV.last^listDV.first < 0) {选择一条随机线，计算方向向量u如listDV.last^u < 0，将 u 推入listDV}。
  3. 丢弃 的最后一个向量listDV。

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

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

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