Return to Revisions

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