Geometry — 2D

Typedefs

typedef CGAL::Arrangement_2<Traits_2> Arrangement_2
typedef Arrangement_2::Ccb_halfedge_const_circulator Ccb_halfedge_const_circulator
typedef Arrangement_2::Face_const_iterator Face_const_iterator
class Arrangement2
#include <arrangement2.h>

Arrangement2.

Class to handle 2D arrangements

Public Functions

Arrangement2() = default

Default Constructor.

Initializes an empty arrangement.

std::vector<Polygon2> getBoundedFaces()

Get the bounded faces of the arrangement.

Reconstructs polygons from all closed, bounded regions delineated by the line segments in the arrangement.

Returns:

A vector of bounded faces represented as Polygon2 instances.

std::vector<Polygon2> getUnboundedFaces()

Get the unbounded faces of the arrangement.

Reconstructs polygons from regions of the arrangement extending to infinity.

Returns:

A vector of unbounded faces represented as Polygon2 instances.

void insert(const Polygon2 &polygon)

Inserts a polygon into the arrangement.

Converts the outline and hole boundaries of a Polygon2 to line segments and adds them to the CGAL arrangement.

Parameters:

polygon – The polygon to insert.

void insert(const Polyline2 &polyline)

Inserts a polyline into the arrangement.

Adds the line segments comprising the Polyline2 to the CGAL arrangement.

Parameters:

polyline – The polyline to insert.

Private Functions

std::vector<Polygon2> getFaces(uint8_t type)

Get the faces of the arrangement.

Parameters:

type – 0 for bounded faces, 1 for unbounded faces, 2 for all faces

Returns:

A vector of faces

Private Members

Arrangement_2 m_arrangement

The arrangement.

Defines

INT_POINT_MULTIPLIER
class Polygon2 : public Polygon_2
#include <polygon2.h>

A class for storing and manipulating polygons in 2D space.

Public Functions

void add_hole(const Polygon2 &hole)

Appends a single hole to the polyon’s holes list.

Parameters:

hole – The hole to append.

std::pair<Point_2, Point_2> bounding_box() const

Calculates the bounding box of the polygon.

Returns:

A pair of points representing the minimum and maximum corners of the bounding box.

std::vector<Polygon2> diff(const Polygon2 &other) const

Calculates the difference of the polygon with another polygon.

Parameters:

other – The other polygon.

Returns:

A vector of polygons representing the difference.

std::vector<Polygon2> diff(const std::vector<Polygon2> &other) const

Calculates the difference of the polygon with a vector of polygons.

Parameters:

other – The vector of polygons to subtract.

Returns:

A vector of polygons representing the difference.

std::pair<std::vector<Polygon2>, std::vector<Polyline2>> do_clip(const std::vector<Polyline2> &polylines) const

Clips an arbitrary set of passing polylines using this polygon’s shape.

Parameters:

polylines – Line elements to clip.

Returns:

Bounded regions mapping to closed loops, and segments mapping to un-closed polylines.

std::vector<Polygon2> do_union(const Polygon2 &other) const

Calculates the union of the polygon with another polygon.

Parameters:

other – The other polygon.

Returns:

A vector of valid polygons representing the union.

std::vector<Polygon2> do_union(const std::vector<Polygon2> &others) const

Calculates the union of the polygon with a vector of polygons.

Parameters:

others – Vector of other polygons.

Returns:

A vector of polygons representing the unified areas.

double double_area() const

Calculates twice the signed area of the polygon.

Returns:

Double area value.

void draw()

Displays the polygon layout interactively using CGAL viewer.

std::vector<Polygon2> holes() const

Returns the holes of the polygon.

Returns:

A vector of holes.

bool inside(const Point_2 &point) const

Checks if a point is inside the polygon.

Parameters:

point – The point to check.

Returns:

True if the point is inside the polygon, false otherwise.

std::vector<Polygon2> intersect(const Polygon2 &other) const

Calculates the intersection of the polygon with another polygon.

Parameters:

other – The other polygon.

Returns:

A vector of polygons representing the intersection.

std::vector<Polygon2> intersect(const std::vector<Polygon2> &others) const

Calculates the intersection of the polygon with a vector of polygons.

Parameters:

others – The vector of polygons.

Returns:

A vector of polygons representing the intersection.

bool is_ccw() const

Checks if the points in the polygon are in counter-clockwise order.

Returns:

True if the points are in counter-clockwise order, false otherwise.

std::vector<Polygon2> offset(double distance) const

Creates offset contours around the exterior boundary and its holes.

Parameters:

distance – Positive for outward expansion, negative for inward shrinking.

Returns:

A vector of offset polygons.

bool on_boundary(const Point_2 &point) const

Checks if a point is on the boundary of the polygon.

Parameters:

point – The point to check.

Returns:

True if the point is on the boundary of the polygon, false otherwise.

operator std::vector<glm::vec2>() const

Converts the polygon to a vector of 2D vectors.

Returns:

A vector of 2D vectors representing the points of the polygon.

Polygon2() = default

Default constructor.

Creates an empty Polygon2 object.

Polygon2(const Polygon_2 &polygon)

Constructor.

Creates an exact copy of a CGAL Polygon_2.

Parameters:

polygon – The CGAL polygon.

Polygon2(const std::vector<glm::dvec2> &points)

Constructor.

Creates a Polygon2 object from a sequence of points with double precision.

Parameters:

points – The points defining the polygon as double precision.

Pre:

There must be at least 3 points in the sequence.

Pre:

The the first and last point in the sequence must be the same.

Polygon2(const std::vector<glm::vec2> &points)

Constructor.

Creates a Polygon2 object from a sequence of points.

Parameters:

points – The points defining the polygon.

Pre:

There must be at least 3 points in the sequence.

Pre:

The the first and last point in the sequence must be the same.

Polygon2(const std::vector<Point_2> &points)

Constructor.

Creates a Polygon2 object from a sequence of points with single precision.

Parameters:

points – The points defining the polygon as single precision.

Pre:

There must be at least 3 points in the sequence.

Pre:

The the first and last point in the sequence must be the same.

void reverse()

Reverses the order of the points in the polygon.

void scale(glm::dvec2 scale)

Scales the polygon by a factor about the origin.

void set_holes(const std::vector<Polygon2> &holes)

Sets the holes of the polygon, replacing existing ones.

Parameters:

holes – A vector of holes to set.

void simplify(double tolerance = 0.001)

Simplifies the polygon by removing nearly co-linear points.

Parameters:

tolerance – The maximum distance a point can be from the line segment formed by its neighboring points to be considered nearly co-linear. Defaults to 0.001.

Polyline2 to_polyline() const

Converts the exterior boundary to a Polyline2.

Returns:

The perimeter as a sequence of line segments.

void translate(glm::dvec2 translation)

Translates the polygon by a vector.

Public Static Functions

static std::pair<std::vector<Polygon2>, std::vector<Polyline2>> Clip(const std::vector<Polygon2> &polygons, const std::vector<Polyline2> &polylines)

Cuts geometric polylines tracking over bounding areas.

Parameters:

  • polygons – Clipping bounding shapes.

  • polylines – Target curve trajectories.

Returns:

Pair with polygon paths forming closed boundaries and polyline splits.

static std::vector<Polygon2> Difference(const std::vector<Polygon2> &polygons, const std::vector<Polygon2> &others)

Static difference of a set of polygons from a base set.

Parameters:

  • polygons – Base set of polygons.

  • others – Polygons to subtract.

Returns:

Difference polygon boundaries.

static std::vector<Polygon2> Intersection(const std::vector<Polygon2> &polygons, const std::vector<Polygon2> &others)

Calculates the difference of the polygon with a vector of polygons.

Parameters:

others – The vector of polygons.

Returns:

A vector of polygons representing the difference.

static std::vector<Polygon2> Offset(const std::vector<Polygon2> &polygons, double distance)

Static offset of a set of polygons by a shared contour delta.

Parameters:

  • polygons – The input polygons to scale offsets for.

  • distance – Expanding offset positive / sinking offset negative.

Returns:

An offset vector of polygons.

static std::vector<Polygon2> Union(const std::vector<Polygon2> &polygons, const std::vector<Polygon2> &others)

Static union of multiple sets of polygons.

Parameters:

  • polygons – The first set of polygons.

  • others – The second set of polygons.

Returns:

Merged polygon boundaries outlining the unified area of both lists combined.

Private Members

std::vector<Polygon2> m_holes
class Polyline2 : public std::vector<Segment_2>
#include <polyline2.h>

A class for storing and manipulating polylines.

A polyline is a sequence of line segments, defined by a sequence of points.

Public Functions

void append(const Polyline2 &polyline)

Appends another polyline’s segments to the end of this polyline.

Parameters:

polyline – The polyline to append.

double length() const

Calculates the total distance along the polyline.

Returns:

The length of the polyline.

std::vector<Point_2> points() const

Returns the points of the polyline.

Returns:

The points of the polyline.

Polyline2() = default

Default constructor.

Creates an empty Polyline2 object.

Polyline2(const std::vector<glm::dvec2> &points)

Constructor.

Creates a Polyline2 object from a sequence of points with double precision.

See also

Polygon2 instead.

Parameters:

points – The points defining the polyline as double precision.

Pre:

There must be at least 2 points in the sequence.

Pre:

The the first and last point must NOT be the same. If they are the same,

Polyline2(const std::vector<glm::vec2> &points)

Constructor.

Creates a Polyline2 object from a sequence of points with single precision.

See also

Polygon2 instead.

Parameters:

points – The points defining the polyline as single precision.

Pre:

There must be at least 2 points in the sequence.

Pre:

The the first and last point must NOT be the same. If they are the same,

Polyline2(const std::vector<Point_2> &points)

Constructor.

Creates a Polyline2 object from a sequence of points.

See also

Polygon2 instead.

Parameters:

points – The points defining the polyline.

Pre:

There must be at least 2 points in the sequence.

Pre:

The the first and last point must NOT be the same. If they are the same,

void prepend(const Polyline2 &polyline)

Prepends another polyline’s segments to the start of this polyline.

Parameters:

polyline – The polyline to prepend.

void reverse()

Reverses the order of the points in the polyline.

std::vector<Segment_2> segments() const

Returns the list of line segments making up the polyline.

Returns:

The list of segments.

void simplify(double tolerance = 0.001)

Remove co-linear points from the polyline.

Parameters:

tolerance – The tolerance for co-linearity.

void translate(const Point_2 &translation)

Translates all points in the polyline by a given vector.

Parameters:

translation – The vector to translate by.

Private Static Functions

static double Distance(const Point_2 &a, const Point_2 &b)
class MarchingSquares
#include <marching_squares.h>

A class to compute iso-lines from a 2D scalar field using the marching squares algorithm.

This class provides a method to compute iso-lines from a 2D scalar field using the marching squares algorithm. An arbitrary function can be evaluated at each point in the 2D scalar field to determine the iso-value at that point by passing a function pointer.

Public Types

typedef std::pair<std::vector<Polygon2>, std::vector<Polyline2>> CrossSection

This class returns a CrossSection which is a pair of vectors of polygons and polylines.

Note

The polygons represent the closed regions of the iso-lines and the polylines represent open iso-lines.

Public Static Functions

static std::pair<std::vector<glm::dvec2>, std::vector<glm::ivec2>> ComputeIsoLinesDistribution(std::function<double(double, double, double)> &geometry_evaluator, std::function<std::unordered_map<uint8_t, float>(double, double, double)> &distribution_evaluator, size_t channel, double z, const glm::dvec2 &min, const glm::dvec2 &max, const glm::dvec2 &cell_size, double iso_value = 0.0, double epsilon = 1e-12)

Compute the iso-lines of a 2D scalar field accounting for volume fractions.

Parameters:

  • geometry_evaluator – A function evaluating the boundary geometry of the part. Points <= 0 are inside the part.

  • distribution_evaluator – A function evaluating the continuous material distributions at a point. Returns a map of material channels to fractions.

  • channel – The material channel index to track the iso-value for.

  • z – The z-value of the 2D slice to evaluate at.

  • min – The minimum x and y block coordinates in the plane.

  • max – The maximum x and y block coordinates in the plane.

  • cell_size – Dimensions of each marching square cell.

  • iso_value – The iso-value to compute the iso-lines at.

  • epsilon – Epsilon for floating comparisons.

Returns:

A pair forming raw unconnected vertices and edge indices.

static std::pair<std::vector<glm::dvec2>, std::vector<glm::ivec2>> ComputeIsoLinesGeometry(std::function<double(double, double, double)> &evaluator, double z, const glm::dvec2 &min, const glm::dvec2 &max, const glm::dvec2 &cell_size, double iso_value = 0.0, double epsilon = 1e-12)

Compute the iso-lines of a 2D scalar field using the marching squares algorithm.

Warning

The vertices and edges are not connected, so they need to be stitched into polylines using the StitchIsoLinesIntoPolylines method.

Parameters:

  • evaluator – A function pointer to the function that evaluates the scalar field at a given point. This function must take in three arguments: x, y, and z and return a double. The reason that the z argument is included is to allow for the evaluation of a 3D scalar field slice. This avoids the need extract a slice from a 3D scalar field first.

  • z – The z-value of the 2D slice to evaluate the scalar field at.

  • min – The minimum x and y values of the 2D slice.

  • max – The maximum x and y values of the 2D slice.

  • cell_size – The size of the cells in the 2D slice.

  • iso_value – The iso-value to compute the iso-lines at.

  • epsilon – The epsilon value to use when comparing floating point numbers. If you have problems with the iso-lines not connecting during stitching try increasing this value.

Returns:

A pair of vectors of vertices and edges that represent the unconnected iso-lines.

static CrossSection ComputeStitchedIsoLinesDistribution(std::function<double(double, double, double)> &geometry_evaluator, std::function<std::unordered_map<uint8_t, float>(double, double, double)> &distribution_evaluator, size_t channel, double z, const glm::dvec2 &min, const glm::dvec2 &max, const glm::dvec2 &cell_size, double iso_value = 0.0, double epsilon = 1e-12)

A convenience method computing the iso-lines for material distributions and stitching them into polylines.

See also

ComputeIsoLinesDistribution and StitchIsoLinesIntoPolylines

Parameters:

  • geometry_evaluator – A function evaluating the boundary geometry of the part.

  • distribution_evaluator – A function evaluating the continuous material distributions at a point.

  • channel – The material channel to track the iso-value for.

  • z – The z-value of the 2D slice to run evaluation at.

  • min – The minimum x and y coordinates.

  • max – The maximum x and y coordinates.

  • cell_size – Dimensions of each marching square cell.

  • iso_value – The iso-value to compute the distribution iso-lines at.

  • epsilon – Floating point comparison epsilon.

Returns:

A pair containing closed polygon boundaries and open polylines.

static CrossSection ComputeStitchedIsoLinesGeometry(std::function<double(double, double, double)> &evaluator, double z, const glm::dvec2 &min, const glm::dvec2 &max, const glm::dvec2 &cell_size, double iso_value = 0.0, double epsilon = 1e-12)

A convenience method to compute the iso-lines of a 2D scalar field using the marching squares algorithm and then stitch them into polylines using a depth-first search.

See also

ComputeIsoLines and StitchIsoLinesIntoPolylines

Parameters:

  • evaluator – A function pointer to the function that evaluates the scalar field at a given point. This function must take in three arguments: x, y, and z and return a double. The reason that the z argument is included is to allow for the evaluation of a 3D scalar field slice. This avoids the need extract a slice from a 3D scalar field first.

  • z – The z-value of the 2D slice to evaluate the scalar field at.

  • min – The minimum x and y values of the 2D slice.

  • max – The maximum x and y values of the 2D slice.

  • cell_size – The size of the cells in the 2D slice.

  • iso_value – The iso-value to compute the iso-lines at.

  • epsilon – The epsilon value to use when comparing floating point numbers. If you have problems with the iso-lines not connecting during stitching try increasing this value.

Returns:

A pair of vectors of polygons and polylines that represent the CrossSection.

static CrossSection StitchIsoLinesIntoPolylines(const std::vector<glm::dvec2> &vertices, const std::vector<glm::ivec2> &edges)

Stitch the iso-lines into polylines/.

This method takes the vertices and edges from the ComputeIsoLines method and stitches them into polylines. It does this by performing a depth-first search (DFS) over the edges to determine the connected components of the iso-lines. Special care is taken to allow for cycles graph in the case the contours form closed polygons.

Parameters:

  • vertices – The vertices of the iso-lines.

  • edges – The edges of the iso-lines.

Returns:

A pair of vectors of polygons and polylines that represent the CrossSection.

Private Static Functions

static glm::dvec2 Interpolate(const glm::dvec2 &p1, const glm::dvec2 &p2, double val1, double val2, double iso_value = 0.0, double epsilon = 1e-12)

Linearly interpolate between two points.

Parameters:

  • p1 – The first point.

  • p2 – The second point.

  • val1 – The value at the first point.

  • val2 – The value at the second point.

  • iso_value – The iso-value to interpolate at.

Returns:

The interpolated point.

static size_t VectorInsert(std::vector<glm::dvec2> &vertices, const glm::dvec2 &vertex, double epsilon = 1e-12)

Insert a vertex into a vector of vertices if it does not already exist.

Parameters:

  • vertices – The vector of vertices to insert the vertex into.

  • vertex – The vertex to insert.

  • epsilon – The epsilon value to use when comparing floating point numbers.

Returns:

The index of the vertex in the vector.