Fix findOpenCircles To Properly Handle The Field Constraint

[garethellis0]

Description of the task

Before reading this, please go read the implementation of findOpenCircles in geom/utils.cpp.

Currently, in findOpenCircles we just add the 4 corners of rectangle given to the Voronoi diagram and then find the largest open circle. This is incorrect, consider the case where the rectangle is the field and the points are enemy robots. Adding the corner points to the Voronoi diagram is like treating every corner as an enemy robot. Instead of doing this we should just construct the voronoi diagram from the given points, then treat all intersections of the Voronoi diagram with the edge of the rectangle as vertices. See this stackoverflow post:

https://stackoverflow.com/questions/34093602/efficient-algorithm-to-determine-largest-open-space

Having a math background would be helpful for this!

Acceptance criteria

• [ ] Add unit tests that show the failure case indicated in the description
• [ ] Fix findOpenCircles as per the description above

Blocked By

[matthewberends]

@garethellis0 Is it necessary for the entire circle to be within the defined rectangle?

For example, if my understanding is correct, adding a Voronoi vertex on boundary of the rectangle will lead to situations where half the circle is out of the rectangle yet it is still returned as a valid circle. Is this the desired functionality?

[garethellis0]

Yup! Really what we're trying to find here is the point in the field that is farthest from all the enemy robots. Consider the case where this point is in the corner of the field. In this case we want the center of the largest empty circle to be the corner.

Does that make sense? Apologies if it's a tad confusing. Lemme know and I can draw it out if need be.

[matthewberends]

Yeah that makes sense. Thanks