0
$\begingroup$

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:

enter image description here

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

enter image description here

Suppose that the user wants to place a point on the yellow area:

enter image description here

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:

enter image description here

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:

enter image description here

I came up with a possible solution.

enter image description here

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?

$\endgroup$
1
$\begingroup$

Don't add the point between the closest pair of points; add it between the endpoints of the closest edge.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.