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

我试图在 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

最佳答案

问题在于你的角度选择。您必须遵守两个约束条件。

第一个约束 一个凸多边形的内角和是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 .初始化列表 listDV与 u 的方向向量。注意:如果u.x = 0 , 然后选择 u例如u.y > 0 .
2. While( listDV.last^listDV.first < 0 ) {选择一条随机线，计算方向向量u例如 listDV.last^u < 0 ，把你推到listDV的末尾}.
3. 丢弃 listDV 的最后一个向量.

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

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

https://stackoverflow.com/questions/17242392/