Inkscape: Geom::ConvexHull Class Reference

Searching...

No Matches

Convex hull based on the Andrew's monotone chain algorithm. More...

#include <convex-hull.h>

Public Types
using	iterator = std::vector< Point >::const_iterator

using	const_iterator = std::vector< Point >::const_iterator

using	UpperIterator = std::vector< Point >::const_iterator

using	LowerIterator = ConvexHullLowerIterator

Public Member Functions
void	swap (ConvexHull &other)

void	swap (std::vector< Point > &pts)

Construct a convex hull.
	ConvexHull ()=default
	Create an empty convex hull.

	ConvexHull (Point const &a)
	Construct a singular convex hull.

	ConvexHull (Point const &a, Point const &b)
	Construct a convex hull of two points.

	ConvexHull (Point const &a, Point const &b, Point const &c)
	Construct a convex hull of three points.

	ConvexHull (Point const &a, Point const &b, Point const &c, Point const &d)
	Construct a convex hull of four points.

	ConvexHull (std::vector< Point > const &pts)
	Create a convex hull of a vector of points.

template<typename Iter >
	ConvexHull (Iter first, Iter last)
	Create a convex hull of a range of points.

Inspect basic properties.
bool	empty () const
	Check for emptiness.

size_t	size () const
	Get the number of points in the hull.

bool	isSingular () const
	Check whether the hull contains only one point.

bool	isLinear () const
	Check whether the hull is a line.

bool	isDegenerate () const
	Check whether the hull has zero area.

double	area () const
	Calculate the area of the convex hull.

Inspect bounds and extreme points.
OptRect	bounds () const
	Compute the bounding rectangle of the convex hull.

std::pair< Rotate, OptRect >	minAreaRotation () const
	Return a rotation that puts the convex hull into a position such that bounds() has minimal area, and return those bounds.

Coord	left () const
	Get the leftmost (minimum X) coordinate of the hull.

Coord	right () const
	Get the rightmost (maximum X) coordinate of the hull.

Coord	top () const
	Get the topmost (minimum Y) coordinate of the hull.

Coord	bottom () const
	Get the bottommost (maximum Y) coordinate of the hull.

Point	leftPoint () const
	Get the leftmost (minimum X) point of the hull.

Point	rightPoint () const
	Get the rightmost (maximum X) point of the hull.

Point	topPoint () const
	Get the topmost (minimum Y) point of the hull.

Point	bottomPoint () const
	Get the bottommost (maximum Y) point of the hull.

Iterate over points.
iterator	begin () const
	Get the begin iterator to the points that form the hull.

iterator	end () const
	Get the end iterator to the points that form the hull.

Point const &	front () const
	Get the first, leftmost point in the hull.

Point const &	back () const
	Get the penultimate point of the lower hull.

Point const &	operator[] (std::size_t i) const

boost::iterator_range< UpperIterator >	upperHull () const
	Get an iterator range to the upper part of the hull.

boost::iterator_range< LowerIterator >	lowerHull () const
	Get an iterator range to the lower part of the hull.

Check for containment and intersection.
bool	contains (Point const &p) const
	Check whether the given point is inside the hull.

bool	contains (Rect const &r) const
	Check whether the given axis-aligned rectangle is inside the hull.

bool	contains (ConvexHull const &other) const
	Check whether the given convex hull is completely contained in this one.

Private Member Functions
void	_construct ()

Static Private Member Functions
template<typename Iter >
static void	_prune (Iter first, Iter last, std::vector< Point > &out)
	Take a vector of points and produce a pruned sorted vector.

Private Attributes
std::vector< Point >	_boundary
	Sequence of points forming the convex hull polygon.

std::size_t	_lower
	Index one past the rightmost point, where the lower part of the boundary starts.

Detailed Description

Convex hull based on the Andrew's monotone chain algorithm.

Definition at line 114 of file convex-hull.h.

Member Typedef Documentation

◆ const_iterator

using Geom::ConvexHull::const_iterator = std::vector<Point>::const_iterator

Definition at line 118 of file convex-hull.h.

◆ iterator

using Geom::ConvexHull::iterator = std::vector<Point>::const_iterator

Definition at line 117 of file convex-hull.h.

◆ LowerIterator

using Geom::ConvexHull::LowerIterator = ConvexHullLowerIterator

Definition at line 120 of file convex-hull.h.

◆ UpperIterator

using Geom::ConvexHull::UpperIterator = std::vector<Point>::const_iterator

Definition at line 119 of file convex-hull.h.

Constructor & Destructor Documentation

◆ ConvexHull() [1/7]

Geom::ConvexHull::ConvexHull ( )

default

Create an empty convex hull.

◆ ConvexHull() [2/7]

Geom::ConvexHull::ConvexHull ( Point const & a )

inlineexplicit

Construct a singular convex hull.

Definition at line 128 of file convex-hull.h.

◆ ConvexHull() [3/7]

Geom::ConvexHull::ConvexHull	(	Point const &	a,
		Point const &	b
	)

Construct a convex hull of two points.

Definition at line 62 of file convex-hull.cpp.

References _boundary, and _construct().

◆ ConvexHull() [4/7]

Geom::ConvexHull::ConvexHull	(	Point const &	a,
		Point const &	b,
		Point const &	c
	)

Construct a convex hull of three points.

Definition at line 72 of file convex-hull.cpp.

References _boundary, _construct(), and c.

◆ ConvexHull() [5/7]

Geom::ConvexHull::ConvexHull	(	Point const &	a,
		Point const &	b,
		Point const &	c,
		Point const &	d
	)

Construct a convex hull of four points.

Definition at line 83 of file convex-hull.cpp.

References _boundary, _construct(), and c.

◆ ConvexHull() [6/7]

Geom::ConvexHull::ConvexHull ( std::vector< Point > const & pts )

Create a convex hull of a vector of points.

Definition at line 95 of file convex-hull.cpp.

References _boundary, and _construct().

◆ ConvexHull() [7/7]

template<typename Iter >

Geom::ConvexHull::ConvexHull	(	Iter	first,
		Iter	last
	)

inline

Create a convex hull of a range of points.

Definition at line 143 of file convex-hull.h.

References _boundary, _construct(), and _prune().

Member Function Documentation

◆ _construct()

void Geom::ConvexHull::_construct ( )

private

Definition at line 113 of file convex-hull.cpp.

References _boundary, _lower, and Geom::is_clockwise_turn().

Referenced by ConvexHull(), ConvexHull(), ConvexHull(), ConvexHull(), ConvexHull(), and swap().

◆ _prune()

template<typename Iter >

static void Geom::ConvexHull::_prune	(	Iter	first,
		Iter	last,
		std::vector< Point > &	out
	)

inlinestaticprivate

Take a vector of points and produce a pruned sorted vector.

Definition at line 278 of file convex-hull.h.

References contains().

Referenced by ConvexHull().

◆ area()

double Geom::ConvexHull::area ( ) const

Calculate the area of the convex hull.

Definition at line 151 of file convex-hull.cpp.

References _boundary, Geom::cross(), and size().

Referenced by minAreaRotation(), and wrap_convex_cover().

◆ back()

Point const & Geom::ConvexHull::back ( ) const

inline

Get the penultimate point of the lower hull.

Definition at line 215 of file convex-hull.h.

References _boundary.

Referenced by cairo_convex_hull(), and Geom::Path::Path().

◆ begin()

iterator Geom::ConvexHull::begin ( ) const

inline

Get the begin iterator to the points that form the hull.

Points are returned beginning with the leftmost one, going along the upper (minimum Y) side, and then along the bottom. Thus the points are always ordered clockwise. No point is repeated.

Definition at line 209 of file convex-hull.h.

References _boundary.

Referenced by Geom::andrew_merge(), and Geom::graham_merge().

◆ bottom()

Coord Geom::ConvexHull::bottom ( ) const

inline

Get the bottommost (maximum Y) coordinate of the hull.

Definition at line 186 of file convex-hull.h.

References bottomPoint(), and Geom::Y.

Referenced by bounds().

◆ bottomPoint()

Point Geom::ConvexHull::bottomPoint ( ) const

Get the bottommost (maximum Y) point of the hull.

If the bottommost edge is horizontal, the left point of the edge is returned.

Definition at line 248 of file convex-hull.cpp.

References lowerHull(), Geom::Y, and Geom::Point::y().

Referenced by bottom().

◆ bounds()

OptRect Geom::ConvexHull::bounds ( ) const

Compute the bounding rectangle of the convex hull.

Definition at line 163 of file convex-hull.cpp.

References bottom(), empty(), left(), right(), and top().

◆ contains() [1/3]

bool Geom::ConvexHull::contains ( ConvexHull const & other ) const

Check whether the given convex hull is completely contained in this one.

Definition at line 316 of file convex-hull.cpp.

References contains().

◆ contains() [2/3]

bool Geom::ConvexHull::contains ( Point const & p ) const

Check whether the given point is inside the hull.

This takes logarithmic time.

Definition at line 286 of file convex-hull.cpp.

References _boundary, _lower, Geom::below_x_monotonic_polyline(), lowerHull(), upperHull(), and Geom::X.

Referenced by _prune(), contains(), contains(), HullContainsPoint(), and Geom::sbasis_to_cubic_bezier().

◆ contains() [3/3]

bool Geom::ConvexHull::contains ( Rect const & r ) const

Check whether the given axis-aligned rectangle is inside the hull.

A rectangle is inside the hull if all of its corners are inside.

Definition at line 308 of file convex-hull.cpp.

References contains(), and Geom::GenericRect< C >::corner().

◆ empty()

bool Geom::ConvexHull::empty ( ) const

inline

Check for emptiness.

Definition at line 155 of file convex-hull.h.

References _boundary.

Referenced by bounds(), cairo_convex_hull(), cairo_convex_hull(), minAreaRotation(), Geom::Path::Path(), and wrap_convex_cover().

◆ end()

iterator Geom::ConvexHull::end ( ) const

inline

Get the end iterator to the points that form the hull.

Definition at line 211 of file convex-hull.h.

References _boundary.

Referenced by Geom::andrew_merge(), and Geom::graham_merge().

◆ front()

Point const & Geom::ConvexHull::front ( ) const

inline

Get the first, leftmost point in the hull.

Definition at line 213 of file convex-hull.h.

References _boundary.

Referenced by minAreaRotation(), and Geom::Path::Path().

◆ isDegenerate()

bool Geom::ConvexHull::isDegenerate ( ) const

inline

Check whether the hull has zero area.

Definition at line 163 of file convex-hull.h.

References _boundary.

◆ isLinear()

bool Geom::ConvexHull::isLinear ( ) const

inline

Check whether the hull is a line.

Definition at line 161 of file convex-hull.h.

References _boundary.

◆ isSingular()

bool Geom::ConvexHull::isSingular ( ) const

inline

Check whether the hull contains only one point.

Definition at line 159 of file convex-hull.h.

References _boundary.

◆ left()

Coord Geom::ConvexHull::left ( ) const

inline

Get the leftmost (minimum X) coordinate of the hull.

Definition at line 180 of file convex-hull.h.

References _boundary, and Geom::X.

Referenced by bounds().

◆ leftPoint()

Point Geom::ConvexHull::leftPoint ( ) const

inline

Get the leftmost (minimum X) point of the hull.

If the leftmost edge is vertical, the top point of the edge is returned.

Definition at line 190 of file convex-hull.h.

References _boundary.

◆ lowerHull()

boost::iterator_range< LowerIterator > Geom::ConvexHull::lowerHull ( ) const

inline

Get an iterator range to the lower part of the hull.

This returns a range that includes the leftmost point, all points of the lower hull, and the rightmost point.

Definition at line 228 of file convex-hull.h.

References _boundary, and _lower.

Referenced by bottomPoint(), and contains().

◆ minAreaRotation()

std::pair< Rotate, OptRect > Geom::ConvexHull::minAreaRotation ( ) const

Return a rotation that puts the convex hull into a position such that bounds() has minimal area, and return those bounds.

Definition at line 169 of file convex-hull.cpp.

References _boundary, area(), Geom::dot(), empty(), Geom::GenericRect< Coord >::from_xywh(), front(), Geom::Rotate::inverse(), Geom::Point::length(), size(), and w.

Referenced by Inkscape::UI::Widget::Stores::snapshot_combine().

◆ operator[]()

Point const & Geom::ConvexHull::operator[] ( std::size_t i ) const

inline

Definition at line 216 of file convex-hull.h.

References _boundary.

◆ right()

Coord Geom::ConvexHull::right ( ) const

inline

Get the rightmost (maximum X) coordinate of the hull.

Definition at line 182 of file convex-hull.h.

References _boundary, _lower, and Geom::X.

Referenced by bounds().

◆ rightPoint()

Point Geom::ConvexHull::rightPoint ( ) const

inline

Get the rightmost (maximum X) point of the hull.

If the rightmost edge is vertical, the bottom point edge is returned.

Definition at line 193 of file convex-hull.h.

References _boundary, and _lower.

◆ size()

size_t Geom::ConvexHull::size ( ) const

inline

Get the number of points in the hull.

Definition at line 157 of file convex-hull.h.

References _boundary.

Referenced by area(), Geom::bridges(), cairo_convex_hull(), cairo_convex_hull(), Geom::detail::bezier_clipping::clip_interval(), Geom::detail::bezier_clipping::clip_interval(), Geom::find_bottom_right(), Geom::merge(), minAreaRotation(), Geom::Path::Path(), and Geom::sweepline_intersection().

◆ swap() [1/2]

void Geom::ConvexHull::swap ( ConvexHull & other )

Definition at line 335 of file convex-hull.cpp.

References _boundary, and _lower.

Referenced by Geom::detail::bezier_clipping::clip_interval(), and Geom::detail::bezier_clipping::clip_interval().

◆ swap() [2/2]

void Geom::ConvexHull::swap ( std::vector< Point > & pts )

Definition at line 341 of file convex-hull.cpp.

References _boundary, _construct(), and _lower.

◆ top()

Coord Geom::ConvexHull::top ( ) const

inline

Get the topmost (minimum Y) coordinate of the hull.

Definition at line 184 of file convex-hull.h.

References topPoint(), and Geom::Y.

Referenced by bounds().

◆ topPoint()

Point Geom::ConvexHull::topPoint ( ) const

Get the topmost (minimum Y) point of the hull.

If the topmost edge is horizontal, the right point of the edge is returned.

Definition at line 232 of file convex-hull.cpp.

References upperHull(), Geom::Y, and Geom::Point::y().

Referenced by top().

◆ upperHull()

boost::iterator_range< UpperIterator > Geom::ConvexHull::upperHull ( ) const

inline

Get an iterator range to the upper part of the hull.

This returns a range that includes the leftmost point, all points of the upper hull, and the rightmost point.

Definition at line 221 of file convex-hull.h.

References _boundary, and _lower.

Referenced by contains(), and topPoint().

Member Data Documentation

◆ _boundary

std::vector<Point> Geom::ConvexHull::_boundary

private

Sequence of points forming the convex hull polygon.

Definition at line 312 of file convex-hull.h.

Referenced by _construct(), area(), back(), begin(), contains(), ConvexHull(), ConvexHull(), ConvexHull(), ConvexHull(), ConvexHull(), empty(), end(), front(), isDegenerate(), isLinear(), isSingular(), left(), leftPoint(), lowerHull(), minAreaRotation(), operator[](), right(), rightPoint(), size(), swap(), swap(), and upperHull().

◆ _lower

std::size_t Geom::ConvexHull::_lower

private

Index one past the rightmost point, where the lower part of the boundary starts.

Definition at line 314 of file convex-hull.h.

Referenced by _construct(), contains(), lowerHull(), right(), rightPoint(), swap(), swap(), and upperHull().

The documentation for this class was generated from the following files:

/builds/inkscape/inkscape/src/3rdparty/2geom/include/2geom/convex-hull.h
/builds/inkscape/inkscape/src/3rdparty/2geom/src/2geom/convex-hull.cpp

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ const_iterator

◆ iterator

◆ LowerIterator

◆ UpperIterator

Constructor & Destructor Documentation

◆ ConvexHull() [1/7]

◆ ConvexHull() [2/7]

◆ ConvexHull() [3/7]

◆ ConvexHull() [4/7]

◆ ConvexHull() [5/7]

◆ ConvexHull() [6/7]

◆ ConvexHull() [7/7]

Member Function Documentation

◆ _construct()

◆ _prune()

◆ area()

◆ back()

◆ begin()

◆ bottom()

◆ bottomPoint()

◆ bounds()

◆ contains() [1/3]

◆ contains() [2/3]

◆ contains() [3/3]

◆ empty()

◆ end()

◆ front()

◆ isDegenerate()

◆ isLinear()

◆ isSingular()

◆ left()

◆ leftPoint()

◆ lowerHull()

◆ minAreaRotation()

◆ operator[]()

◆ right()

◆ rightPoint()

◆ size()

◆ swap() [1/2]

◆ swap() [2/2]

◆ top()

◆ topPoint()

◆ upperHull()

Member Data Documentation

◆ _boundary

◆ _lower