Expressing a line figure as a set of triangles

May 27, 2022 10:19 AM

Before I reinvent this triangular wheel I thought I'd see if there's already some code that does this. The figure will be an outline although there could be loops (an 8 for example). Failing an existing algorithm, if you have a clever idea feel free to share. The more the merrier!
posted by Tell Me No Lies to Computers & Internet (14 answers total)

What is "this"? The picture does not define what you're trying to do. In the lower picture there is one vertex with three lines leading to it, one with one, and two with zero. The rest have two. There's no pattern to this.
posted by caek at 10:24 AM on May 27, 2022

Best answer: There are a bunch of algorithms for this, though it's not something I have dealt with much myself so I have no specific recommendation there. But for the purpose of further searching, the term you want is in fact triangulation. There are absolutely going to be libraries out there that do it; do you have a particular language/platform context you're hoping to work in?
posted by cortex at 10:25 AM on May 27, 2022 [6 favorites]

Best answer: Earcut is one Javascript implementation of a particular tessellation or triangulation algorithm. The README describes and references others, as well, for comparison of performance. The linked papers may help with researching the larger family of tessellation/triangulation algorithms, as well as implementations in your desired language.
posted by They sucked his brains out! at 10:26 AM on May 27, 2022 [1 favorite]

Best answer: In mathematics this is known as a "triangulation", and in general there is not a unique way to do it. For instance, there are two possible triangulations of a square:

-----
|\  |
| \ |
|  \|
-----

vs

-----
|  /|
| / |
|/  |
-----

There are algorithms for special cases, as you can see on that wiki page.
posted by number9dream at 10:27 AM on May 27, 2022 [4 favorites]

I know Blender has some tools essentially for carving up an n-gon face into quads or tris. Can't recall the exact process off the top but have done as much when 3d modelling before.
posted by GoblinHoney at 10:31 AM on May 27, 2022 [1 favorite]

It's also worth keeping in mind the scale of the stuff you want to triangulate, as far as whether or how much to worry about efficiency of any given algorithm; if it's all fairly small figures the computational complexity is gonna be really minimal for basically any approach so just finding something that works is a good plan vs. trying to minmax things or choose juuuuust the right implementation, etc. Unless the joy is *in* sweating the details in which case go wild and enjoy it. (For few, small figures this is the sort of thing I would enjoy doing by hand and involving random processes, but if it's either not few or not small that way lies madness.)
posted by cortex at 10:36 AM on May 27, 2022 [1 favorite]

I have done this in QGIS/Grass using the Voronoi tools but found with thin/tortuos shapes it is necessary to buffer the shape to achieve a meaningful division - the incut will make many algos fail, buffering to produce a convex hull may solve failures. Go to last answer here on gis.stackexchange for example.

IDK how large your area is but if very small [whatever very small means in your context] you may find scaling up and running an algorithm (and then rescaling) produces a more accurate result - I know this to be the case for e.g sketchup.
posted by unearthed at 11:06 AM on May 27, 2022

Response by poster: What is "this"?

I have a closed line figure, an outline. I want to reproduce the figure by building it with triangles.

I’m sorry, between the title and that I’m not sure how else to explain it.
posted by Tell Me No Lies at 11:10 AM on May 27, 2022

Response by poster: There are absolutely going to be libraries out there that do it; do you have a particular language/platform context you're hoping to work in?

Python is preferred, but I’m flexible.

It's also worth keeping in mind the scale of the stuff you want to triangulate, as far as whether or how much to worry about efficiency of any given algorithm

It’s a bit of an open question. The original figures I’m working with have smooth curves that I’m boiling down to sets of really small edges. It’s going to take some trial and error to figure out how fine the resolution needs to be.
posted by Tell Me No Lies at 11:23 AM on May 27, 2022

Python is preferred, but I’m flexible.

scipy has an implementation of Delaunay triangulation, which is one of the basic methods. There's also a handy function that will plot that triangulation using matplotlib.
posted by jedicus at 11:38 AM on May 27, 2022

PyMesh is another implementation.
posted by jedicus at 11:43 AM on May 27, 2022

I have a closed line figure, an outline. I want to reproduce the figure by building it with triangles.

That makes sense. If you have no preference other than "it should be made of triangles" then that makes things simpler. If not, the problem you're going to run into is that there is not a unique solution to that problem, for a general line figure, so the best approach depends on which of the many possible triangulations you want.
posted by caek at 2:45 PM on May 27, 2022

Best answer: Some of my reading on making Voronoi networks brought up controlling the direction of polygon traversal ie clockwise or anticlock to simplify the problem (or direct output), I believe for some software direction is arbitrary unless user-directed.

Also just found the "Triangulation Template Library" (TTL)" while writing the above.


TTL features in this (paywalled) paper
Programming Triangulations: The Triangulation Template Library (TTL).
posted by unearthed at 1:40 PM on May 28, 2022

Response by poster: Thank you everyone for the pointers. After a number of false starts I've settled on the Python 'triangle' package. The documentation isn't great, but it's a shim over an older C Delaunay implementation that has docs of a sort.

The primary reason for false starts was either very limited or no support for constraints. If you want anything beyond a field of vertices and an auto-generated convex hull you can filter out a lot of packages up front.
posted by Tell Me No Lies at 9:32 PM on May 29, 2022