How do you triangulate a polygon in Shapely?

Question

How do you triangulate a polygon in Shapely? Shapely actually offers a triangulate() function, but that only triangulates the vertices of the polygon as a point set. For convex polygons the solution is the same, but for non-convex you get extra triangles. I tried removing all triangles that are outside the polygon, but sometimes triangles can cross the polygon boundary (see below image). I guess I could remove those too, then substract the remaining triangles from the polygon and recursively triangulate the components of that difference. But is there a simpler way?

Example where polygon triangulation is not a subset of vertices triangulation (polygon boundary wider and grey, triangle boundaries darker and thinner): Code to produce this geometry:

from shapely.geometry import Polygon
from shapely.ops import triangulate

polygon = Polygon( [ (0,0), (0,3), (5,3), (2,4), (6,4), (6,0) ])
delauney=triangulate(polygon)

Glut

what you are looking for is called "constrained triangulation" and as far as I know shapely doesn't support that, but there is a pure Python sect library that can solve this problem even for polygon with holes – Geri

Answer 1

I have updated my answer at Delaunay triangulation algorithm in shapely producing erratic result

import numpy as np
from shapely.geometry import Polygon
from shapely.ops import triangulate
import shapely.wkt
import geopandas as gpd
from geovoronoi import voronoi_regions_from_coords

def to_triangles(polygon):

    poly_points = []

    gdf_poly_exterior = gpd.GeoDataFrame({'geometry': [polygon.buffer(-0.0000001).exterior]}).explode().reset_index()
    for geom in gdf_poly_exterior.geometry:
        poly_points += np.array(geom.coords).tolist()

    try:
        polygon.interiors[0]
    except:
        poly_points = poly_points
    else:
        gdf_poly_interior = gpd.GeoDataFrame({'geometry': [polygon.interiors]}).explode().reset_index()
        for geom in gdf_poly_interior.geometry:
          poly_points += np.array(geom.coords).tolist()

    poly_points = np.array([item for sublist in poly_points for item in sublist]).reshape(-1,2)

    poly_shapes, pts = voronoi_regions_from_coords(poly_points, polygon)
    gdf_poly_voronoi = gpd.GeoDataFrame({'geometry': poly_shapes}).explode().reset_index()
    gdf_poly_voronoi.plot()

    tri_geom = []
    for geom in gdf_poly_voronoi.geometry:
        inside_triangles = [tri for tri in triangulate(geom) if tri.centroid.within(polygon)]
        tri_geom += inside_triangles

    gdf_poly_triangles = gpd.GeoDataFrame({'geometry': tri_geom})

    gdf_poly_exterior.plot()
    if 'gdf_poly_interior' in locals():
        gdf_poly_interior.plot()
    gdf_poly_triangles.plot()

polygon_1 = Polygon([(0, 0), (0, 3), (5, 3), (2, 4), (6, 4), (6, 0)])
polygon_2 = Polygon([(3.0, 0.0), (2.0, 0.0), (2.0, 0.75), (2.5, 0.75), (2.5, 0.6), (2.25, 0.6), (2.25, 0.2), (3.0, 0.2), (3.0, 0.0)])
poly_3_wkt = 'POLYGON ((-74.05644319847762 4.664371152795165, -74.05701264773319 4.663503533579181, -74.05770573357918 4.662810447733186, -74.05896428283818 4.662056102337443, -74.05990224838993 4.661771573597983, -74.06224145161008 4.661772473597984, -74.06317941716183 4.662057002337444, -74.06443796642083 4.662811347733187, -74.06572065226682 4.664052233579182, -74.06921901369725 4.668360960588712, -74.07141674761461 4.670691972117472, -74.07635895116509 4.673818151938486, -74.07894493390593 4.675834266094067, -74.08192435226682 4.679424333579181, -74.08891615226682 4.688383433579182, -74.08958587724112 4.689463067989243, -74.09086467349047 4.690719228823506, -74.09790275116509 4.694460551938487, -74.10034036642082 4.696114147733187, -74.10386724657296 4.698958762835078, -74.10814346936803 4.700870863662334, -74.10930545161006 4.700957773597984, -74.11043741716183 4.701320402337444, -74.11139045116509 4.701828051938487, -74.11214813390593 4.702449866094067, -74.11445885226682 4.704984433579183, -74.11521319766256 4.706242982838176, -74.11590442640203 4.70845234838992, -74.11611382363337 4.710865185701647, -74.11554750632175 4.71273208368413, -74.11467343390593 4.713910633905932, -74.11305131716183 4.714994497662556, -74.11211335161008 4.715279026402015, -74.11073328554708 4.715355222566556, -74.11041129766257 4.716545717161825, -74.1094660522668 4.718057466420818, -74.10756213390592 4.720161033905933, -74.10568445116508 4.721873348061513, -74.10420772338625 4.722584201678661, -74.10275629999998 4.7227995, -74.10130487661371 4.722584201678661, -74.09995094883489 4.721945648061514, -74.09403374773316 4.716245366420819, -74.09338219367824 4.71525808368413, -74.09288787359796 4.71387655161008, -74.09288787359796 4.711925648389919, -74.0936469519385 4.710096948834901, -74.09548963357916 4.708043347733187, -74.09763068874044 4.70677727898599, -74.09460666784895 4.704312469919607, -74.09203589291714 4.702595752799392, -74.08765371631586 4.700417706321742, -74.08459603357916 4.698508252266813, -74.08273894773316 4.696641066420818, -74.08206922275886 4.695561432010757, -74.08118604773318 4.694727366420818, -74.0717936025263 4.682825210334004, -74.06562484883489 4.678834648061513, -74.06390001213198 4.677314420684328, -74.0535710885149 4.739037649974117, -74.05520778283815 4.737937702337444, -74.05712119999998 4.7375571, -74.06045152338628 4.738003698321339, -74.06217206642083 4.738923347733187, -74.06340970632175 4.74043141631587, -74.06393542640203 4.74187004838992, -74.06400742363337 4.743335585701648, -74.063537026402 4.74698295161008, -74.06279044806149 4.748785351165098, -74.06139073691359 4.75018144712255, -74.0609743487264 4.751890490745711, -74.06128649999999 4.753612599999999, -74.06107120167866 4.755064023386272, -74.06039964806149 4.756487551165098, -74.0594142664208 4.757574752266813, -74.05806621716184 4.758372197662556, -74.05615280000001 4.7587528, -74.05377854838993 4.758482026402016, -74.0507277649826 4.757844764394359, -74.05055722640202 4.75945045161008, -74.04983964400328 4.762451751932777, -74.04873032640204 4.76925805161008, -74.04829449766255 4.770818617161826, -74.04766074258318 4.772140089033794, -74.04726809766255 4.773711517161825, -74.04651375226682 4.774970066420818, -74.04542655116509 4.775955448061513, -74.04410012338627 4.776582801678661, -74.04215861429836 4.776774023633361, -74.04029171631588 4.776207706321742, -74.03878364773318 4.774970066420818, -74.03800540233745 4.773666917161825, -74.03729177636662 4.771281485701648, -74.03727967636664 4.770004014298352, -74.03747549832134 4.769002476613728, -74.03843161386389 4.767199327773277, -74.04047532279198 4.75512284897233, -74.0369408023945 4.754256982815782, -74.03025007661371 4.753148101678661, -74.02876484883491 4.752415548061514, -74.02767764773319 4.751430166420819, -74.02692330233745 4.750171617161826, -74.02654087636664 4.748620285701648, -74.02683367636664 4.736912214298353, -74.02739999367826 4.73504531631587, -74.02863763357918 4.733537247733187, -74.03035817661373 4.732617598321339, -74.03229968570164 4.732426376366639, -74.03372301716183 4.732782902337444, -74.03534513390593 4.733866766094067, -74.03621920632175 4.73504531631587, -74.03676491551958 4.736773285680133, -74.04355019487681 4.738452884397855, -74.04767016881966 4.714185707761746, -74.04885077359798 4.706409648389919, -74.05027314410287 4.698677293675041, -74.05045487359796 4.696561148389919, -74.05077748485968 4.695365046361829, -74.05289107166563 4.682999393176747, -74.05422957359798 4.67404324838992, -74.05473458359565 4.671889824337649, -74.05543207359798 4.667273848389919, -74.05644319847762 4.664371152795165))'
polygon_3 = shapely.wkt.loads(poly_3_wkt)
poly_4_wkt = 'Polygon ((22.11315279161000547 -25.09231820047121886, 21.62718174901616663 -26.2204652636354929, 22.01769419395764515 -27.5308514677724574, 23.33675845242663982 -28.13831527101475416, 24.77731547154409597 -27.47010508744822488, 24.86409601486442256 -26.98413404485438605, 23.92686614700487624 -26.97545599052235232, 24.55168605891124045 -26.38534829594411946, 25.86207226304820495 -26.14236277464719649, 26.1918383276654545 -26.70643630622933529, 25.92281864337243391 -27.30522205513960188, 26.69516547892335723 -26.88867544720202218, 26.75591185924758975 -26.19443110063939528, 25.93149669770446764 -25.73449422104165407, 25.51495008976689149 -25.98615779667060366, 25.14179375348947687 -25.69978200371352273, 24.68185687389173566 -25.25720123277984541, 23.85744171234861355 -26.09029444865500125, 23.71859284303608462 -26.81925101254575949, 22.81607519250466964 -26.2204652636354929, 23.26733401777037713 -25.343981776100172, 23.17187542011801682 -24.90140100516649824, 22.77268492084450457 -24.55427883188518123, 22.11315279161000547 -25.09231820047121886),(22.46027496489132247 -25.79524060136588304, 22.01769419395764515 -26.19443110063939528, 22.2172894435943995 -26.38534829594411946, 22.45159691055928874 -26.48948494792850994, 22.55573356254368278 -26.53287521958867501, 22.49498718221945381 -26.75850463222153053, 22.92021184448906368 -26.68908019756526784, 22.33010414991082726 -26.32460191561988694, 22.5817677255397804 -26.02087001399873856, 22.93756795315312758 -25.3786939934283069, 22.81607519250466964 -25.343981776100172, 22.46027496489132247 -25.79524060136588304),(23.10245098546175413 -27.53952952210448757, 22.54705550821164906 -27.47010508744822488, 22.81607519250466964 -27.05355847951064874, 23.64049035404779175 -27.17505124015910667, 23.692558680039987 -27.59159784809668636, 23.18055347445005054 -27.85193947805767323, 23.10245098546175413 -27.53952952210448757),(24.24795415729009207 -26.20310915497142901, 24.36076886360651983 -25.94276752501044214, 24.70789103688783328 -25.95144557934247587, 24.81202768887222732 -25.95144557934247587, 24.77731547154409597 -25.78656254703384931, 25.0810473731652479 -25.91673336201434097, 25.07236931883321418 -26.10765055731906514, 24.65582271089563449 -26.15104082897923021, 24.34341275494245238 -26.38534829594411946, 24.24795415729009207 -26.20310915497142901))'
polygon_4 = shapely.wkt.loads(poly_4_wkt)

to_triangles(polygon_1)

Davena

Very nice solution, it was very useful to me. Just commenting to state that, according to warnings given by prior code, now all usages of the explode() function should pass the argument index_parts=True to avoid warnings (due to changes in the code to comply with pandas). – Narcose