Mitsuhiro Sakamoto

Here are the current benchmark results with 500 randomly generated polygons with 9 vertices: |function|Boost|self-impl.|task| |----|----|----|----| |`area()`|0.18ms|0.65ms|calculate the area of 500 polygons| |`convex_hull()`|1.93ms|4.59ms|calculate the convex hull of vertices of 500...

Latest benchmark results with 500 randomly generated polygons with 9 vertices: |function|Boost|self-impl.|task| |----|----|----|----| |`area()`|0.03ms|0.03ms|calculate the area of 500 polygons| |`convex_hull()`|0.38ms|0.32ms|calculate the convex hull of vertices of 500 polygons| |`covered_by()`|309.93ms|307.29ms|check if...

At this moment, the implementation assumes that polygons are convex. But considering that the purpose is to replace Boost.Geometry functions, it would be better for the alternatives to work with...

Now that @mraditya01 's https://github.com/autowarefoundation/autoware.universe/pull/8609 is merged, I'll begin working on supporting non-convex polygons. But first let me re-implement the triangulation algorithm without using Boost.Geometry.

I asked @mraditya01 to clean up the code of triangulation algorithm first. I'm working on adding `alt::Polygon2d` class that accepts non-convex polygons.

I added `alt::Polygon2d` class and modified some functions to support non-convex polygons. After @mraditya01 finishes refactoring I will make the existing geometry functions accept `Polygon2d` by triangulation.

#8965 enabled the triangulation function to be used with `alt::Polygon2d`. I'm now adding overloads of geometry functions to support concave polygons.

I finished working on #8974, but it cannot be merged since it is not fully tested yet. Currently, the concave polygon generator for random test occasionally creates a polygon with...

Below are not implemented yet: - `difference()` (@mraditya01) - `intersection()` (@mraditya01 ?) - `union_()` (@mraditya01) - `buffer()` (@mitukou1109 -> @mraditya01 ?)

This PR should be merged after #8995. Currently the random tests fail because the concave polygon generator occasionally creates self-intersections.