# Algorithm for creating adjacent triangles

I have a system where you can click once to place a node in a scene. When you place 3 nodes, it forms a triangle. When you place any future nodes, it creates a new triangle by joining that node to the 2 nearest existing nodes.

This works fine most of the time but is flawed when used near triangles with very acute angles, because one of the 2 nearest nodes is often not one that should be used.

For example, see the image below. The magenta triangle is the first one placed. If I then click at the position marked X, what I get is a new triangle where the blue overlay is. What I want is a new triangle where the green overlay is. (ie. symmetrical to the magenta one, in this example. Clarification: The green and magenta triangles don't overlap - the green one extends under the blue one to the left-most node)

How can I determine which 2 existing vertices to use when creating new triangles so that triangles are not superimposed like this?

EDIT: Searching for the nearest edge gives better results, but not perfect ones. Consider this situation:

The 'nearest edge' test is ambiguous, and can return AB or AC (as the nearest point to X for both is at A). The desired result would be AC, to form the ACX triangle with no edges overlapping. How could I ensure this result? (I'd rather not have to perform individual edge overlap tests as a tie-breaker if possible as I'm concerned that the nearest edge test won't necessarily spot the 2 are exactly equidistant, given floating point precision issues.)

• Isn't it good enough to look at the last 5 vertices placed and select the two closest to the newly placed vertex? I would point you to the algorithms for triangle strips (codercorner.com/Strips.htm) but those often just use the last two or the last three skipping one. – Roy T. Jul 24 '12 at 17:27
• Is the green triangle overlapping the magenta one? What's the goal of this? Does the user need control over where and how triangles are created or would triangulation of a point-cloud be acceptable? – bummzack Jul 24 '12 at 17:34
• To put this in a graph context, essentially you want to connect your nodes, without any edges overlapping? (Assuming the magenta/green triangles would share an edge) – MichaelHouse Jul 24 '12 at 17:37
• Roy T: no - just picking the 2 closest is wrong, as I thought the example shows. Is something unclear? Bummzack - The green one doesn't overlap with the magenta one. The goal is to make a mesh or graph of these triangles. The user does need control, yes. Byte56 - yes, no edges should cross. – Kylotan Jul 24 '12 at 17:46
• Will the user actually see the individual triangles? Or is it going to be one continuous surface? – bummzack Jul 24 '12 at 18:06

Rather than finding the minimum distance to the nodes, find the minimum distance to the edge (ie the line segment defined by the nodes).

Then, if the nearest point is a vertex (which you'll have to use some floating point epsilon** test), compare the angle between the line from new point to the vertex and each of the edges connected to that vertex. Choose the one with the minimum absolute angle:

MinAngle(newPoint, vertex, edge1, edge2)
{
newEdgeUnit = norm(newPoint - vertex); // don't actually need to normalize this
edge1Unit = norm(edge1 - vertex);      // you probably have these from your dist to line tests
edge2Unit = norm(edge2 - vertex);

edge1Dot = dot(edge1Unit, newEdgeUnit);
edge2Dot = dot(edge2Unit, newEdgeUnit);

// you can simply compare dot products to find the minimum absolute angle
if (edge1Dot > edge2Dot) return edge1;     // set up this way so you can generalize to an array
return edge2;
}


** To avoid adding degenerate triangles, which might disrupt the epsilon test, you might want to put a region around each vertex where adding points is disallowed, (something like disallowing points within some multiple of the epsilon used above).

• +1 - this is IMHO a much more straightforward answer than the others, and more likely to provide the correct results. Distance-to-segment is easy to compute, too, with a smart scheme. – Steven Stadnicki Jul 24 '12 at 20:13
• Agreed, this is a cleaner method. Probably what I would have arrived at if I'd thought about it more :/ – MichaelHouse Jul 24 '12 at 22:36
• Ah, so close! But, as with Byte56's answer and Jimmy's diagram, sometimes there are 2 equidistant edges, and one of them violates the constraints. I've updated my question. – Kylotan Jul 25 '12 at 14:30
• @Kylotan Perhaps in that case, simply checking which one overlaps and taking the other option would do? Look for triangles sharing the edge you chose, and check if your new triangle is on the same side of that edge as the existing one. – Kevin Reid Jul 25 '12 at 15:13
• @Kylotan Do you ensure your triangles always have the same winding? If yes, you could rule out the edge that has a normal pointing away from your new vertex (using dot-product). – bummzack Jul 25 '12 at 15:48

After the first triangle is placed, when placing a new vertex, you will always generate two new edges. The third edge for the new triangle will always be a shared edge with a previous triangle. If you could find a way to determine the shared edge, you'd know which vertices to connect to, but that's the hard part. I believe one way you can do this by drawing a line from your new vertex to the center of each of the last three edges generated (or probably the 3 nearest edges).

If the line from your vertex to the center of the edge does not cross either of the other two edges, you have your shared edge. The shared edge will tell you which two vertices to connect your new vertex to.

Jimmy brought up the case for a point that is ambiguous as to where the new triangle would go like this:

That would give you the opportunity to choose between two valid triangles. Perhaps the tie breaking being which center point is closest.

Considering your update, while more complex, my solution will only result in a tie when you have two valid triangles. Using this method your second example image would produce the result you want.

• It's possible to have a situation where two of the lines do not intersect with edges (when X is closer to a vertex than it is to the edge) – Jimmy Jul 24 '12 at 19:30
• @Jimmy can you draw an image of such a situation? – MichaelHouse Jul 24 '12 at 20:38
• i.stack.imgur.com/iqLE8.png – Jimmy Jul 24 '12 at 20:41
• Ah yes, then you have two choices of where to put the triangle! Either side would work. Perhaps you can tie break with the one that has the shortest distance to the center. – MichaelHouse Jul 24 '12 at 20:43
• @Kylotan does this solution not work? You mentioned in a comment to Jeff that Jimmy's image has two cases and one violates the constraints, but that's not true. In Jimmy's image the two cases would both produce valid triangles using my method. – MichaelHouse Jul 27 '12 at 4:59

Having your magenta triangle ABC, you then incorporate a new vertex X. I think it is obvious that there will be two lines starting at D that will not intersect between any of the edges of the triangle ABC.

These two lines could be AX & BX, BX & CX or AX & CX. You can then treat your problem as the classical problem of "do two lines intersect"? You can then check which of this pairs of lines does not intersect with any of the ABC triangle edges following, for example, any of the methods from this question. Hence, you will have the two new edges of the new triangle.

• This seems good, but the way you've stated it seems to assume that there is only one existing triangle. How would it generalise to many? – Kylotan Jul 24 '12 at 17:48
• Hum... if your X and your triangle ABC are fixed, I guess there is only one, isn't it? – Dan Jul 24 '12 at 17:50
• The system creates a new triangle for every node after the 2nd one. – Kylotan Jul 24 '12 at 17:52
• Sorry, I misunderstood your question. Let me see how I can extend this to many triangles. – Dan Jul 24 '12 at 17:54
• Well I guess you could search the two closest vertices to X that don't cross any edge when connected to X? – bummzack Jul 24 '12 at 18:25

Figuring out if you're in one of the unambiguous regions (1, 2, 3 below), is fairly easy: treat each edge of your triangle as a 2D plane and test which side of the plane your new point is on. If you're inside two of them but outside one, then that one corresponds to the edge of the triangle that contributes two vertices to your new triangle.

If you're inside one and outside two, you're in the ambiguous case where the nearest part of the triangle to your new point is a corner. In that case, you can form a 2D plane from the midpoint of the opposite edge (the one that you're inside of) and the nearest vertex (the one shared by the two planes you're outside of). You can pick an edge depending on which side of this plane your new point is on.

Note that a plane test in 2D works the same way as in 3D: dot a vector from anywhere on the plane to your point with the plane's normal (in 2D, this is the line's perpendicular).

(Incidentally, the magenta-delimited regions in this image are called Voronoi regions; they're the areas of space containing points that are closest to a particular feature—edge or vertex—of the triangle. Edit: My terminology here isn't actually quite correct, these aren't exactly Voronoi regions.)

• It's not immediately clear to me how this generalises to multiple triangles in the scene - especially if the nearest feature is a vertex that may be shared by more than 1 triangle. – Kylotan Jul 25 '12 at 15:50
• @Kylotan Just run the algorithm for all the triangles, and pick the overall nearest feature. You need some tie-breaking logic no matter what. If you end up with the nearest feature being a shared vertex, then you should be in the edge-region (#1, #2, #3) for only one triangle, so maybe you can pick that? – John Calsbeek Jul 26 '12 at 5:07