Algorithm to find best fitting point on a plane

0
votes

I am working on a path finding system for my game that uses A* and i need to position the nodes in such a way that they would be within minimal distance from other points.

I wonder if there is an algorithm that would allow me to find best fitting point on a plane or a line (between neighboring points) as close as possible to the specified position, while maintaining minimal distance between the neighbors.

Basically i need an algorithm that given input (in pseudocode) min distance = 2, original position = 1, 1 and a set of existing points would do this:

points graph

In the example the shape is a triangle and the point can be calculated using Pythagoras theorem, but i need it to work for any shape.

1
algorithmcomputational-geometry
Why would you choose that point? I.e., how do you measure optimality? The given point has a total distance of 6.36 to all three neighbors. If you choose (1, 1), you get 5.89. What is the meaning of min distance? Is that the maximum distance from the initial point that you want to allow? – Nico Schertler

1 Answers

1
votes

Your problem seems uneasy. If you draw the "forbidden areas", they form a complex geometry made of the union of disks.

enter image description here

enter image description here

The there are two cases:

  • if the new point belongs to the allowed area, you are done;

  • otherwise you need to find the nearest allowed point.

It is easy to see if a point is allowed, by computing all distances. But finding the nearest allowed point seems more challenging. (By the way, this point could be very far.) If the target point lies inside a circle, the nearest candidate location might be the orthogonal projection on a circle, or the intersection between two circles. Compute all these points and check if they are allowed. Then keep the nearest candidate.

In red, the allowed candidates. In black the forbidden candidates.

enter image description here

For N points, this is an O(N³) process. This can probably be reduced by a factor N by means of computational geometry techniques, but at the price of high complexity.