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

#include <polygon.H>

Inheritance diagram for Polygon:

Collaboration diagram for Polygon:

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

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

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 after the given vertex.

const Vertex &	get_prev_vertex (const Vertex &v) const
	Get the vertex before the given vertex.

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

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

bool	intersects_with (const Segment &sg)
	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	remove_vertex (const Vertex &v)
	Remove a vertex from the polygon.

void	close ()
	Close the polygon.

bool	contains_to (const Point &p)
	Check if a point is inside the polygon.

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

Public Member Functions inherited from Geom_Object
	Geom_Object ()=default

virtual	~Geom_Object ()=default

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.

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 232 of file polygon.H.

Constructor & Destructor Documentation

◆ Polygon() [1/5]

Polygon::Polygon ( )

inline

Default constructor. Creates an empty, open polygon.

Definition at line 292 of file polygon.H.

◆ ~Polygon()

Polygon::~Polygon ( )

inline

Destructor. Frees all vertices.

Definition at line 297 of file polygon.H.

References delete_points().

◆ Polygon() [2/5]

Polygon::Polygon ( const Polygon & poly )

inline

Copy constructor.

Parameters

poly	The polygon to copy.

Definition at line 304 of file polygon.H.

References copy_points().

◆ Polygon() [3/5]

Polygon::Polygon ( Polygon && poly )

inlinenoexcept

Move constructor.

Parameters

poly	The polygon to move from.

Definition at line 315 of file polygon.H.

References __is_closed, highest, leftmost, lowest, num_vertex, rightmost, Aleph::Dlink::swap(), and vertex_list.

◆ Polygon() [4/5]

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 330 of file polygon.H.

References copy_regular_polygon().

◆ Polygon() [5/5]

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 775 of file polygon.H.

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

Member Function Documentation

◆ add_vertex() [1/2]

void 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 666 of file polygon.H.

References add_vertex(), and y.

◆ add_vertex() [2/2]

void 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 610 of file polygon.H.

References __is_closed, ah_domain_error_if, Aleph::Dlink::append(), get_last_segment(), get_last_vertex(), Aleph::maps(), num_vertex, update_extreme_points(), and vertex_list.

◆ close()

void 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 710 of file polygon.H.

References __is_closed, ah_domain_error_if, Polygon::Segment_Iterator::get_current_segment(), get_first_vertex(), get_last_segment(), get_last_vertex(), Aleph::maps(), and num_vertex.

Referenced by Polygon(), copy_regular_polygon(), PolygonConstructionTest::create_square(), PolygonConstructionTest::create_triangle(), demo_triangulation_basic(), PolygonVariantsTest::SetUp(), ThickPolygonVariantsTest::SetUp(), PolygonIntersectionTest::SetUp(), PolygonContainmentTest::SetUp(), TEST(), TEST(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ contains_to()

bool Polygon::contains_to ( const Point & p )

inline

Check if a point is inside the polygon.

Tests whether the given point lies inside this closed polygon. The test works by checking if the point is consistently on the same side (left or right) of all edges.

Parameters

p	The point to test.

Returns: True if p is inside the polygon.

Exceptions

std::domain_error If the polygon is not closed.

Note: This algorithm assumes a convex polygon. For non-convex polygons, use a ray-casting or winding number algorithm.

Definition at line 751 of file polygon.H.

References __is_closed, ah_domain_error_if, Polygon::Segment_Iterator::get_current_segment(), Polygon::Segment_Iterator::has_curr(), Aleph::maps(), and test().

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

◆ copy_points()

void Polygon::copy_points ( const Polygon & poly )

inlineprivate

Copy all vertices from another polygon.

Parameters

poly	The polygon to copy vertices from.

Definition at line 278 of file polygon.H.

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

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

◆ copy_regular_polygon()

void 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 1085 of file polygon.H.

References __is_closed, add_vertex(), close(), Regular_Polygon::get_vertex(), Aleph::maps(), num_vertex, and Regular_Polygon::size().

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

◆ delete_points()

void Polygon::delete_points ( )

inlineprivate

Delete all vertices and reset the polygon state.

Definition at line 267 of file polygon.H.

References __is_closed, Vertex::dlink_to_vertex(), Aleph::Dlink::is_empty(), Aleph::maps(), num_vertex, Aleph::Dlink::remove_next(), and vertex_list.

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

◆ get_first_segment()

Segment Polygon::get_first_segment ( )

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 556 of file polygon.H.

References ah_domain_error_if, get_first_vertex(), Aleph::Dlink::is_unitarian_or_empty(), Aleph::maps(), and vertex_list.

Referenced by TEST_F().

◆ get_first_vertex()

const Vertex & 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 510 of file polygon.H.

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

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

◆ get_last_segment()

Segment Polygon::get_last_segment ( )

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 569 of file polygon.H.

References ah_domain_error_if, get_last_vertex(), Aleph::Dlink::is_unitarian_or_empty(), Aleph::maps(), 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 & 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 521 of file polygon.H.

References ah_domain_error_if, 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 & Polygon::get_next_vertex ( const Vertex & v ) const

inline

Get the vertex after the given vertex.

Parameters

v	A vertex of this polygon.

Returns: Reference to the next vertex (wraps around for closed polygons).

Note: No validation is performed to check if v belongs to this polygon.

Definition at line 533 of file polygon.H.

References Vertex::dlink_to_vertex(), Aleph::Dlink::get_next(), 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 & Polygon::get_prev_vertex ( const Vertex & v ) const

inline

Get the vertex before the given vertex.

Parameters

v	A vertex of this polygon.

Returns: Reference to the previous vertex (wraps around for closed polygons).

Note: No validation is performed to check if v belongs to this polygon.

Definition at line 545 of file polygon.H.

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

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

◆ highest_point()

const Point & Polygon::highest_point ( ) const

inline

Get the vertex with the maximum y-coordinate.

Returns: Reference to the highest point.

Definition at line 391 of file polygon.H.

References highest.

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

◆ intersects_with()

bool Polygon::intersects_with ( const Segment & sg )

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 582 of file polygon.H.

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

◆ is_closed()

const bool & Polygon::is_closed ( ) const

inline

Check if the polygon is closed.

Returns: True if closed, false if still open.

Definition at line 403 of file polygon.H.

References __is_closed.

Referenced by Polygon::Segment_Iterator::get_current_segment(), Polygon::Segment_Iterator::has_curr(), TEST(), TEST(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), TEST_F(), and TEST_F().

◆ leftmost_point()

const Point & Polygon::leftmost_point ( ) const

inline

Get the vertex with the minimum x-coordinate.

Returns: Reference to the leftmost point.

Definition at line 395 of file polygon.H.

References leftmost.

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

◆ lowest_point()

const Point & Polygon::lowest_point ( ) const

inline

Get the vertex with the minimum y-coordinate.

Returns: Reference to the lowest point.

Definition at line 387 of file polygon.H.

References lowest.

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

◆ operator=() [1/3]

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

inline

Copy assignment operator.

Parameters

poly	The polygon to copy.

Returns: Reference to this polygon.

Definition at line 339 of file polygon.H.

References __is_closed, copy_points(), delete_points(), highest, leftmost, lowest, num_vertex, and rightmost.

◆ operator=() [2/3]

Polygon & 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 377 of file polygon.H.

References copy_regular_polygon(), and delete_points().

◆ operator=() [3/3]

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

inlinenoexcept

Move assignment operator.

Parameters

poly	The polygon to move from.

Returns: Reference to this polygon.

Definition at line 361 of file polygon.H.

References __is_closed, highest, leftmost, lowest, num_vertex, rightmost, Aleph::Dlink::swap(), and vertex_list.

◆ remove_vertex()

void 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 680 of file polygon.H.

References ah_domain_error_if, Aleph::maps(), and num_vertex.

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

◆ rightmost_point()

const Point & Polygon::rightmost_point ( ) const

inline

Get the vertex with the maximum x-coordinate.

Returns: Reference to the rightmost point.

Definition at line 399 of file polygon.H.

References rightmost.

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

◆ size()

const size_t & Polygon::size ( ) const

inline

Get the number of vertices.

Returns: Number of vertices in the polygon.

Definition at line 407 of file polygon.H.

References num_vertex.

Referenced by Aleph::CuttingEarsTriangulation::operator()(), print_polygon(), TEST(), TEST(), 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().

◆ update_extreme_points()

void 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 245 of file polygon.H.

References highest, leftmost, lowest, num_vertex, and rightmost.

Referenced by add_vertex().

◆ vertex_belong_polygon()

bool 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 498 of file polygon.H.

Member Data Documentation

◆ __is_closed

bool Polygon::__is_closed

private

True if the polygon has been closed.

Definition at line 236 of file polygon.H.

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

◆ highest

Point Polygon::highest

private

Vertex with maximum y-coordinate.

Definition at line 239 of file polygon.H.

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

◆ leftmost

Point Polygon::leftmost

private

Vertex with minimum x-coordinate.

Definition at line 240 of file polygon.H.

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

◆ lowest

Point Polygon::lowest

private

Vertex with minimum y-coordinate.

Definition at line 238 of file polygon.H.

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

◆ num_vertex

size_t Polygon::num_vertex

private

Number of vertices in the polygon.

Definition at line 235 of file polygon.H.

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

◆ rightmost

Point Polygon::rightmost

private

Vertex with maximum x-coordinate.

Definition at line 241 of file polygon.H.

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

◆ vertex_list

Dlink Polygon::vertex_list

private

Doubly-linked list of vertices.

Definition at line 234 of file polygon.H.

Referenced by Polygon(), Polygon::Segment_Iterator::Segment_Iterator(), 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 Member Functions

Private Member Functions

Private Attributes

Detailed Description

Key Features

Building a Polygon

Limitations

Constructor & Destructor Documentation

◆ Polygon() [1/5]

◆ ~Polygon()

◆ Polygon() [2/5]

◆ Polygon() [3/5]

◆ Polygon() [4/5]

◆ Polygon() [5/5]

Member Function Documentation

◆ add_vertex() [1/2]

◆ add_vertex() [2/2]

◆ close()

◆ 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()

◆ leftmost_point()

◆ lowest_point()

◆ operator=() [1/3]

◆ operator=() [2/3]

◆ operator=() [3/3]

◆ remove_vertex()

◆ rightmost_point()

◆ size()

◆ update_extreme_points()

◆ vertex_belong_polygon()

Member Data Documentation

◆ __is_closed

◆ highest

◆ leftmost

◆ lowest

◆ num_vertex

◆ rightmost

◆ vertex_list