A general (irregular) 2D polygon defined by a sequence of vertices. More...

#include <polygon.H>

Inheritance diagram for Aleph::Polygon:

Collaboration diagram for Aleph::Polygon:

Classes
class	Iterator
	STL/Aleph-compatible iterator over polygon vertices as Points. More...

class	Segment_Iterator
	Iterator over the edges (segments) of a polygon. More...

struct	Vertex_Iterator
	Iterator over the vertices of a polygon. More...

Public Types
enum class	PointLocation { Outside , Boundary , Inside }

using	Item_Type = Point
	The type of elements iterated over.

using	Key_Type = Point
	Alias for Item_Type.

Public Types inherited from StlAlephIterator< Polygon >
using	iterator = StlIterator< Polygon >

using	const_iterator = StlConstIterator< Polygon >

Public Member Functions
	Polygon ()
	Default constructor. Creates an empty, open polygon.

	~Polygon ()
	Destructor. Frees all vertices.

	Polygon (const Polygon &poly)
	Copy constructor.

	Polygon (Polygon &&poly) noexcept
	Move constructor.

	Polygon (const Regular_Polygon &poly)
	Construct from a Regular_Polygon.

Polygon &	operator= (const Polygon &poly)
	Copy assignment operator.

Polygon &	operator= (Polygon &&poly) noexcept
	Move assignment operator.

Polygon &	operator= (const Regular_Polygon &poly)
	Assignment from a Regular_Polygon.

const Point &	lowest_point () const
	Get the vertex with the minimum y-coordinate.

const Point &	highest_point () const
	Get the vertex with the maximum y-coordinate.

const Point &	leftmost_point () const
	Get the vertex with the minimum x-coordinate.

const Point &	rightmost_point () const
	Get the vertex with the maximum x-coordinate.

const bool &	is_closed () const
	Check if the polygon is closed.

const size_t &	size () const
	Get the number of vertices.

bool	vertex_belong_polygon (const Vertex &v) const
	Check if a vertex belongs to this polygon.

const Vertex &	get_first_vertex () const
	Get the first vertex of the polygon.

const Vertex &	get_last_vertex () const
	Get the last vertex of the polygon.

const Vertex &	get_next_vertex (const Vertex &v) const
	Get the vertex following `v` in the polygon.

const Vertex &	get_prev_vertex (const Vertex &v) const
	Get the vertex preceding `v` in the polygon.

Segment	get_first_segment () const
	Get the first edge (segment) of the polygon.

Segment	get_last_segment () const
	Get the last edge (segment) of the polygon.

bool	intersects_with (const Segment &sg) const
	Check if a segment intersects with any edge of the polygon.

void	add_vertex (const Point &point)
	Add a vertex to the polygon.

void	add_vertex (const Geom_Number &x, const Geom_Number &y)
	Add a vertex using coordinates.

void	append (const Point &point)
	Append a vertex (Aleph container protocol).

template<template< typename > class List>
	Polygon (const List< Point > &l)

template<class It >
	Polygon (It b, It e)

	Polygon (std::initializer_list< Point > l)

void	remove_vertex (const Vertex &v)
	Remove a vertex from the polygon.

void	close ()
	Close the polygon.

PointLocation	locate_point (const Point &p) const
	Classify a point against this closed polygon.

bool	contains (const Point &p) const
	Check if a point is inside the polygon (or on its boundary).

bool	contains_to (const Point &p) const

Geom_Number	signed_area () const
	Compute the signed area of the polygon using the shoelace formula.

Geom_Number	area () const
	Compute the absolute area of the polygon.

Geom_Number	perimeter () const
	Compute the perimeter of the polygon.

Point	centroid () const
	Compute the centroid (center of mass) of the polygon.

bool	is_convex () const
	Check if the polygon is convex.

	Polygon (const Triangle &tr)
	Construct a polygon from a Triangle.

Public Member Functions inherited from Aleph::Geom_Object
	Geom_Object ()=default

virtual	~Geom_Object ()=default

Public Member Functions inherited from GenericTraverse< Polygon >
bool	traverse (Operation &operation) noexcept(traverse_is_noexcept< Operation >())
	Traverse the container via its iterator and performs a conditioned operation on each item.

bool	traverse (Operation &operation) const noexcept(traverse_is_noexcept< Operation >())
	Const overload of `traverse(Operation&)`.

bool	traverse (Operation &&operation) const noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&) const` that accepts rvalues.

bool	traverse (Operation &&operation) noexcept(traverse_is_noexcept< Operation >())
	Overload of `traverse(Operation&)` that accepts rvalues.

Public Member Functions inherited from FunctionalMethods< Polygon, Point >
void	emplace (Args &&... args)
	Appends a new element into the container by constructing it in-place with the given args.

void	emplace_end (Args &&... args)

void	emplace_ins (Args &&... args)
	Insert a new element into the container by constructing it in-place with the given args.

size_t	ninsert (Args ... args)
	Insert n variadic items.

size_t	nappend (Args ... args)
	Append n variadic items.

void	for_each (Operation &operation)
	Traverse all the container and performs an operation on each element.

void	for_each (Operation &operation) const
	Const overload of `for_each(Operation&)`.

void	for_each (Operation &&operation) const
	Overload of for_each() const that accepts rvalues.

void	for_each (Operation &&operation)
	Overload of for_each() that accepts rvalues.

void	each (Operation &operation)
	Alias of `for_each(Operation&)`.

void	each (Operation &operation) const
	Const alias of `for_each(Operation&)`.

void	each (Operation &&operation) const
	Const alias of each() that accepts rvalues.

void	each (Operation &&operation)
	Alias of each() that accepts rvalues.

void	each (size_t pos, const size_t slice, Operation &operation) const
	Traverse the container starting at `pos` taking one item every `slice`, performing a mutable operation on each visited element.

void	each (const size_t pos, const size_t slice, Operation &&operation) const

void	mutable_for_each (Operation &operation)
	Apply a mutable operation to each element of the container.

void	mutable_for_each (Operation &&operation)

bool	all (Operation &operation) const
	Check if all the elements of the container satisfy a condition.

bool	all (Operation &&operation) const
	Overload of all() that accepts rvalues.

bool	exists (Operation &op) const
	Test for existence in the container of an element satisfying a criterion.

bool	exists (Operation &&op) const
	Overload of exists() that accepts rvalues.

Aleph::DynList< __T >	maps (Operation &op) const
	Map the elements of the container.

Aleph::DynList< __T >	maps (Operation &&op) const
	Overload of maps() that accepts rvalues.

Aleph::DynList< __T >	maps_if (Prop prop, Operation &op) const
	Conditional mapping of the elements of the container.

Aleph::DynList< __T >	maps_if (Prop prop, Operation &&op) const
	Overload of maps_if() that accepts rvalues.

Aleph::DynList< Point >	to_dynlist () const
	Convert container to DynList.

std::vector< Point >	to_vector () const
	Convert container to std::vector.

__T	foldl (const __T &init, Op &op) const
	Fold the elements of the container to a specific result.

__T	foldl (const __T &init, Op &&op=Op()) const
	Overload of foldl() that accepts rvalues.

__T	fold_left (const __T &init, Op &op) const
	Alias for foldl with the same accumulator type.

__T	fold_left (const __T &init, Op &&op=Op()) const
	Overload of fold_left() that accepts rvalues.

Point	fold (const Point &init, Operation &operation) const
	Simplified version of foldl() where the folded type is the same type of elements stored in the container.

Point	fold (const Point &init, Operation &&operation) const
	Overload of fold() that accepts rvalues.

Aleph::DynList< Point >	filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion.

Aleph::DynList< Point >	filter (Operation &&operation) const
	Overload of filter() that accepts rvalues.

Aleph::DynList< const Point * >	ptr_filter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and return a pointer to the matched items in the container.

Aleph::DynList< const Point * >	ptr_filter (Operation &&operation) const
	Overload of ptr_filter() that accepts rvalues.

Aleph::DynList< std::tuple< Point, size_t > >	pfilter (Operation &operation) const
	Filter the elements of a container according to a matching criterion and determine its positions respect to the traversal of container.

Aleph::DynList< std::tuple< Point, size_t > >	pfilter (Operation &&operation) const
	Overload of pfilter() that accepts rvalues.

std::pair< Aleph::DynList< Point >, Aleph::DynList< Point > >	partition (Operation &op) const
	Exclusive partition of container according to a filter criterion.

std::pair< Aleph::DynList< Point >, Aleph::DynList< Point > >	partition (Operation &&op) const
	Overload of partition() that accepts rvalues.

std::pair< Aleph::DynList< Point >, Aleph::DynList< Point > >	partition (size_t n) const
	Exclusive partition of container in the nth item.

std::pair< Aleph::DynList< Point >, Aleph::DynList< Point > >	split_half () const
	Split the container into two halves by alternating elements.

std::tuple< Aleph::DynList< Point >, Aleph::DynList< Point > >	tpartition (Operation &op) const
	Exclusive partition of container according to a filter criterion.

std::tuple< Aleph::DynList< Point >, Aleph::DynList< Point > >	tpartition (Operation &&op) const
	Overload of tpartition() that accepts rvalues.

size_t	length () const noexcept
	Count the number of elements of a container.

Aleph::DynList< Point >	rev () const
	Return a list with the elements of container in reverse order respect to its traversal order.

Aleph::DynList< Point >	take (const size_t n) const
	Return a list with the first n elements seen in the container during its traversal.

Aleph::DynList< Point >	take (size_t i, const size_t j, const size_t step=1) const
	Return a list with elements seen in the container between i and j position respect to its traversal.

Aleph::DynList< Point >	drop (const size_t n) const
	Drop the first n elements seen in the container during its traversal.

void	mutable_drop (const size_t n)
	Drop the first n elements seen from container.

Public Member Functions inherited from LocateFunctions< Polygon, Point >
auto	get_it () const
	Return a properly initialized iterator positioned at the first item on the container.

auto	get_it (const size_t pos) const
	Return a properly initialized iterator positioned at the `pos` item on the container.

auto	get_itor () const
	Alias of `get_it()`.

Point &	nth_ne (const size_t n) noexcept
	Return the n‑th element without bounds checking.

const Point &	nth_ne (const size_t n) const noexcept
	Const overload of `nth_ne(size_t)`.

Point &	nth (const size_t n)
	Return the n-th item of the container.

const Point &	nth (const size_t n) const
	Const overload of `nth(size_t)`.

Point *	find_ptr (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Find a pointer to an item in the container according to a searching criterion.

const Point *	find_ptr (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Const overload of `find_ptr(Operation&)`.

const Point *	find_ptr (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() const that accepts rvalues.

Point *	find_ptr (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_ptr() that accepts rvalues.

size_t	find_index (Operation &operation) const noexcept(operation_is_noexcept< Operation >())
	Find the position of an item in the container according to a searching criterion.

size_t	find_index (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_index() that accepts rvalues.

std::tuple< bool, Point >	find_item (Operation &operation) noexcept(operation_is_noexcept< Operation >())
	Safe sequential searching of an item matching a criterion.

std::tuple< bool, Point >	find_item (Operation &operation) const noexcept(operation_is_noexcept< Operation >())

std::tuple< bool, Point >	find_item (Operation &&operation) noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() that accepts rvalues.

std::tuple< bool, Point >	find_item (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Overload of find_item() const that accepts rvalues.

bool	contains_if (Operation &&operation) const noexcept(operation_is_noexcept< Operation >())
	Test if an item satisfying a criterion is present in the container.

bool	contains (const Point &item) const
	Test if an item is present in the container using equality.

Public Member Functions inherited from StlAlephIterator< Polygon >
iterator	begin () noexcept
	Return an STL-compatible iterator to the first element.

const_iterator	begin () const noexcept
	Return a const iterator to the first element.

iterator	end () noexcept
	Return an STL-compatible end iterator.

const_iterator	end () const noexcept
	Return a const end iterator.

const_iterator	cbegin () const noexcept
	Return a const iterator to the first element.

const_iterator	cend () const noexcept
	Return a const end iterator.

Private Member Functions
void	update_extreme_points (const Point &point)
	Update extreme points after adding a new vertex.

void	delete_points ()
	Delete all vertices and reset the polygon state.

void	copy_points (const Polygon &poly)
	Copy all vertices from another polygon.

void	copy_regular_polygon (const Regular_Polygon &poly)
	Copy vertices from a regular polygon.

Private Attributes
Dlink	vertex_list_
	Doubly linked list of vertices.

size_t	num_vertex_
	Number of vertices in the polygon.

bool	is_closed_
	True if the polygon has been closed.

Point	lowest_
	Vertex with minimum y-coordinate.

Point	highest_
	Vertex with maximum y-coordinate.

Point	leftmost_
	Vertex with minimum x-coordinate.

Point	rightmost_
	Vertex with maximum x-coordinate.

Additional Inherited Members
Related Symbols inherited from FunctionalMethods< Polygon, Point >
	each

	each

	each

Detailed Description

A general (irregular) 2D polygon defined by a sequence of vertices.

The Polygon class represents a 2D polygon as an ordered sequence of vertices stored in a doubly linked list. The polygon can be open (a polyline) or closed (a proper polygon).

Key Features

Dynamic construction: Vertices can be added one at a time.
Self-intersection prevention: Adding vertices that would cause self-intersection throws an exception.
Colinearity handling: Colinear vertices are automatically merged to simplify the polygon.
Bounding box tracking: Extreme points (lowest, highest, leftmost, rightmost) are maintained incrementally.
Point containment: Test if a point lies inside a closed polygon.

Building a Polygon

Polygon pentagon;
pentagon.add_vertex(Point(0, 100));
pentagon.add_vertex(Point(95, 31));
pentagon.add_vertex(Point(59, -81));
pentagon.add_vertex(Point(-59, -81));
pentagon.add_vertex(Point(-95, 31));
pentagon.close();  // Connect last vertex to first

Limitations

The containment test assumes the polygon is convex. For non-convex polygons, use a more sophisticated algorithm.

See also: Vertex, Regular_Polygon, Triangle

Definition at line 241 of file polygon.H.

Member Typedef Documentation

◆ Item_Type

using Aleph::Polygon::Item_Type = Point

The type of elements iterated over.

Definition at line 305 of file polygon.H.

◆ Key_Type

using Aleph::Polygon::Key_Type = Point

Alias for Item_Type.

Definition at line 308 of file polygon.H.

Member Enumeration Documentation

◆ PointLocation

enum class Aleph::Polygon::PointLocation

strong

Enumerator
Outside
Boundary
Inside

Definition at line 869 of file polygon.H.

Constructor & Destructor Documentation

◆ Polygon() [1/8]

Aleph::Polygon::Polygon ( )

inline

Default constructor. Creates an empty, open polygon.

Definition at line 362 of file polygon.H.

◆ ~Polygon()

Aleph::Polygon::~Polygon ( )

inline

Destructor. Frees all vertices.

Definition at line 367 of file polygon.H.

References delete_points().

◆ Polygon() [2/8]

Aleph::Polygon::Polygon ( const Polygon & poly )

inline

Copy constructor.

Parameters

poly	The polygon to copy.

Definition at line 374 of file polygon.H.

References copy_points().

◆ Polygon() [3/8]

Aleph::Polygon::Polygon ( Polygon && poly )

inlinenoexcept

Move constructor.

Parameters

poly	The polygon to move from.

Definition at line 385 of file polygon.H.

References highest_, is_closed_, leftmost_, lowest_, num_vertex_, rightmost_, Aleph::Dlink::swap(), and vertex_list_.

◆ Polygon() [4/8]

Aleph::Polygon::Polygon ( const Regular_Polygon & poly )

inline

Construct from a Regular_Polygon.

Parameters

poly	The regular polygon to convert.

Note: The resulting polygon is automatically closed.

Definition at line 400 of file polygon.H.

References copy_regular_polygon().

◆ Polygon() [5/8]

template<template< typename > class List>

Aleph::Polygon::Polygon ( const List< Point > & l )

inline

Definition at line 766 of file polygon.H.

◆ Polygon() [6/8]

template<class It >

Aleph::Polygon::Polygon	(	It	b,
		It	e
	)

inline

Definition at line 766 of file polygon.H.

◆ Polygon() [7/8]

Aleph::Polygon::Polygon ( std::initializer_list< Point > l )

inline

Definition at line 766 of file polygon.H.

◆ Polygon() [8/8]

Aleph::Polygon::Polygon ( const Triangle & tr )

inline

Construct a polygon from a Triangle.

Creates a closed 3-vertex polygon from the given triangle.

Parameters

tr	The triangle to convert.

Definition at line 1071 of file polygon.H.

References add_vertex(), close(), and Aleph::divide_and_conquer_partition_dp().

Member Function Documentation

◆ add_vertex() [1/2]

void Aleph::Polygon::add_vertex	(	const Geom_Number &	x,
		const Geom_Number &	y
	)

inline

Add a vertex using coordinates.

Parameters

x	The x-coordinate.
y	The y-coordinate.

See also: add_vertex(const Point &)

Definition at line 756 of file polygon.H.

References add_vertex(), and y.

◆ add_vertex() [2/2]

void Aleph::Polygon::add_vertex ( const Point & point )

inline

Add a vertex to the polygon.

Adds a new vertex at the end of the vertex list. The method performs several validations:

Closed check: Cannot add vertices to a closed polygon.
Colinearity: If the new point is colinear with the last segment, the last vertex is replaced (edge extension).
Self-intersection: If the new edge would intersect any existing edge, an exception is thrown.

Parameters

point The point to add as a vertex.

Exceptions

std::domain_error If the polygon is closed, the point is inside the last segment, or the new edge would cause self-intersection.

Definition at line 677 of file polygon.H.

References ah_domain_error_if, Aleph::Dlink::append(), Aleph::divide_and_conquer_partition_dp(), get_first_vertex(), get_last_segment(), get_last_vertex(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Dlink::Iterator::has_curr(), highest_, is_closed_, Aleph::Point::is_colinear_with(), Aleph::Point::is_inside(), leftmost_, lowest_, Aleph::Dlink::Iterator::next_ne(), num_vertex_, rightmost_, Aleph::Vertex::to_point(), update_extreme_points(), and vertex_list_.

◆ append()

void Aleph::Polygon::append ( const Point & point )

inline

Append a vertex (Aleph container protocol).

Parameters

point The point to add as a vertex.

See also: add_vertex(const Point &)

Definition at line 764 of file polygon.H.

References add_vertex().

Referenced by TEST_F().

◆ area()

Geom_Number Aleph::Polygon::area ( ) const

inline

Compute the absolute area of the polygon.

Returns: The unsigned area of the polygon.

Exceptions

std::domain_error If polygon has fewer than 3 vertices.

Definition at line 963 of file polygon.H.

References signed_area().

Referenced by TEST(), TEST(), TEST(), and TEST().

◆ centroid()

Point Aleph::Polygon::centroid ( ) const

inline

Compute the centroid (center of mass) of the polygon.

Uses the standard formula for the centroid of a simple polygon.

Returns: The centroid point.

Exceptions

std::domain_error If polygon has fewer than 3 vertices or zero area.

Definition at line 993 of file polygon.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Polygon::Segment_Iterator::has_curr(), and num_vertex_.

Referenced by TEST(), TEST(), and TEST().

◆ close()

void Aleph::Polygon::close ( )

inline

Close the polygon.

Closes the polygon by logically connecting the last vertex to the first. This enables segment iteration to include the closing edge and allows containment testing.

Exceptions

std::domain_error If the polygon is already closed or if closing would cause a self-intersection.

Precondition: The polygon must have at least 3 vertices to form a valid closed shape.

Definition at line 840 of file polygon.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::Segment_Iterator::get_current_segment(), get_first_vertex(), get_last_segment(), get_last_vertex(), is_closed_, Aleph::Dlink::Iterator::next(), Aleph::Dlink::Iterator::next_ne(), and num_vertex_.

◆ contains()

bool Aleph::Polygon::contains ( const Point & p ) const

inline

Check if a point is inside the polygon (or on its boundary).

Tests whether the given point lies inside or on the boundary of this closed simple polygon. Uses the winding number algorithm, which works correctly for both convex and non-convex polygons.

Parameters

p	The point to test.

Returns: True if p is inside or on the boundary.

Exceptions

std::domain_error If the polygon is not closed.

Definition at line 926 of file polygon.H.

References locate_point(), and Outside.

Referenced by contains_to(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ contains_to()

bool Aleph::Polygon::contains_to ( const Point & p ) const

inline

Deprecated:: Use contains() instead.

Definition at line 933 of file polygon.H.

References contains().

◆ copy_points()

void Aleph::Polygon::copy_points ( const Polygon & poly )

inlineprivate

Copy all vertices from another polygon.

Parameters

poly	The polygon to copy vertices from.

Definition at line 291 of file polygon.H.

References Aleph::Dlink::append(), Aleph::Vertex::dlink_to_vertex(), Aleph::Dlink::Iterator::has_curr(), and vertex_list_.

Referenced by Polygon(), and operator=().

◆ copy_regular_polygon()

void Aleph::Polygon::copy_regular_polygon ( const Regular_Polygon & poly )

inlineprivate

Copy vertices from a regular polygon.

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Copy vertices from a regular polygon.

Parameters

[in] poly The regular polygon to copy.

See declaration for parameter documentation.

Definition at line 1379 of file polygon.H.

References add_vertex(), Aleph::and, close(), Aleph::divide_and_conquer_partition_dp(), Aleph::Regular_Polygon::get_vertex(), is_closed_, num_vertex_, and Aleph::Regular_Polygon::size().

Referenced by Polygon(), and operator=().

◆ delete_points()

void Aleph::Polygon::delete_points ( )

inlineprivate

Delete all vertices and reset the polygon state.

Definition at line 280 of file polygon.H.

References Aleph::divide_and_conquer_partition_dp(), Aleph::Vertex::dlink_to_vertex(), is_closed_, Aleph::Dlink::is_empty(), num_vertex_, Aleph::Dlink::remove_next(), and vertex_list_.

Referenced by ~Polygon(), operator=(), and operator=().

◆ get_first_segment()

Segment Aleph::Polygon::get_first_segment ( ) const

inline

Get the first edge (segment) of the polygon.

Returns: Segment from first to second vertex.

Exceptions

std::domain_error If the polygon has fewer than 2 vertices.

Definition at line 626 of file polygon.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), get_first_vertex(), Aleph::Dlink::is_unitarian_or_empty(), and vertex_list_.

Referenced by TEST_F().

◆ get_first_vertex()

const Vertex & Aleph::Polygon::get_first_vertex ( ) const

inline

Get the first vertex of the polygon.

Returns: Reference to the first vertex.

Exceptions

std::domain_error If the polygon has no vertices.

Definition at line 578 of file polygon.H.

References ah_domain_error_if, Aleph::Vertex::dlink_to_vertex(), Aleph::Dlink::get_next(), Aleph::Dlink::is_empty(), and vertex_list_.

Referenced by add_vertex(), close(), Aleph::Polygon::Segment_Iterator::get_current_segment(), get_first_segment(), Aleph::CuttingEarsTriangulation::operator()(), remove_vertex(), TEST_F(), and TEST_F().

◆ get_last_segment()

Segment Aleph::Polygon::get_last_segment ( ) const

inline

Get the last edge (segment) of the polygon.

Returns: Segment from second-to-last to last vertex.

Exceptions

std::domain_error If the polygon has fewer than 2 vertices.

Definition at line 639 of file polygon.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), get_last_vertex(), Aleph::Dlink::is_unitarian_or_empty(), and vertex_list_.

Referenced by add_vertex(), close(), Eepic_Dash_Polygon_With_Arrow::draw(), and Eepic_Thick_Dash_Polygon_With_Arrow::draw().

◆ get_last_vertex()

const Vertex & Aleph::Polygon::get_last_vertex ( ) const

inline

Get the last vertex of the polygon.

Returns: Reference to the last vertex.

Exceptions

std::domain_error If the polygon has no vertices.

Definition at line 588 of file polygon.H.

References ah_domain_error_if, Aleph::Vertex::dlink_to_vertex(), Aleph::Dlink::get_prev(), Aleph::Dlink::is_empty(), and vertex_list_.

Referenced by add_vertex(), close(), get_last_segment(), and TEST_F().

◆ get_next_vertex()

const Vertex & Aleph::Polygon::get_next_vertex ( const Vertex & v ) const

inline

Get the vertex following v in the polygon.

For closed polygons, this wraps from the last vertex to the first.

Parameters

v	Reference vertex.

Returns: Reference to the next vertex.

Definition at line 601 of file polygon.H.

References Aleph::Vertex::dlink_to_vertex(), Aleph::Dlink::get_next(), Aleph::Vertex::next_vertex(), and vertex_list_.

Referenced by Aleph::CuttingEarsTriangulation::in_cone(), Aleph::CuttingEarsTriangulation::init_ears(), and Aleph::CuttingEarsTriangulation::operator()().

◆ get_prev_vertex()

const Vertex & Aleph::Polygon::get_prev_vertex ( const Vertex & v ) const

inline

Get the vertex preceding v in the polygon.

For closed polygons, this wraps from the first vertex to the last.

Parameters

v	Reference vertex.

Returns: Reference to the previous vertex.

Definition at line 615 of file polygon.H.

References Aleph::Vertex::dlink_to_vertex(), Aleph::Dlink::get_prev(), Aleph::Vertex::prev_vertex(), and vertex_list_.

Referenced by Aleph::CuttingEarsTriangulation::in_cone(), Aleph::CuttingEarsTriangulation::init_ears(), and Aleph::CuttingEarsTriangulation::operator()().

◆ highest_point()

const Point & Aleph::Polygon::highest_point ( ) const

inline

Get the vertex with the maximum y-coordinate.

Returns: Reference to the highest point.

Definition at line 461 of file polygon.H.

References highest_.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ intersects_with()

bool Aleph::Polygon::intersects_with ( const Segment & sg ) const

inline

Check if a segment intersects with any edge of the polygon.

Parameters

sg	The segment to test.

Returns: True if sg intersects with any edge of the polygon.

Definition at line 652 of file polygon.H.

References Aleph::divide_and_conquer_partition_dp(), and Aleph::Polygon::Segment_Iterator::has_curr().

◆ is_closed()

const bool & Aleph::Polygon::is_closed ( ) const

inline

Check if the polygon is closed.

Returns: True if closed, false if still open.

Definition at line 473 of file polygon.H.

References is_closed_.

Referenced by Aleph::Tikz_Plane::draw_polygon(), Aleph::VoronoiDiagramFromDelaunay::extract_vertices(), Aleph::RotatingCalipersConvexPolygon::extract_vertices(), Aleph::ConvexPolygonIntersectionBasic::extract_vertices(), Aleph::HalfPlaneIntersection::from_convex_polygon(), Aleph::Polygon::Segment_Iterator::get_current_segment(), Aleph::Polygon::Segment_Iterator::has_curr(), Aleph::PointInPolygonWinding::locate(), main(), Aleph::TrapezoidalMapPointLocation::operator()(), Aleph::BooleanPolygonOperations::operator()(), Aleph::ConvexPolygonDistanceGJK::operator()(), Aleph::CuttingEarsTriangulation::operator()(), Aleph::ConvexPolygonDecomposition::operator()(), Aleph::PolygonOffset::operator()(), Aleph::TrapezoidalMapPointLocation::operator()(), Aleph::VisibilityPolygon::operator()(), Aleph::ShortestPathInPolygon::operator()(), Aleph::MonotonePolygonTriangulation::operator()(), Aleph::operator<<(), polygon_area(), print_polygon(), Aleph::detail::shortest_path_portals(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ is_convex()

bool Aleph::Polygon::is_convex ( ) const

inline

Check if the polygon is convex.

A polygon is convex if all cross products of consecutive edges have the same sign (all left turns or all right turns).

Returns: True if the polygon is convex, false otherwise.

Exceptions

std::domain_error If polygon has fewer than 3 vertices.

Definition at line 1021 of file polygon.H.

References ah_domain_error_if, Aleph::and, Aleph::area_of_parallelogram(), Aleph::divide_and_conquer_partition_dp(), Aleph::Polygon::Segment_Iterator::get_current_segment(), Aleph::Polygon::Segment_Iterator::has_curr(), Aleph::Dlink::Iterator::next_ne(), and num_vertex_.

Referenced by TEST(), TEST(), and TEST().

◆ leftmost_point()

const Point & Aleph::Polygon::leftmost_point ( ) const

inline

Get the vertex with the minimum x-coordinate.

Returns: Reference to the leftmost point.

Definition at line 465 of file polygon.H.

References leftmost_.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ locate_point()

PointLocation Aleph::Polygon::locate_point ( const Point & p ) const

inline

Classify a point against this closed polygon.

Uses winding number with exact predicates.

Parameters

p	The point to test.

Returns: PointLocation::Outside, PointLocation::Boundary, or PointLocation::Inside.

Exceptions

std::domain_error If the polygon is not closed.

Definition at line 884 of file polygon.H.

References ah_domain_error_if, Aleph::and, Boundary, Aleph::CCW, Aleph::CW, Aleph::divide_and_conquer_partition_dp(), Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_y(), Aleph::Polygon::Segment_Iterator::has_curr(), Inside, is_closed_, Aleph::on_segment(), Aleph::orientation(), and Outside.

Referenced by contains(), and Aleph::PointInPolygonWinding::locate().

◆ lowest_point()

const Point & Aleph::Polygon::lowest_point ( ) const

inline

Get the vertex with the minimum y-coordinate.

Returns: Reference to the lowest point.

Definition at line 457 of file polygon.H.

References lowest_.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ operator=() [1/3]

Polygon & Aleph::Polygon::operator= ( const Polygon & poly )

inline

Copy assignment operator.

Parameters

poly	The polygon to copy.

Returns: Reference to this polygon.

Definition at line 409 of file polygon.H.

References copy_points(), delete_points(), highest_, is_closed_, leftmost_, lowest_, num_vertex_, and rightmost_.

◆ operator=() [2/3]

Polygon & Aleph::Polygon::operator= ( const Regular_Polygon & poly )

inline

Assignment from a Regular_Polygon.

Parameters

poly	The regular polygon to convert.

Returns: Reference to this polygon.

Definition at line 447 of file polygon.H.

References copy_regular_polygon(), and delete_points().

◆ operator=() [3/3]

Polygon & Aleph::Polygon::operator= ( Polygon && poly )

inlinenoexcept

Move assignment operator.

Parameters

poly	The polygon to move from.

Returns: Reference to this polygon.

Definition at line 431 of file polygon.H.

References highest_, is_closed_, leftmost_, lowest_, num_vertex_, rightmost_, Aleph::Dlink::swap(), and vertex_list_.

◆ perimeter()

Geom_Number Aleph::Polygon::perimeter ( ) const

inline

Compute the perimeter of the polygon.

Sum of all edge lengths. For closed polygons, includes the closing edge.

Returns: The perimeter length.

Exceptions

std::domain_error If polygon has fewer than 2 vertices.

Definition at line 976 of file polygon.H.

References ah_domain_error_if, Aleph::Polygon::Segment_Iterator::has_curr(), num_vertex_, and Aleph::sum().

Referenced by TEST(), and TEST().

◆ remove_vertex()

void Aleph::Polygon::remove_vertex ( const Vertex & v )

inline

Remove a vertex from the polygon.

Removes the specified vertex from the polygon.

Parameters

v	The vertex to remove.

Exceptions

std::domain_error If v does not belong to this polygon.

Warning: This method does not handle colinearity cases that might arise from removing a vertex (the caller is responsible for validation).

Definition at line 777 of file polygon.H.

References ah_domain_error_if, Aleph::divide_and_conquer_partition_dp(), get_first_vertex(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Dlink::Iterator::has_curr(), highest_, is_closed_, leftmost_, lowest_, num_vertex_, rightmost_, and Aleph::Vertex::to_point().

Referenced by Aleph::CuttingEarsTriangulation::operator()().

◆ rightmost_point()

const Point & Aleph::Polygon::rightmost_point ( ) const

inline

Get the vertex with the maximum x-coordinate.

Returns: Reference to the rightmost point.

Definition at line 469 of file polygon.H.

References rightmost_.

Referenced by TEST_F(), TEST_F(), and TEST_F().

◆ signed_area()

Geom_Number Aleph::Polygon::signed_area ( ) const

inline

Compute the signed area of the polygon using the shoelace formula.

Positive for counter-clockwise vertices, negative for clockwise. Works for both convex and non-convex simple polygons.

Returns: The signed area (positive if CCW, negative if CW).

Exceptions

std::domain_error If polygon has fewer than 3 vertices.

Definition at line 943 of file polygon.H.

References ah_domain_error_if, Aleph::Segment::get_src_point(), Aleph::Segment::get_tgt_point(), Aleph::Point::get_x(), Aleph::Point::get_y(), Aleph::Polygon::Segment_Iterator::has_curr(), num_vertex_, and Aleph::sum().

Referenced by area(), TEST(), and TEST().

◆ size()

const size_t & Aleph::Polygon::size ( ) const

inline

Get the number of vertices.

Returns: Number of vertices in the polygon.

Definition at line 477 of file polygon.H.

References num_vertex_.

◆ update_extreme_points()

void Aleph::Polygon::update_extreme_points ( const Point & point )

inlineprivate

Update extreme points after adding a new vertex.

Parameters

point The newly added point.

Definition at line 258 of file polygon.H.

References Aleph::Point::get_x(), Aleph::Point::get_y(), highest_, leftmost_, lowest_, num_vertex_, and rightmost_.

Referenced by add_vertex().

◆ vertex_belong_polygon()

bool Aleph::Polygon::vertex_belong_polygon ( const Vertex & v ) const

inline

Check if a vertex belongs to this polygon.

Parameters

v	The vertex to check.

Returns: True if v is a vertex of this polygon.

Definition at line 566 of file polygon.H.

References Aleph::Dlink::Iterator::has_curr().

Member Data Documentation

◆ highest_

Point Aleph::Polygon::highest_

private

Vertex with maximum y-coordinate.

Definition at line 252 of file polygon.H.

Referenced by Polygon(), add_vertex(), highest_point(), operator=(), operator=(), remove_vertex(), and update_extreme_points().

◆ is_closed_

bool Aleph::Polygon::is_closed_

private

True if the polygon has been closed.

Definition at line 249 of file polygon.H.

Referenced by Polygon(), add_vertex(), close(), copy_regular_polygon(), delete_points(), is_closed(), locate_point(), operator=(), operator=(), and remove_vertex().

◆ leftmost_

Point Aleph::Polygon::leftmost_

private

Vertex with minimum x-coordinate.

Definition at line 253 of file polygon.H.

Referenced by Polygon(), add_vertex(), leftmost_point(), operator=(), operator=(), remove_vertex(), and update_extreme_points().

◆ lowest_

Point Aleph::Polygon::lowest_

private

Vertex with minimum y-coordinate.

Definition at line 251 of file polygon.H.

Referenced by Polygon(), add_vertex(), lowest_point(), operator=(), operator=(), remove_vertex(), and update_extreme_points().

◆ num_vertex_

size_t Aleph::Polygon::num_vertex_

private

Number of vertices in the polygon.

Definition at line 248 of file polygon.H.

Referenced by Polygon(), add_vertex(), centroid(), close(), copy_regular_polygon(), delete_points(), is_convex(), operator=(), operator=(), perimeter(), remove_vertex(), signed_area(), size(), and update_extreme_points().

◆ rightmost_

Point Aleph::Polygon::rightmost_

private

Vertex with maximum x-coordinate.

Definition at line 254 of file polygon.H.

Referenced by Polygon(), add_vertex(), operator=(), operator=(), remove_vertex(), rightmost_point(), and update_extreme_points().

◆ vertex_list_

Dlink Aleph::Polygon::vertex_list_

private

Doubly linked list of vertices.

Definition at line 247 of file polygon.H.

Referenced by Polygon(), Aleph::Polygon::Segment_Iterator::Segment_Iterator(), Aleph::Polygon::Vertex_Iterator::Vertex_Iterator(), add_vertex(), copy_points(), delete_points(), get_first_segment(), get_first_vertex(), get_last_segment(), get_last_vertex(), get_next_vertex(), get_prev_vertex(), and operator=().

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

polygon.H

Classes

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Key Features

Building a Polygon

Limitations

Member Typedef Documentation

◆ Item_Type

◆ Key_Type

Member Enumeration Documentation

◆ PointLocation

Constructor & Destructor Documentation

◆ Polygon() [1/8]

◆ ~Polygon()

◆ Polygon() [2/8]

◆ Polygon() [3/8]

◆ Polygon() [4/8]

◆ Polygon() [5/8]

◆ Polygon() [6/8]

◆ Polygon() [7/8]

◆ Polygon() [8/8]

Member Function Documentation

◆ add_vertex() [1/2]

◆ add_vertex() [2/2]

◆ append()

◆ area()

◆ centroid()

◆ close()

◆ contains()

◆ contains_to()

◆ copy_points()

◆ copy_regular_polygon()

◆ delete_points()

◆ get_first_segment()

◆ get_first_vertex()

◆ get_last_segment()

◆ get_last_vertex()

◆ get_next_vertex()

◆ get_prev_vertex()

◆ highest_point()

◆ intersects_with()

◆ is_closed()

◆ is_convex()

◆ leftmost_point()

◆ locate_point()

◆ lowest_point()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ perimeter()

◆ remove_vertex()

◆ rightmost_point()

◆ signed_area()

◆ size()

◆ update_extreme_points()

◆ vertex_belong_polygon()

Member Data Documentation

◆ highest_

◆ is_closed_

◆ leftmost_

◆ lowest_

◆ num_vertex_

◆ rightmost_

◆ vertex_list_