Reduce dependence on Boost.Geometry

[mitukou1109]

Checklist

• [X] I've read the contribution guidelines.
• [X] I've searched other issues and no duplicate issues were found.
• [X] 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 is 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 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.

[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.