CODEWITHSUNDEEP
python
DinosaurMoritz
DinosaurMoritz

Reputation: 145

turn polygon into triangles

I am looking for a simple way to divide a polygon into triangles. It will have no angles > 180. For example the polygon: A, B, C, D, E should be A, B, C, A, C, E, C, D, E. A picture:

poly

I have tried:

    def turnIntoTriangles(poly):
        triangles = []

        while len(poly) > 3:
            triangles.append([poly[0], poly.pop(1), poly[-2]])

        triangles.append(poly)

        return triangles

This works for polygons with 4 corners, but not any higher.

Upvotes: 0

Views: 1415

Answers (3)

Alain T.
Alain T.

Reputation: 42139

You can use a list comprehension to combine the first point with all consecutive pairs of subsequent points (using zip):

def tripoly(poly):
    return [(poly[0],b,c) for b,c in zip(poly[1:],poly[2:])]

output:

print(tripoly("ABCDE")) # [('A', 'B', 'C'), ('A', 'C', 'D'), ('A', 'D', 'E')]
print(tripoly("CDEAB")) # [('C', 'D', 'E'), ('C', 'E', 'A'), ('C', 'A', 'B')]
print(tripoly("ABCDEFGHIJKL"))
# [('A', 'B', 'C'), ('A', 'C', 'D'), ('A', 'D', 'E'), ('A', 'E', 'F'), 
   ('A', 'F', 'G'), ('A', 'G', 'H'), ('A', 'H', 'I'), ('A', 'I', 'J'), 
   ('A', 'J', 'K'), ('A', 'K', 'L')]

This produces the triangles based on the first point (without destroying the source data). You could wrap it in a rotating loop to get all possibilities.

You could also do it with recursion:

def tripoly(poly):
    if len(poly)<3: return []
    return [tuple(poly[:3])] + tripoly(poly[:1]+poly[2:])

Upvotes: 1

DinosaurMoritz
DinosaurMoritz

Reputation: 145

I found:

def turnIntoTriangles(poly):
    triangles = []

    while len(poly) - 2 > 1:
        triangles.append([poly[0], poly.pop(-1), poly[-1]])

    triangles.append(poly)
    return triangles

to work.

Upvotes: 0

Daweo
Daweo

Reputation: 36745

turn polygon into triangles

This action has own name: polygon triangulation amd there are numerous algorithms for that. I assume that It will have no angles > 180. means you will deal only with convex shapes, thus fan triangulation should suffice.

Upvotes: 0

Related Questions