Find a point further from other points

Question

I am trying to create an “escape” algorithm and would like to first find points that are “safe”. That is, the points where they are relatively distant from other points.

This is 2D (not so important) and occurs within a fixed-size circle.

I assume that the sum of the squared distances will create a good initial equation, with the result that the highest result will be the farthest.

As for the choice of points, I do not think that it would be possible to solve for X, Y, but approximation is enough.

I did some reading and decided that in order to cover the area of ​​the circle, you will need 7 half circles (with the centers forming the hexadecimal and the seventh in the center)

I could iterate over them, all of which are within the circle. Since I choose the best scoring area, I could continue to divide them into 7 areas. Of course, excluding any points that go beyond the original circle.

Then I could iterate to the desired precision or the desired level.

To broaden the approach, it is assumed that it takes time to reach a location, and although the location can be safe, there cannot be a trip between them. How can I include distance in the equation so that I come to a good solution.

I suppose I could direct the distance to a new point and multiply it by the score, and repeat from there. This will greatly contribute to the local location, but I think this is good behavior. He would try to allow a safe place near, and then, when recounting, he could find outs and continue to hide in safety.

Any thoughts on this, or has this problem been done before? I could not find this problem specifically when I looked.

EDIT:

I introduced the C # implementation in Fortune Algorithm, and also added a few points around my points to create a pseudo-circular constraint, since I don’t understand the algorithm enough to manually configure it.

Now I understand that the blue lines create a path between the nodes. I can use the length of these and the distance between the surrounding points to calculate the path (travel time and danger) and weigh this with security (the empty circle that he is trying to get to) to determine what is the best course of action. By playing with how they interact, I can eliminate most of the work that I would have to do just using voronoi. Also my spawning algorithm will use this now to determine the LEC and spawn in this place.

Answer 1

You can take the convex hull of your set of places - the vertices of the convex hull will provide you with a set of "farthest" points. Then take centroid from the points from which you run away, then determine which vertex of the convex hull is the farthest from the center of gravity, you can speed it up, for example, by dividing the playing field into quadrants - you only need to check the vertices that are in the farther quadrant (for example, if the centroid is in the positive-positive quadrant, then you only need to check the vertices in the negative-x-negative quadrant); if the playing field has an irregular shape, this may not be an option.

As an alternative to fleeing to the farthest point, if you have a starting point from which you are running away (for example, the glasses you are running from are enemies and the player’s character is currently at point X, which means his starting point) then instead of the player running to the farthest point, you can instead follow the path that most quickly takes them from the center of gravity of the enemies - draw a beam from the centroid of the enemies through the player’s place, and this beam gives you the direction in which the player must run.

If the player’s character is surrounded, then both of these algorithms will give meaningless results, but in this case the player’s character has no viable options at all.