Reduce dependence on Boost.Geometry

[mitukou1109]

Checklist

• I've read the contribution guidelines.
• I've searched other issues and no duplicate issues were found.
• I've agreed with the maintainers that I can plan this task.

Description

Currently, Autoware relies on Boost.Geometry for most geometric calculations. However, Boost's generic implementation is considered to extend the build time.
The goal of this task is to reduce the build time by minimizing (or eliminating) dependency on Boost.Geometry.

Purpose

This task aims to shorten the build time by reducing dependency on Boost.Geometry. This involves adding utility functions that compile independently of Boost and omitting unnecessary features for Autoware to improve function execution efficiency.

Possible approaches

The following functions are planned to be replaced:

• area() @mitukou1109
• convex_hull() @mitukou1109
• covered_by() @mitukou1109
• disjoint() @mitukou1109
• distance() @mitukou1109
• intersects() @mitukou1109
• within() @mitukou1109
• difference() @mraditya01
• union_() @mraditya01
• envelope() @mitukou1109
• simplify() @mitukou1109
• buffer() @mitukou1109

Definition of done

• All replaceable Boost.Geometry functions are migrated to self-implementations.
• Build and processing time are reduced compared to Boost.Geometry.

[mitukou1109]

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 polygons
covered_by()	278.20ms	946.09ms	check if each vertex of 500 polygons is covered by (= inside or on border of) another 500 polygons
disjoint()	195.58ms	180.81ms	check if 500 polygons are disjoint (runs totally 250,000 times)
intersects()	195.41ms	145.11ms	check if 500 polygons intersect (runs totally 250,000 times)
within()	842.81ms	120.63ms	check if each of 500 polygons is within 500 polygons

I will need to work on speeding up (especially for convex_hull() and covered_by()) before starting migration.

[mitukou1109]

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 each vertex of 500 polygons is covered by (= inside or on border of) another 500 polygons
disjoint()	198.91ms	77.51ms	check if 500 polygons are disjoint (runs totally 250,000 times)
intersects()	199.10ms	58.56ms	check if 500 polygons intersect (runs totally 250,000 times)
touches()	309.29ms	343.14ms	check if each vertex of 500 polygons touches (= on border of) another 500 polygons
within()	1058.86ms	55.80ms	check if each of 500 polygons is within 500 polygons

Now all functions except touches() work equally or faster than Boost's.

[mitukou1109]

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 concave polygons.
Is it OK to keep the current implementation or should I use convexity-independent algorithms?

[maxime-clem]

@mraditya01 is implementing a triangulation algorithm which allows to split any concave polygon into a set of convex polygons (triangles). This will allow using convex-only algorithms with any type of polygons. Of course the effect on performance will need to properly be investigated, and in some case it may be better to implement generic algorithms rather than use triangulation+convex algorithms.

[mitukou1109]

Now that @mraditya01 's #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.

[mitukou1109]

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.

[mitukou1109]

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.

[mitukou1109]

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

[mitukou1109]

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 self-intersections, which my implementation does not expect.
It will be fixed by #8995, and after the PR is merged, I will confirm every function works with random non-convex polygons. I've already added equivalence class and boundary value test cases and they are passing.

By #7778, #8592 and #8974, the following classes will be added:

Class	Geometry types	Notes
alt::Vector2d	vector
alt::Point2d	point	equivalent to alt::Vector2d
alt::Points2d	point set	equivalent to std::vector<alt::Point2d>
alt::PointList2d	ring, line	equivalent to std::list<alt::Point2d>
alt::Polygon2d	polygon	mutually convertible with autoware::universe_utils::Polygon2d
alt::ConvexPolygon2d	convex polygon	subclass of alt::Polygon2d

Note:

• Polygons have closing points (i.e. the last vertex in the list should match the first, as any polygon given is considered to be closed)
• Polygons can only be created by calling alt::Polygon2d::create(), and convex polygons by alt::ConvexPolygon2d::create().
  They are correct()-ed internally, and their convexity is checked as needed.

In addition, the following functions will be available without dependence on Boost.Geometry:

Function	Supported geometry types	Non-convex support
area()	ring / polygon	o
convex_hull()	point set	-
correct()	polygon	o
covered_by()	point & ring / point polygon	o
disjoint()	polygon & polygon	o
distance()	point & segment (2 edge points) / point & polygon	o
envelope()	polygon	o
equals()	point & point / polygon & polygon	o
intersects()	segment & segment / polygon & polygon	o
simplify()	line	-
touches()	point & segment / point & polygon	o
within()	point & ring / point & polygon / polygon & polygon	o

Note:

• All functions supporting non-convex polygons cannot be used for self-intersecting polygons. Some may work but possibly cause unintended behavior.