Polygon and ConvexPolygon

Main author: Simon Rohou

The following classes provide a reliable representation of polygons and convex polygons.

Polygon class

class Polygon : public std::vector<Segment>

Represents a polygon (convex or non-convex) defined by its vertices enclosed in IntervalVectors.

A polygon can be constructed from a list of vertices (either Vector or IntervalVector) or from a list of edges (Segments). Internally, it stores a list of edges enclosed in Segments.

Subclassed by codac2::ConvexPolygon

Public Functions

Polygon(std::initializer_list<Vector> vertices)

Constructs a Polygon from an initializer list of Vector vertices.

Parameters:

vertices – A list of vertices defining the polygon.

Polygon(const std::vector<Vector> &vertices)

Constructs a Polygon from a vector of Vector vertices.

Parameters:

vertices – A vector of vertices defining the polygon.

explicit Polygon(const std::vector<IntervalVector> &vertices)

Constructs a Polygon from a vector of IntervalVector vertices.

Parameters:

vertices – A vector of IntervalVectors enclosing the polygon vertices.

Polygon(std::initializer_list<Segment> edges)

Constructs a Polygon from an initializer list of Segment edges.

Parameters:

edges – A list of Segments forming the polygon.

Polygon(const std::vector<Segment> &edges)

Constructs a Polygon from a vector of Segment edges.

Parameters:

edges – A vector of Segments forming the polygon.

explicit Polygon(const IntervalVector &x)

Constructs a box as a Polygon.

Typically used to create a rectangular polygon.

Parameters:

x – An IntervalVector representing the bounds of the polygon.

const std::vector<Segment> &edges() const

Returns the list of edges of the polygon.

Returns:

A constant reference to the vector of Segments.

std::list<IntervalVector> unsorted_vertices() const

Returns the list of unique vertices in no particular order.

If a vertex is involved several times in the polygon definition, then it will be returned only once in the output list.

Returns:

A list of IntervalVectors enclosing the unique vertices.

std::vector<IntervalVector> sorted_vertices() const

Returns the list of vertices sorted in polygonal order.

Returns:

A vector of IntervalVectors enclosing the ordered vertices.

IntervalVector box() const

Computes the bounding box of the polygon.

Returns:

The IntervalVector hull box.

bool is_empty() const

Checks whether the polygon is empty (has no vertex).

Returns:

True if the polygon is empty.

BoolInterval contains(const IntervalVector &p) const

Checks whether the polygon contains a given point.

Parameters:

p – The point to check, enclosed in an IntervalVector.

Returns:

A BoolInterval indicating possible containment.

bool operator==(const Polygon &p) const

Comparison operator.

Equality means that both polygons have the same edges, possibly in a different order (clockwise or counterclockwise).

Parameters:

p – Another polygon.

Returns:

True if both polygons are strictly equal.

Public Static Functions

static Polygon empty()

Provides an empty polygon.

Returns:

An empty polygon without vertices.

ConvexPolygon class

class ConvexPolygon : public codac2::Polygon

Represents a convex polygon defined by vertices enclosed in IntervalVectors.

A convex polygon is a special case of polygon where all internal angles are less than 180°, and every line segment between any two points in the polygon lies entirely within it. It inherits all functionality from Polygon and ensures convexity of the structure.

Public Functions

ConvexPolygon(std::initializer_list<Vector> vertices)

Constructs a ConvexPolygon from an initializer list of Vector vertices.

Parameters:

vertices – A list of vertices defining the convex polygon.

ConvexPolygon(const std::vector<Vector> &vertices, bool compute_convex_hull = true)

Constructs a ConvexPolygon from a vector of Vector vertices.

Parameters:

• vertices – A vector of vertices defining the convex polygon.

• compute_convex_hull – if true, will create the shape as the convex hull of the provided points. This option may be set to false when one can ensure that the points are already convex and provided in counterclockwise order. This would speed up computations, avoiding a Graham scan procedure.

explicit ConvexPolygon(const std::vector<IntervalVector> &vertices, bool compute_convex_hull = true)

Constructs a ConvexPolygon from a vector of IntervalVector vertices.

Parameters:

• vertices – A vector of IntervalVectors enclosing the convex polygon vertices.

• compute_convex_hull – if true, will create the shape as the convex hull of the provided points. This option may be set to false when one can ensure that the points are already convex and provided in counterclockwise order. This would speed up computations, avoiding a Graham scan procedure.

ConvexPolygon(std::initializer_list<Segment> edges)

Constructs a ConvexPolygon from an initializer list of Segment edges.

Parameters:

edges – A list of Segments forming the convex polygon.

ConvexPolygon(const std::vector<Segment> &edges)

Constructs a ConvexPolygon from a vector of Segment edges.

Parameters:

edges – A vector of Segments forming the convex polygon.

explicit ConvexPolygon(const IntervalVector &x)

Constructs a box as a ConvexPolygon.

Typically used to create a rectangular convex polygon.

Parameters:

x – An IntervalVector representing the bounds of the convex polygon.

Public Static Functions

static ConvexPolygon empty()

Provides an empty convex polygon.

Returns:

An empty convex polygon without vertices.

ConvexPolygon codac2::operator&(const ConvexPolygon &p1, const ConvexPolygon &p2)

Computes the intersection of two convex polygons.

The result is a new ConvexPolygon enclosing the intersection area. If the polygons do not intersect, the result is an empty convex polygon.

Parameters:

• p1 – The first convex polygon.

• p2 – The second convex polygon.

Returns:

A ConvexPolygon enclosing the intersection area.

PythonC++

# ConvexPolygons are defined from sets of vertices in any order
p1 = ConvexPolygon([ # drawn in red
  [4,2],[1,8],[2,10],[2,3],
  [1,6],[8,6],[7,3],[5,11],[7,10]
])
p2 = ConvexPolygon([ # drawn in blue
  [5,1],[7,1],[9,3],[4,3],[4,5],
  [9,6],[5,6],[8,8],[6,7]
])

p3 = p1 & p2

Intersection of two convex polygons.