Polygon and ConvexPolygon

Main author: Simon Rohou

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

Polygon class

class Polygon

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.

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)

Constructs a ConvexPolygon from a vector of Vector vertices.

Parameters:: vertices – A vector of vertices defining the convex polygon.

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

Constructs a ConvexPolygon from a vector of IntervalVector vertices.

Parameters:: vertices – A vector of IntervalVectors enclosing the convex polygon vertices.

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.

# 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

// ConvexPolygons are defined from sets of vertices in any order
ConvexPolygon p1({ // drawn in red
  {4,2},{1,8},{2,10},{2,3},
  {1,6},{8,6},{7,3},{5,11},{7,10}
});
ConvexPolygon p2({ // drawn in blue
  {5,1},{7,1},{9,3},{4,3},{4,5},
  {9,6},{5,6},{8,8},{6,7}
});

ConvexPolygon p3 = p1 & p2;

../../_images/convexpolygon_inter_example.png — Intersection of two convex polygons.