Function autoware_utils_geometry::triangulate(const alt::Polygon2d&)

Function Documentation

std::vector<alt::ConvexPolygon2d> autoware_utils_geometry::triangulate(const alt::Polygon2d &polygon)

triangulates a polygon into convex triangles

simplifies a concave polygon, with or without holes, into a set of triangles the size of the points vector at the end of the perform_triangulation algorithm is described as follow:

  • outer_points: Number of points in the initial outer linked list.

  • hole_points: Number of points in all inner polygons.

  • 2 * n_holes: Additional points for bridging holes, where n_holes is the number of holes. the final size of points vector is: outer_points + hole_points + 2 * n_holes.

Returns:

A vector of convex triangles representing the triangulated polygon.