convex or concave polygon in 2D (not selfintersecting, no holes) More...

#include <simple_polygon_2d.h>

Inheritance diagram for lass::prim::SimplePolygon2D< T, DegeneratePolicy >:

[legend]

Public Member Functions
const TPoint &	operator[] (size_t iIndexOfVertex) const
	return vertex of polygon by its index, not wrapped, no bounds check.

TPoint &	operator[] (size_t iIndexOfVertex)
	return vertex of polygon by its index, not wrapped, no bounds check.

const TPoint &	at (int iIndexOfVertex) const
	return vertex of polygon by its index, but wrap around the bounds.

TPoint &	at (int iIndexOfVertex)
	return vertex of polygon by its index, but wrap around the bounds.

const TLineSegment	edge (int iIndexOfTailVertex) const
	return the edge of the polygon between vertices at(iIndex) and at(iIndex + 1).

const TVector	vector (int iIndexOfTailVertex) const
	return the vector between vertices at(iIndex) and at(iIndex + 1)\

void	add (const TPoint &iVertex)
	add a point at the "end" of the vertex list.

void	insert (int iIndexOfVertex, const TPoint &iVertex)
	insert a vertex at iIndex (so it will sit before the current at(iIndex)).

void	erase (int iIndexOfVertex)
	remove the vertex at(iIndex)

bool	isEmpty () const
	return true if polygon has no vertices

size_t	size () const
	return number of vertices

const TValue	signedArea () const
	return signed polygon area.

const TValue	area () const
	return area of the polygons surface.

const TValue	perimeter () const
	return sum of the lengths of all edges

const TPointH	vertexCentroid () const
	return the barycenter of all vertices.

const TPointH	surfaceCentroid () const
	return the centroid of the filled polygon.

bool	isSimple () const
	return true if polygon is simple, false if not.

bool	isConvex () const
	return true if polygon is convex, false if not.

Orientation	orientation () const
	return orientation of polygon.

bool	isReflex (int iIndexOfVertex) const
	return true if inner angle of vertex is reflex (is > 180 degrees).

bool	contains (const TPoint &iP) const
	return true when a point is inside or on a polygon.

void	flip ()
	flip orientation of polygon.

void	fixDegenerate ()
	fixes degenerate polygons as far as possible.

bool	isValid () const
	a simple polygon is valid if it is not degenerate.

Related Symbols
(Note that these are not member symbols.)
template<typename T, class DP, class NP, class PP>
Result	intersect (const SimplePolygon2D< T, DP > &polygon, const Ray2D< T, NP, PP > &ray, T &t, const T &tMin=T())
	Find the intersection of a ray and a triangle by their parameter t on the ray.

template<typename T, typename DP, typename PP>
bool	intersects (const SimplePolygon2D< T, DP > &poly, const LineSegment2D< T, PP > &segment)
	O(N) with N is size of poly.

template<typename T, typename DP, typename PP>
bool	intersects (const LineSegment2D< T, PP > &segment, const SimplePolygon2D< T, DP > &poly)
	O(N) with N is size of poly.

template<typename T, typename DP1, typename DP2>
bool	intersects (const SimplePolygon2D< T, DP1 > &a, const SimplePolygon2D< T, DP2 > &b)
	O(M+N) with M and N the sizes of the polygons.

Detailed Description

template<typename T, class DegeneratePolicy = NoDegenerate>
class lass::prim::SimplePolygon2D< T, DegeneratePolicy >

convex or concave polygon in 2D (not selfintersecting, no holes)

Author: Bram de Greve [BdG]

Warning: SimplePolygon2D only ASSUMES it's simple. there's no guarantee at any time. It's your own responsibility to keep it simple. We do it this way because it's just to costly to check it at every access to the polygon. However, we provide some methods to check it yourself.

Definition at line 73 of file simple_polygon_2d.h.

Member Function Documentation

◆ at() [1/2]

template<typename T, class DP>

const SimplePolygon2D< T, DP >::TPoint & lass::prim::SimplePolygon2D< T, DP >::at ( int iIndexOfVertex ) const

return vertex of polygon by its index, but wrap around the bounds.

this->at(-1) will return the same vertex as this->at(this->size() - 1);

Exceptions

an	exception is thrown if polygon is empty

Definition at line 113 of file simple_polygon_2d.inl.

References at().

Referenced by at(), at(), edge(), fixDegenerate(), and vector().

◆ at() [2/2]

template<typename T, class DP>

SimplePolygon2D< T, DP >::TPoint & lass::prim::SimplePolygon2D< T, DP >::at ( int iIndexOfVertex )

return vertex of polygon by its index, but wrap around the bounds.

this->at(-1) will return the same vertex as this->at(this->size() - 1);

Exceptions

an	exception is thrown if polygon is empty

Definition at line 129 of file simple_polygon_2d.inl.

References at().

◆ edge()

template<typename T, class DP>

const SimplePolygon2D< T, DP >::TLineSegment lass::prim::SimplePolygon2D< T, DP >::edge ( int iIndexOfTailVertex ) const

return the edge of the polygon between vertices at(iIndex) and at(iIndex + 1).

Exceptions

an	exception is thrown if polygon has less than two vertices

Definition at line 145 of file simple_polygon_2d.inl.

References at(), and edge().

Referenced by edge(), lass::prim::SimplePolygon2D< T, NoDegenerate >::intersects(), lass::prim::SimplePolygon2D< T, NoDegenerate >::intersects(), and isSimple().

◆ add()

template<typename T, class DP>

void lass::prim::SimplePolygon2D< T, DP >::add ( const TPoint & iVertex )

add a point at the "end" of the vertex list.

this is almost the same as insert(0, iVertex) with the difference that add(iVertex) is also valid for empty polygons.

Definition at line 170 of file simple_polygon_2d.inl.

References add().

Referenced by add(), and lass::prim::SimplePolygon3D< T, PlaneEquationPolicy, PlaneNormalizingPolicy >::mapping().

◆ signedArea()

template<typename T, class DP>

const SimplePolygon2D< T, DP >::TValue lass::prim::SimplePolygon2D< T, DP >::signedArea ( ) const

return signed polygon area.

The area of a convex polygon is defined to be positive if the points are arranged in a counterclockwise order, and negative if they are in clockwise order., Eric W. Weisstein. "Polygon Area." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/PolygonArea.html

Algorithm:: comp.graphics.algorithms Frequently Asked Questions: Subject 2.01: "How do I find the area of a polygon?" http://www.faqs.org/faqs/graphics/algorithms-faq/

https://www.johndcook.com/blog/2018/09/26/polygon-area/

Warning: polygon must be simple accoring degenerate policy.

Definition at line 241 of file simple_polygon_2d.inl.

References signedArea(), and size().

Referenced by area(), fixDegenerate(), isReflex(), isValid(), and signedArea().

◆ area()

template<typename T, class DP>

const SimplePolygon2D< T, DP >::TValue lass::prim::SimplePolygon2D< T, DP >::area ( ) const

return area of the polygons surface.

The area of a surface is the amount of material needed to "cover" it completely, Eric W. Weisstein. "Area." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/Area.html

Warning: polygon must be simple accoring DegeneratePolicy.

Definition at line 274 of file simple_polygon_2d.inl.

References lass::num::abs(), area(), and signedArea().

Referenced by area().

◆ vertexCentroid()

template<typename T, class DP>

const SimplePolygon2D< T, DP >::TPointH lass::prim::SimplePolygon2D< T, DP >::vertexCentroid ( ) const

return the barycenter of all vertices.

The vertex centroid is the homogenous sum of all vertices.

Warning: for non-convex polygons, it's NOT guaranteed that this center is inside the polygon.

Definition at line 319 of file simple_polygon_2d.inl.

References size(), and vertexCentroid().

Referenced by surfaceCentroid(), and vertexCentroid().

◆ surfaceCentroid()

template<typename T, class DP>

const SimplePolygon2D< T, DP >::TPointH lass::prim::SimplePolygon2D< T, DP >::surfaceCentroid ( ) const

return the centroid of the filled polygon.

Eric W. Weisstein. "Geometric Centroid." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/GeometricCentroid.html

Algorithm:: comp.graphics.algorithms Frequently Asked Questions: Subject 2.02: "How can the centroid of a polygon be computed?" http://www.faqs.org/faqs/graphics/algorithms-faq/

Warning: for non-convex polygons, it's NOT guaranteed that this center is inside the polygon.

Definition at line 346 of file simple_polygon_2d.inl.

References size(), surfaceCentroid(), and vertexCentroid().

Referenced by surfaceCentroid().

◆ isSimple()

template<typename T, class DP>

bool lass::prim::SimplePolygon2D< T, DP >::isSimple ( ) const

return true if polygon is simple, false if not.

A polygon P is said to be simple (or Jordan) if the only points of the plane belonging to two polygon edges of P are the polygon vertices of P. Such a polygon has a well defined interior and exterior. Simple polygons are topologically equivalent to a disk., Eric W. Weisstein. "Simple Polygon." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/SimplePolygon.html

A polygon with less than four vertices is always simple.

Warning: this is a brute force test. we simple test for all edges if they are not intersecting Hence, this is O(n^2).

Definition at line 380 of file simple_polygon_2d.inl.

References edge(), intersect(), isSimple(), lass::prim::rNone, lass::prim::rOne, and size().

Referenced by fixDegenerate(), isSimple(), and isValid().

◆ isConvex()

template<typename T, class DP>

bool lass::prim::SimplePolygon2D< T, DP >::isConvex ( ) const

return true if polygon is convex, false if not.

A planar polygon is convex if it contains all the line segments connecting any pair of its points. Thus, for example, a regular pentagon is convex, while an indented pentagon is not. A planar polygon that is not convex is said to be a concave polygon, Eric W. Weisstein. "Convex Polygon." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/ConvexPolygon.html

A simple polygon is convex if all the cross products of adjacent edges will be the same sign (we ignore zero cross products of colinear edges, only + or - are taken in account), a concave polygon will have a mixture of cross product signs.

A polygon with less than three vertices is always convex. A polygon with all coincident. vertices is considered convex if DegeneratePolicy allows this.

Warning: polygon must be simple and should not have coincident vertices, according DegeneratePolicy.

Definition at line 432 of file simple_polygon_2d.inl.

References isConvex(), lass::num::sign(), sign(), size(), and vector().

Referenced by isConvex().

◆ orientation()

template<typename T, class DP>

Orientation lass::prim::SimplePolygon2D< T, DP >::orientation ( ) const

return orientation of polygon.

Warning: polygon must be simple accoring DegeneratePolicy.

Definition at line 286 of file simple_polygon_2d.inl.

References lass::prim::oClockWise, lass::prim::oCounterClockWise, lass::prim::oInvalid, and orientation().

Referenced by orientation().

◆ isReflex()

template<typename T, class DP>

bool lass::prim::SimplePolygon2D< T, DP >::isReflex ( int iIndexOfVertex ) const

return true if inner angle of vertex is reflex (is > 180 degrees).

Reflect Angle: An angle more than 180�, Eric W. Weisstein. "Reflex Angle." From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/ReflexAngle.html

test if signedArea() and perdDot(...) have different sign. if one of them is zero, it will return false by default.

Warning: polygon must be simple accoring DegeneratePolicy.

Definition at line 477 of file simple_polygon_2d.inl.

References isEmpty(), isReflex(), signedArea(), and vector().

Referenced by isReflex().

◆ contains()

template<typename T, class DP>

bool lass::prim::SimplePolygon2D< T, DP >::contains ( const TPoint & iP ) const

return true when a point is inside or on a polygon.

When a point lies on a polygon edge the answer can either be true or false but in a way that for a meshing the answer will only be true for one polygon. More precise: for polygons sharing an edge only one of them will return true for a point on the edge. For an explanation of how this exactly works: http://www.ecse.rpi.edu/Homepages/wrf/geom/pnpoly.html (Wm Randolph Franklin)

Algorithm:: comp.graphics.algorithms Frequently Asked Questions: Subject 2.03: "How do I find if a point lies within a polygon?" http://www.faqs.org/faqs/graphics/algorithms-faq/

Definition at line 502 of file simple_polygon_2d.inl.

References contains(), and size().

Referenced by contains(), and lass::prim::SimplePolygon2D< T, NoDegenerate >::intersects().

◆ fixDegenerate()

template<typename T, class DP>

void lass::prim::SimplePolygon2D< T, DP >::fixDegenerate ( )

fixes degenerate polygons as far as possible.

things that can be repared are:

coincident vertices: if two or more adjacent vertices are coincident, they can be reduced to one vertex.
colinear edges: if two or more adjacent edges are colinear, they can be merged to one edge.
zero area: if a polygon has no area, this is pretty much the same as an empty polygon. All vertices will be removed.

Things that can't repared (and will cause an exception to be thrown) are:

non-simple polygons: there's no way we can repare polygons that are not simple, so we don't even try to! An exception is thrown regardless the DegeneratePolicy.

Definition at line 555 of file simple_polygon_2d.inl.

References at(), erase(), fixDegenerate(), isSimple(), signedArea(), size(), and vector().

Referenced by fixDegenerate().

Friends And Related Symbol Documentation

◆ intersect()

template<typename T, class DP, class NP, class PP>

Result intersect	(	const SimplePolygon2D< T, DP > &	polygon,
		const Ray2D< T, NP, PP > &	ray,
		T &	t,
		const T &	tMin = T() )

Find the intersection of a ray and a triangle by their parameter t on the ray.

Parameters

polygon	[in] the simple polygon
ray	[in] the ray
t	[out] the parameter of the intersection point > tMin.
tMin	[in] the minimum t that may be returned as valid intersection.

Returns

rNone no intersections with t > tMin found t is not assigned.
rOne a intersection with t > tMin is found t is assigned.

Definition at line 71 of file ray_2d_simple_polygon_2d.h.

Referenced by isSimple().

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

Public Member Functions

Related Symbols

Detailed Description

Member Function Documentation

◆ at() [1/2]

◆ at() [2/2]

◆ edge()

◆ add()

◆ signedArea()

◆ area()

◆ vertexCentroid()

◆ surfaceCentroid()

◆ isSimple()

◆ isConvex()

◆ orientation()

◆ isReflex()

◆ contains()

◆ fixDegenerate()

Friends And Related Symbol Documentation

◆ intersect()