Namespaces
	bounding_box
	Functions and types for generating enclosing bounding boxes around a set of points.

	details
	Contains computation geometry functions not intended for the end user to directly use.

	point_adapter
	Temporary namespace for point adapter methods, for use with nonstandard point types.

	spatial_hash
	All objects related to the spatial hash data structure for efficient near neighbor lookup.

Classes
class	Interval
	Data structure to contain scalar interval bounds. More...

Typedefs
using	Point = geometry_msgs::msg::Point32

typedef Interval< autoware::common::types::float64_t >	Interval_d

typedef Interval< autoware::common::types::float32_t >	Interval_f

Functions
template<typename T1 , typename T2 , typename T3 >
auto	ccw (const T1 &pt, const T2 &q, const T3 &r)
	compute whether line segment rp is counter clockwise relative to line segment qp More...

template<typename T1 , typename T2 >
auto	cross_2d (const T1 &pt, const T2 &q)
	compute p x q = p1 * q2 - p2 * q1 More...

template<typename T1 , typename T2 >
auto	dot_2d (const T1 &pt, const T2 &q)
	compute p * q = p1 * q1 + p2 * q2 More...

template<typename T >
T	minus_2d (const T &p, const T &q)
	Compute the 2d difference between two points, p - q. More...

template<typename T >
T	minus_2d (const T &p)
	The unary minus or negation operator applied to a single point's 2d fields. More...

template<typename T >
T	plus_2d (const T &p, const T &q)
	The 2d addition operation, p + q. More...

template<typename T >
T	times_2d (const T &p, const float32_t a)
	The scalar multiplication operation, p * a. More...

template<typename T >
T	intersection_2d (const T &pt, const T &u, const T &q, const T &v)
	solve p + t * u = q + s * v Ref: https://stackoverflow.com/questions/563198/ whats-the-most-efficent-way-to-calculate-where-two-line-segments-intersect More...

template<typename T >
void	rotate_2d (T &pt, const float32_t cos_th, const float32_t sin_th)
	rotate point given precomputed sin and cos More...

template<typename T >
T	rotate_2d (const T &pt, const float32_t th_rad)
	rotate by radian angle th in z direction with ccw positive More...

template<typename T >
T	get_normal (const T &pt)
	compute q s.t. p T q, or p * q = 0 This is the equivalent of a 90 degree ccw rotation More...

template<typename T >
auto	norm_2d (const T &pt)
	get magnitude of x and y components: More...

template<typename T >
T	closest_segment_point_2d (const T &p, const T &q, const T &r)
	Compute the closest point on line segment p-q to point r Based on equations from https://stackoverflow.com/a/1501725 and http://paulbourke.net/geometry/pointlineplane/. More...

template<typename T >
T	closest_line_point_2d (const T &p, const T &q, const T &r)
	Compute the closest point on the line going through p-q to point r. More...

template<typename T >
auto	point_line_segment_distance_2d (const T &p, const T &q, const T &r)
	Compute the distance from line segment p-q to point r. More...

template<typename T >
T	make_unit_vector2d (float th)
	Make a 2D unit vector given an angle. More...

template<typename T >
bool	is_left_of_line_2d (const T &p1, const T &p2, const T &q)
	Check if the given point is strictly to the left of the infinite line passing from p1 to p2. Logic based on http://geomalgorithms.com/a01-_area.html#isLeft() More...

template<typename IT >
bool	all_ccw (const IT begin, const IT end) noexcept

template<typename IT >
auto	area_2d (const IT begin, const IT end) noexcept

template<typename IT >
auto	area_checked_2d (const IT begin, const IT end)

template<typename T1 , typename T2 >
auto	dot_3d (const T1 &pt, const T2 &q)
	compute p * q = p1 * q1 + p2 * q2 + p3 * 13 More...

template<typename PointT >
std::list< PointT >::const_iterator	convex_hull (std::list< PointT > &list)
	A static memory implementation of convex hull computation. Shuffles points around the deque such that the points of the convex hull of the deque of points are first in the deque, with the internal points following in an unspecified order. More...

template<typename Iter1 , typename Iter2 >
std::vector< std::vector< typename std::iterator_traits< Iter1 >::value_type > >	hull_pockets (const Iter1 polygon_start, const Iter1 polygon_end, const Iter2 convex_hull_start, const Iter2 convex_hull_end)
	Compute a list of "pockets" of a simple polygon (https://en.wikipedia.org/wiki/Simple_polygon), that is, the areas that make up the difference between the polygon and its convex hull. This currently has a bug: More...

template<typename Iter >
bool	intersect (const Iter begin1, const Iter end1, const Iter begin2, const Iter end2)
	Check if polyhedra defined by two given sets of points intersect. More...

Typedef Documentation

◆ Interval_d

typedef Interval<autoware::common::types::float64_t> autoware::common::geometry::Interval_d

◆ Interval_f

typedef Interval<autoware::common::types::float32_t> autoware::common::geometry::Interval_f

◆ Point

using autoware::common::geometry::Point = typedef geometry_msgs::msg::Point32

Function Documentation

◆ all_ccw()

template<typename IT >

bool autoware::common::geometry::all_ccw	(	const IT	begin,
		const IT	end
	)

noexcept

Check if all points are CCW in x-y plane: This function does not check for convexity

Template Parameters

IT	Iterator type pointing to a point containing float x and float y

Parameters

[in]	begin	Beginning of point sequence
[in]	end	one past the last of the point sequence

Returns: Whether or not all point triples p_i, p_{i+1}, p_{i+2} are ccw

◆ area_2d()

template<typename IT >

auto autoware::common::geometry::area_2d	(	const IT	begin,
		const IT	end
	)

noexcept

Compute the area of a convex hull, points are assumed to be in CCW order

Template Parameters

IT	Iterator type pointing to a point containing float x and float y

Parameters

[in]	begin	Iterator pointing to the beginning of the polygon points
[in]	end	Iterator pointing to one past the last of the polygon points

Returns: The area of the polygon, in squared of whatever units your points are in

◆ area_checked_2d()

template<typename IT >

auto autoware::common::geometry::area_checked_2d	(	const IT	begin,
		const IT	end
	)

Compute area of convex hull, throw if points are not in CCW order (convexity check is not implemented)

Exceptions

std::domain_error if points are not in CCW order

Template Parameters

IT	Iterator type pointing to a point containing float x and float y

Parameters

[in]	begin	Iterator pointing to the beginning of the polygon points
[in]	end	Iterator pointing to one past the last of the polygon points

Returns: The area of the polygon, in squared of whatever units your points are in

◆ ccw()

template<typename T1 , typename T2 , typename T3 >

auto autoware::common::geometry::ccw	(	const T1 &	pt,
		const T2 &	q,
		const T3 &	r
	)

inline

compute whether line segment rp is counter clockwise relative to line segment qp

Template Parameters

T1,T2,T3 point type. Must have point adapters defined or have float members x and y

Parameters

[in]	pt	shared point for both line segments
[in]	r	point to check if it forms a ccw angle
[in]	q	reference point

Returns: whether angle formed is ccw. Three collinear points is considered ccw

◆ closest_line_point_2d()

template<typename T >

T autoware::common::geometry::closest_line_point_2d	(	const T &	p,
		const T &	q,
		const T &	r
	)

inline

Compute the closest point on the line going through p-q to point r.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	p	First point defining the line
[in]	q	Second point defining the line
[in]	r	Reference point to find the closest point to

Returns: Closest point on line p-q to point r

Exceptions

std::runtime_error if the two points coincide and hence don't uniquely

◆ closest_segment_point_2d()

template<typename T >

T autoware::common::geometry::closest_segment_point_2d	(	const T &	p,
		const T &	q,
		const T &	r
	)

inline

Compute the closest point on line segment p-q to point r Based on equations from https://stackoverflow.com/a/1501725 and http://paulbourke.net/geometry/pointlineplane/.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	p	First point defining the line segment
[in]	q	Second point defining the line segment
[in]	r	Reference point to find the closest point to

Returns: Closest point on line segment p-q to point r

◆ convex_hull()

template<typename PointT >

std::list<PointT>::const_iterator autoware::common::geometry::convex_hull ( std::list< PointT > & list )

A static memory implementation of convex hull computation. Shuffles points around the deque such that the points of the convex hull of the deque of points are first in the deque, with the internal points following in an unspecified order.

The head of the deque will be the point with the smallest x value, with the other points following in a counter-clockwise manner (from a top down view/facing -z direction). If the point list is 3 or smaller, nothing is done (e.g. the ordering result as previously stated does not hold).

Parameters

[in,out] list A list of nodes that will be reordered into a ccw convex hull

Returns: An iterator pointing to one after the last point contained in the hull

Template Parameters

PointT Type of a point, must have x and y float members

◆ cross_2d()

template<typename T1 , typename T2 >

auto autoware::common::geometry::cross_2d	(	const T1 &	pt,
		const T2 &	q
	)

inline

compute p x q = p1 * q2 - p2 * q1

Template Parameters

T1,T2 point type. Must have point adapters defined or have float members x and y

Parameters

[in]	pt	first point
[in]	q	second point

Returns: 2d cross product

◆ dot_2d()

template<typename T1 , typename T2 >

auto autoware::common::geometry::dot_2d	(	const T1 &	pt,
		const T2 &	q
	)

inline

compute p * q = p1 * q1 + p2 * q2

Template Parameters

T1,T2 point type. Must have point adapters defined or have float members x and y

Parameters

[in]	pt	first point
[in]	q	second point

Returns: 2d scalar dot product

◆ dot_3d()

template<typename T1 , typename T2 >

auto autoware::common::geometry::dot_3d	(	const T1 &	pt,
		const T2 &	q
	)

inline

compute p * q = p1 * q1 + p2 * q2 + p3 * 13

Template Parameters

T1,T2 point type. Must have point adapters defined or have float members x, y and z

Parameters

[in]	pt	first point
[in]	q	second point

Returns: 3d scalar dot product

◆ get_normal()

template<typename T >

T autoware::common::geometry::get_normal ( const T & pt )

inline

compute q s.t. p T q, or p * q = 0 This is the equivalent of a 90 degree ccw rotation

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in] pt point to get normal point of

Returns: point normal to p (unnormalized)

◆ hull_pockets()

template<typename Iter1 , typename Iter2 >

std::vector<std::vector<typename std::iterator_traits<Iter1>::value_type> > autoware::common::geometry::hull_pockets	(	const Iter1	polygon_start,
		const Iter1	polygon_end,
		const Iter2	convex_hull_start,
		const Iter2	convex_hull_end
	)

Compute a list of "pockets" of a simple polygon (https://en.wikipedia.org/wiki/Simple_polygon), that is, the areas that make up the difference between the polygon and its convex hull. This currently has a bug:

Parameters

[in]	polygon_start	Start iterator for the simple polygon (has to be on convex hull)
[in]	polygon_end	End iterator for the simple polygon
[in]	convex_hull_start	Start iterator for the convex hull of the simple polygon
[in]	convex_hull_end	End iterator for the convex hull of the simple polygon

Returns: A vector of vectors of the iterator value type. Each inner vector contains the points for one pocket. We return by value instead of as iterator pairs, because it is possible that the edge connecting the final point in the list and the first point in the list is part of a pocket as well, and this is awkward to represent using iterators into the original collection.

Template Parameters

Iter1	Iterator to a point type
Iter2	Iterator to a point type (can be the same as Iter1, but does not need to be)

◆ intersect()

template<typename Iter >

bool autoware::common::geometry::intersect	(	const Iter	begin1,
		const Iter	end1,
		const Iter	begin2,
		const Iter	end2
	)

Check if polyhedra defined by two given sets of points intersect.

Template Parameters

Iter	Iterator over point-types that must have point adapters

Parameters

[in]	begin1	Start iterator to first list of point types
[in]	end1	End iterator to first list of point types
[in]	begin2	Start iterator to first list of point types
[in]	end2	End iterator to first list of point types

Returns: true if the boxes collide, false otherwise.

◆ intersection_2d()

template<typename T >

T autoware::common::geometry::intersection_2d	(	const T &	pt,
		const T &	u,
		const T &	q,
		const T &	v
	)

inline

solve p + t * u = q + s * v Ref: https://stackoverflow.com/questions/563198/ whats-the-most-efficent-way-to-calculate-where-two-line-segments-intersect

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	pt	anchor point of first line
[in]	u	direction of first line
[in]	q	anchor point of second line
[in]	v	direction of second line

Returns: intersection point

Exceptions

std::runtime_error if lines are (nearly) collinear or parallel

◆ is_left_of_line_2d()

template<typename T >

bool autoware::common::geometry::is_left_of_line_2d	(	const T &	p1,
		const T &	p2,
		const T &	q
	)

inline

Check if the given point is strictly to the left of the infinite line passing from p1 to p2. Logic based on http://geomalgorithms.com/a01-_area.html#isLeft()

Template Parameters

T	T point type. Must have point adapters defined or have float members x and y

Parameters

p1	point 1 laying on the infinite line
p2	point 2 laying on the infinite line
q	point to be checked against the line

Returns: True if q is strictly to the left of infinite line through p1-p2. False otherwise

◆ make_unit_vector2d()

template<typename T >

T autoware::common::geometry::make_unit_vector2d ( float th )

inline

Make a 2D unit vector given an angle.

Template Parameters

T	Point type. Must have point adapters defined or have float members x and y

Parameters

th	Angle in radians

Returns: Unit vector in the direction of the given angle.

◆ minus_2d() [1/2]

template<typename T >

T autoware::common::geometry::minus_2d ( const T & p )

The unary minus or negation operator applied to a single point's 2d fields.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in] p The left hand side

Returns: A point with the negation in the x and y fields, all other fields are default initialized

◆ minus_2d() [2/2]

template<typename T >

T autoware::common::geometry::minus_2d	(	const T &	p,
		const T &	q
	)

Compute the 2d difference between two points, p - q.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	p	The left hand side
[in]	q	The right hand side

Returns: A point with the difference in the x and y fields, all other fields are default initialized

◆ norm_2d()

template<typename T >

auto autoware::common::geometry::norm_2d ( const T & pt )

inline

get magnitude of x and y components:

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in] pt point to get magnitude of

Returns: magitude of x and y components together

◆ plus_2d()

template<typename T >

T autoware::common::geometry::plus_2d	(	const T &	p,
		const T &	q
	)

The 2d addition operation, p + q.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	p	The left hand side
[in]	q	The right hand side

Returns: A point with the sum in the x and y fields, all other fields are default initialized

◆ point_line_segment_distance_2d()

template<typename T >

auto autoware::common::geometry::point_line_segment_distance_2d	(	const T &	p,
		const T &	q,
		const T &	r
	)

inline

Compute the distance from line segment p-q to point r.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	p	First point defining the line segment
[in]	q	Second point defining the line segment
[in]	r	Reference point to find the distance from the line segment to

Returns: Distance from point r to line segment p-q

◆ rotate_2d() [1/2]

template<typename T >

T autoware::common::geometry::rotate_2d	(	const T &	pt,
		const float32_t	th_rad
	)

inline

rotate by radian angle th in z direction with ccw positive

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	pt	reference point to rotate
[in]	th_rad	angle by which to rotate point

Returns: rotated point

◆ rotate_2d() [2/2]

template<typename T >

void autoware::common::geometry::rotate_2d	(	T &	pt,
		const float32_t	cos_th,
		const float32_t	sin_th
	)

inline

rotate point given precomputed sin and cos

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in,out]	pt	point to rotate
[in]	cos_th	precomputed cosine value
[in]	sin_th	precompined sine value

◆ times_2d()

template<typename T >

T autoware::common::geometry::times_2d	(	const T &	p,
		const float32_t	a
	)

The scalar multiplication operation, p * a.

Template Parameters

T	point type. Must have point adapters defined or have float members x and y

Parameters

[in]	p	The point value
[in]	a	The scalar value

Returns: A point with the scaled x and y fields, all other fields are default initialized

Namespaces

Classes

Typedefs

Functions

Typedef Documentation

◆ Interval_d

◆ Interval_f

◆ Point

Function Documentation

◆ all_ccw()

◆ area_2d()

◆ area_checked_2d()

◆ ccw()

◆ closest_line_point_2d()

◆ closest_segment_point_2d()

◆ convex_hull()

◆ cross_2d()

◆ dot_2d()

◆ dot_3d()

◆ get_normal()

◆ hull_pockets()

◆ intersect()

◆ intersection_2d()

◆ is_left_of_line_2d()

◆ make_unit_vector2d()

◆ minus_2d() [1/2]

◆ minus_2d() [2/2]

◆ norm_2d()

◆ plus_2d()

◆ point_line_segment_distance_2d()

◆ rotate_2d() [1/2]

◆ rotate_2d() [2/2]

◆ times_2d()