There is a broken line defined as a set of points. I am trying to come up with an algorithm for inserting a new point into this curve. I just can't figure out how to determine the insertion position.

The first thought was to consider the triangles that the new point and the pair of existing neighboring points form, and choose the triangle with the smallest perimeter. However, for such a case the algorithm considers it necessary to insert a new point between the first and second. Although the second and third are clearly better suited.

I also thought to consider the same triangles, and choose with the smallest height. But even here the algorithm will work incorrectly in certain situations. For example here

the algorithm will choose a position between points 3 and 4, together 1 and 2.

To exclude such cases, I decided to consider only triangles with acute angles at the base. But here there were exceptions.

Both candidate triangles have obtuse angles at the base.

In general, I'm at a dead end. Surely this problem has some kind of solution, or at least a name that you can google. After all, people write all sorts of autocodes and the like.

  • one
    Well, actually it is not a curve, but figs with it :) Could you somehow formulate an insertion criterion? Just something is not very clear what exactly you want to achieve. A new point is set, and you need to specify between which points it should be? or do you calculate the coordinates of the new point? - Harry
  • one
    I would consider the condition of the minimum change in the length of the polyline after inserting the point as the main one. - Igor
  • one
    @ Alexander Muksimov , my boss will never approve of this) It’s better not to disturb the user once again - yrHeTaTeJlb
  • one
    And here you do not need to strain the user - the user puts the dot on the broken line with the mouse and pulls it where it needs to. - Alexander Muksimov
  • 3
    The task is formulated meaninglessly, or rather not formulated at all. There is no unique or "natural" way to insert a point in a polyline. Therefore, a clear optimization criteria has not yet been formulated, or at least more or less meaningful wishes regarding the result, there is nothing to talk about. - AnT

1 answer 1

I would consider the condition of the minimum change in the length of the polyline after inserting the point as the main one.

Only it is necessary to decide whether to look at an absolute increase in length, or in relation to the segment that is replaced by two.

  • I counted the old - (new + new) . The best option always gave the minimum value. Anyway, I couldn’t think of a situation when such an algorithm would work incorrectly - yrHeTaTeJlb
  • Another possible metric, the change in the sum of the angles, tends to the smallest. It may also be worth blocking self-intersections. - Kromster