linuxlewis/tripy

Simple polygon triangulation algorithms in pure python

tripy

Tripy is a simple module with one purpose: triangulating polygons.

Getting Started

pip install tripy

import tripy
# Polygon can be clockwise or counter-clockwise
polygon = [(0,1), (-1, 0), (0, -1), (1, 0)]
triangles = tripy.earclip(polygon)
print triangles
[((1, 0), (0, 1), (-1, 0)), ((1, 0), (-1, 0), (0, -1))]

Examples

To see examples of tripy in action check out the jupyter notebook examples.ipynb

Roadmap

0.1

• Support polygons with holes

0.2

• Implement Seidel's triangulation

tripy's Issues

Tripy-1.0.0 unable to process polygons supported in version 0.0.3

Hi,

We discovered with some colleagues by using different version of tripy that it was not able anymore to process some polygons that were supported in version 0.0.3.

Here is an example to reproduce the case.

import shapely.wkt
import numpy as np
import tripy
import matplotlib.pyplot as plt

if __name__ == '__main__':
    polygon = shapely.wkt.loads("POLYGON ((2.3374803 48.87445059972346, 2.3374866 48.87444049972347, 2.3375329 48.87436569972348, 2.3375717 48.8743029997235, 2.3376836 48.87433219972348, 2.3378011 48.87436279972348, 2.3377983 48.87436709972348, 2.3377661 48.87441459972347, 2.337753 48.87441159972347, 2.3377382 48.87443419972345, 2.337751 48.87443809972346, 2.3377694 48.87443419972345, 2.3379195 48.87447389972345, 2.3380046 48.87471509972338, 2.3379528 48.87472209972339, 2.3379554 48.87472929972338, 2.337902 48.87473809972339, 2.3379056 48.87474939972338, 2.3377288 48.87477829972337, 2.3377241 48.87476549972337, 2.3376082 48.87478359972337, 2.3376066 48.87477919972339, 2.3375998 48.87478029972337, 2.337577099999999 48.87472049972339, 2.3374907 48.87473379972338, 2.3374961 48.87459949972342, 2.3374982 48.87454969972343, 2.3375389 48.87454889972344, 2.3375331 48.87447659972346, 2.3374803 48.87445059972346))")

    poly_coords = np.array(polygon.exterior.coords)
    tris = tripy.earclip(poly_coords)
    for t in np.array(tris):
        plt.plot(t[[0, 1, 2, 0], 0], t[[0, 1, 2, 0], 1])

    plt.plot(poly_coords[:, 0], poly_coords[:, 1], 'k-', lw=3)
    plt.show()

It produces the following images:

tripy-0.0.3	tripy-1.0.0

As you can see in the second images, tripy was not able to produce any triangles.

I was reading the PR #2 and saw that you introduced some changes to handle some edge cases.

Is this a side effect ? Should the library be able to process this polygon (or not) ?
Should it at least produce some of the triangles ?

Issue with EPSILON

Nice and smart.
However I have now the case that tripy is NOT creating trias because testing the area if vertices are inside fails because the area is bigger than EPSILON. Setting EPSILON to half it value seems to work...
But not sure if this is really a valid solution. Or checking if vertices are inside by other methods....

Not all triangles are correct

I'm not sure why this happens, here's some code that causes the bug. I'm using python 3.6, and the latest version from github of tripy.

import numpy as np
import tripy
import matplotlib.pyplot as plt
%matplotlib inline

poly = np.array([[ 229.28340553,   78.91250014],
       [ 258.42948809,   17.98278109],
       [ 132.01956999,  -22.96900817],
       [ 107.97774096,   23.39276058],
       [  65.85573925,   28.63846858],
       [  41.66373597,  -92.78859248],
       [  -5.59948763,  -54.18987786],
       [ -44.61508682,  -69.7461117 ],
       [ -28.41208894, -106.93810071],
       [ -71.11899145, -125.56044277],
       [-100.84787818,  -88.51853387],
       [-211.53564549, -160.76853269],
       [-244.22754588, -147.51172179],
       [-226.83717643,  -42.0984372 ],
       [-230.65279618,  -10.5455196 ],
       [-240.50239817,   70.87826746],
       [ -12.48219264,  137.70176109],
       [   4.65848369,  204.21077075],
       [ 176.5243417 ,  193.73497584],
       [ 171.13537712,   87.27009315],
       [ 229.28340553,   78.91250014]])

tuplepoly = [tuple(p) for p in poly]
tris = tripy.earclip(tuplepoly)
for t in np.array(tris):
    plt.plot(t[[0,1,2,0],0],t[[0,1,2,0],1])
    
plt.plot(poly[:,0],poly[:,1],'k-',lw=3)

Some triangles are wrongly selected I think.
I tried making the polygon open (i.e. left the last point off), and I've also tried using the numpy array directly, and not turn it into an array of tuples. -- neither had any effect.

I found that weirdly, when using the data this came from directly, it worked. But if I transformed the array in some way it failed as above. I don't understand why that would happen...

OK, this polygon also reproduces the problem:

poly = np.array([[ 229, 78],[66, 28.7],[-244.2, -147.5],[-226, -42],[ 229, 78]])

But I found that the problem goes away if I scale the polygon by 1000, e.g.:

poly = np.array([[ 229, 78],[66, 28.7],[-244.2, -147.5],[-226, -42],[ 229, 78]])*1000

I get that there might be problems if the polygon have very weirdly narrow or zero area sections (or worse) but I think this polygon is fairly reasonable. The first polygon at the top of this issue is from the UK output area boundaries for the census.

(by the way, thanks for the module!)

3D possible?

Hi!
Is it possible to add a third dimension to the function?(z height)
Something like:
polygon = [(0,1,2), (-1, 0, 2.5), (0, -1, 2.5), (1, 0, 2)]

I tried it but get the error:
triangles = tripy.earclip(polygon)

 File "C:\Users\SEKRSV\AppData\Local\Programs\Python\Python36\lib\site-packages\tripy.py", line 30, in earclip
    polygon = [Point(*point) for point in polygon]
  File "C:\Users\SEKRSV\AppData\Local\Programs\Python\Python36\lib\site-packages\tripy.py", line 30, in <listcomp>
    polygon = [Point(*point) for point in polygon]
TypeError: __new__() takes 3 positional arguments but 4 were given