Generate Polygon from Set of Angles in Python?

Question

Hello all (first time posting here so I hope I'm not doing anything horribly wrong)...

I'm trying to randomly generate a set of convex polygons with 3 to 2l sides in Python such that each side of each polygon is parallel to one of l predetermined lines. If anybody knows of a way of doing this (with or without the aid of a computational geometry package like CGAL or Shapely), that'd be fantastic.

I start with a list containing 2l angles (the direction of each line, and the direction of each line + pi for parallel sides). For each polygon I make, I randomly choose 3 to 2l angles from this list, sorted in increasing order such that no angle differs by more than pi from the one before it in order to ensure that the angles are capable of defining a polygon. However, after that I am unable to ensure that the polygons I generate remain convex and only contain sides parallel to the lines I chose. My code currently looks like this:

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

Answer 1

The problem lies in the selection of your angles. You have to respect two constraints.

First constraint The sum of the angles of a convex polygon is 180*(n-2) degrees, where n is the number of sides of your convex polygon [src].

Second constraint Given two lines, you have two choices for your angle :

You have to select the green angle. Your selection criteria is not very clear in your description, so I can't be sure if there is a mistake. To select the good angle, I think the simpliest thing to do is considering direction vector for each line. Compute u the direction vector of your last line (pointing towards the new line). Compute v, a direction vector of the new line. If (u^v) > 0, v is not correctly oriented, so you want to take -v. Else if (u^v) < 0, v is correctly oriented. Details : u^v = u.x*v.y -u.y*v.x

So this lead us to our second constraint. Considering u the direction vector of a side and u_next the direction vector of the next side, we have u^u_next < 0.

I think the second constraint is sufficient. We won't need the first one (but it is still good to know for general knowledge).

What to do Here's what I would do for your problem :

1. Select a random line. Compute the direction vector u0 such as u0.x > 0. Initialize the list listDV of direction vector with u. Note: if u.x = 0, then select u such as u.y > 0.
2. While(listDV.last^listDV.first < 0) {Select a random line, compute the direction vector u such as listDV.last^u < 0, push u at the end of listDV}.
3. Discard the last vector of listDV.

So now you have a list of direction vectors, which are parallel to your lines. The list forms a convex polygon.

Next will be the creation of your polygon. If you need help on this, let me know !