I have a closed 2D shape expressed as a list of points, like that:
[
{0, 5}, <-- {x, y}
{10, 5},
{15, 6},
...
]
The user has a canvas: each time he clicks on that canvas, a point will be appended to the list, and he will see the updated shape on screen.
How can insert the point between two nearest points instead of appending it to the list?
Let's say I have this shape:
All points got inserted counter-clockwise, starting from the first point to the left of the red one (meaning that the red one will be the last one):
Suppose that the user wants to place a point on the yellow area:
Right now the algorithm simply appends the new point to the list of existing points, so the new point will be inserted after point number 5, resulting in this shape:
Clearly I don't want this behaviour. I'd like the point to be inserted between points 3 and 4 instead, so that the result will be like that:
I came up with a possible solution.
Find distances between tuples and subtract them. The point's nearest tuple is the one with the minimum distances subtraction
Example:
d1 = abs(pink - blue)
d2 = abs(blue - green)
d3 = abs(green - red)
d4 = abs(red - yellow)
d5 = abs(yellow - pink)
Here, d2 will be the minimum, hence the point will be inserted between 3 and 4.
This approach however is buggy: if point 5 is a bit closer to the line between point 3 and 4, d3 will be the minimum, so the point would be inserted between points 4 and 5, which would be wrong.
Calculating areas of triangles instead of distances has the same issue.
I'm thinking there should be a way to take the segment distance into account. I mean, I would need to not only calculate distances between points, but also the new point's distance from the given segment. That way, I could tell that segment 3-4 is the nearest one, so I'll insert the point between 3 and 4.
So, what is an effective way to to handle this?
