Algorithm for creating adjacent triangles

Question

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.)

Answer 1

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).

Answer 2

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.

Answer 3

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.

Answer 4

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.)