Librcsc high level desired geometric implementations.

[fnalmeidap]

At rcsoccersim standard library (librcsc) there are a few high level useful geometric implementations that would be beneficial to have available across multiple leagues including Very Small Size, Small Size and Soccer Simulation 2D.

Convex Hull: It has the capability of identifying the minimal convex polygon within a specified collection of points that exists within a two-dimensional context. While it may be applicable in higher dimensions, two dimensions prove to be adequate for our purpose, which i believe mainly resides in path finding collision detection. See reference.

Voronoi diagram and Delaunay triangulation: These two representations are closely associated and either one can be derived from another, because the circumcenters of Delaunay triangles are the vertices of the Voronoi diagram. Soccer Simulation 2D strongly relies on these points for positioning purposes, it would be great to have our own implementation of it. See reference for Voronoi and Delaunay.

[joseviccruz]

We have a challenge. C.c.: @bcs5

[bcs5]

Adding some references: Slide from Unicamp with many resources abouts these problems

There are some well known algorithms for this problem, the most famous is the Delaunay O(nlog). But there are others:

• Most simple to understand algorithm: O(n^2) expected
• With halfplane intersection O(n^2 log), similar to above algorithm.
• Fortune`s O(nlog)

We should pick one for the number of points that we have to treat, some have heavy implementation and constants.

But I think that we can start implementing Convex Hull, its a easier code and we can use monotone chain algorithm.

We have to see whats is used today too, @joseviccruz must have done a good job too on VSSL.