在Python中如何从一组角度生成多边形？

Question

大家好（第一次在这里发帖，希望我没有犯什么错误）...

我正在尝试使用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

- mjszczep

Answer 1

问题在于您选择角度的方式。您必须遵守两个限制条件。

第一个限制条件凸多边形的角度和为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.y > 0的u。
2. 当(listDV.last^listDV.first < 0)时，{选择一条随机的线，计算方向向量u，使得listDV.last^u < 0，将u推入listDV的末尾}。
3. 丢弃listDV的最后一个向量。

现在你有了一组与你的线平行的方向向量。这个列表形成了一个凸多边形。

接下来是创建你的多边形。如果需要帮助，请告诉我！

- Cyril

---

谢谢！我在七月中旬到八月时已经解决了这个问题，但是我很感激你的帮助，我会尝试一下。 - mjszczep