Geometry — 2D#
Typedefs
-
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>
A 2D arrangement of line segments (a CGAL Arrangement_2).
Inserted polygons and polylines are split at every crossing, and the plane is divided into faces. A segment arrangement has exactly one unbounded face (everything outside the inserted geometry); all other faces are bounded.
Public Functions
-
Arrangement2() = default#
Default Constructor.
Initializes an empty arrangement.
-
std::vector<Polygon2> getBoundedFaces()#
Get the bounded faces of the arrangement.
Builds one Polygon2 per bounded face from its outer boundary (counter-clockwise), with the face’s inner boundaries attached as holes (clockwise). Faces whose outer boundary is not a single cycle are skipped.
- Returns:
A vector of bounded faces represented as Polygon2 instances.
-
std::vector<Polygon2> getUnboundedFaces()#
Get the outer boundaries of the arrangement, taken from its single unbounded face.
The unbounded face has no outer boundary of its own. Instead, this returns one Polygon2 per inner boundary of the unbounded face, which is the outline of each connected component of the inserted geometry, traversed clockwise. No polygon extends to infinity. Dangling polyline edges are traversed on both sides, so their outlines can be degenerate.
- Returns:
One polygon per connected component outline.
-
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.
-
std::vector<std::shared_ptr<Profile>> profiles()#
Get the bounded faces as profiles, each with its holes.
- Returns:
One Profile per bounded face (see getBoundedFaces()).
Private Functions
-
std::vector<Polygon2> getFaces(uint8_t type)#
Get the faces of the arrangement.
- Parameters:
type – 0 for the bounded faces, 1 for the outlines of the unbounded face. Other values are not supported: they reach outer_ccb() on the unbounded face, which fails a CGAL precondition.
- Returns:
A vector of faces
Private Members
-
Arrangement_2 m_arrangement#
The arrangement.
-
Arrangement2() = default#
Defines
-
INT_POINT_MULTIPLIER#
-
class Polygon2 : public Polygon_2#
- #include <polygon2.h>
A class for storing and manipulating polygons in 2D space.
The vertices are the outer boundary, stored without repeating the first point. Holes are stored as a separate list of Polygon2 objects. Most queries (is_ccw, inside, on_boundary, bounding_box, double_area, simplify) look only at the outer boundary; the booleans, offset and clip also use the holes.
Public Functions
-
void add_hole(const Polygon2 &hole)#
Appends a single hole to the polygon’s holes list.
- Parameters:
hole – The hole to append.
-
std::pair<Point_2, Point_2> bounding_box() const#
Calculates the bounding box of the outer boundary.
- Throws:
std::runtime_error – If the polygon is empty.
- Returns:
A pair of points representing the minimum and maximum corners of the bounding box.
-
std::vector<Polygon2> diff(const Polygon2 &other) const#
Subtracts another polygon from this one.
Same as Difference({*this}, {other}). See do_union(const Polygon2&) for the output format.
- Parameters:
other – The polygon to subtract.
- Returns:
The result contours (holes as separate clockwise polygons).
-
std::vector<Polygon2> diff(const std::vector<Polygon2> &other) const#
Subtracts a vector of polygons from this one.
Same as Difference({*this}, other). See do_union(const Polygon2&) for the output format.
- Parameters:
other – The vector of polygons to subtract.
- Returns:
The result contours (holes as separate clockwise polygons).
-
std::pair<std::vector<Polygon2>, std::vector<Polyline2>> do_clip(const std::vector<Polyline2> &polylines) const#
Clips polylines to the inside of this polygon.
Same as Clip({*this}, polylines).
- Parameters:
polylines – The polylines to clip.
- Returns:
A pair of (closed polygons, clipped polylines). The first element is always empty; see Clip().
-
std::vector<Polygon2> do_union(const Polygon2 &other) const#
Calculates the union of the polygon with another polygon.
Same as Union({*this}, {other}). The booleans use Clipper2 with the even-odd fill rule. Each operand set (with its holes) is filled even-odd, so polygons that overlap inside one set cancel (XOR) there. The result is one Polygon2 per output contour: outer contours are counter-clockwise, and holes come back as separate clockwise polygons, not attached through holes().
- Parameters:
other – The other polygon.
- Returns:
The result contours (holes as separate clockwise polygons).
-
std::vector<Polygon2> do_union(const std::vector<Polygon2> &others) const#
Calculates the union of the polygon with a vector of polygons.
Same as Union({*this}, others). See do_union(const Polygon2&) for the output format.
- Parameters:
others – Vector of other polygons.
- Returns:
The result contours (holes as separate clockwise polygons).
-
double double_area() const#
Calculates the signed area of the outer boundary.
Despite the name, this is the signed area itself, not twice it. It is positive for a counter-clockwise boundary and negative for a clockwise one. Holes are not subtracted.
- Returns:
The signed area as a double.
-
void draw()#
Shows the outer boundary in CGAL’s basic viewer (a debugging aid).
Only opens a window when CGAL_USE_BASIC_VIEWER is defined (CGAL built with Qt).
-
bool inside(const Point_2 &point) const#
Checks if a point is strictly inside the outer boundary.
Holes are ignored, and a point on the boundary is not inside.
- Parameters:
point – The point to check.
- Returns:
True if the point is inside the outer boundary, false otherwise.
-
std::vector<Polygon2> intersect(const Polygon2 &other) const#
Calculates the intersection of the polygon with another polygon.
Same as Intersection({*this}, {other}). See do_union(const Polygon2&) for the output format.
- Parameters:
other – The other polygon.
- Returns:
The result contours (holes as separate clockwise polygons).
-
std::vector<Polygon2> intersect(const std::vector<Polygon2> &others) const#
Calculates the intersection of the polygon with a vector of polygons.
Same as Intersection({*this}, others). See do_union(const Polygon2&) for the output format.
- Parameters:
others – The vector of polygons.
- Returns:
The result contours (holes as separate clockwise polygons).
-
bool is_ccw() const#
Checks if the points of the outer boundary are in counter-clockwise order.
- Returns:
True if the points are in counter-clockwise order, false otherwise.
-
std::vector<Polygon2> offset(double distance) const#
Offsets the polygon and its holes.
Same as Offset({*this}, distance).
- Parameters:
distance – Positive grows the region, negative shrinks it.
- Returns:
Counter-clockwise outer polygons with their holes attached. See Offset().
-
bool on_boundary(const Point_2 &point) const#
Checks if a point is on the outer boundary of the polygon.
Hole boundaries are not checked.
- Parameters:
point – The point to check.
- Returns:
True if the point is on the outer boundary, false otherwise.
-
operator std::vector<glm::vec2>() const#
Converts the outer boundary to a vector of 2D vectors (single precision, holes dropped).
- Returns:
A vector of 2D vectors representing the points of the polygon.
-
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.
The sequence may be open or closed. If the last point equals the first, it is dropped.
- Parameters:
points – The points defining the polygon as double precision.
- Pre:
There must be at least 3 points in the sequence.
-
Polygon2(const std::vector<glm::vec2> &points)#
Constructor.
Creates a Polygon2
object from a sequence of points.
The sequence may be open or closed. If the last point equals the first, it is dropped.
- Parameters:
points – The points defining the polygon.
- Pre:
There must be at least 3 points in the sequence.
-
Polygon2(const std::vector<Point_2> &points)#
Constructor.
Creates a Polygon2
object from a sequence of exact points.
The sequence may be open or closed. If the last point equals the first, it is dropped.
- Parameters:
points – The points defining the polygon.
- Pre:
There must be at least 3 points in the sequence.
-
void reverse()#
Reverses the order of the points of the outer boundary. Holes are not changed.
-
void scale(glm::dvec2 scale)#
Scales the polygon and its holes about the origin.
- Parameters:
scale – The per-axis scale factors.
-
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)#
Removes nearly collinear points from the outer boundary.
Walks the boundary in order and drops a point when the triangle it forms with the previous kept point and the next point has an area below
tolerance. The first point is always kept. The polygon is rebuilt from the remaining points, so its holes are dropped.- Throws:
std::runtime_error – If fewer than 3 points would remain. An empty polygon is left unchanged.
- Parameters:
tolerance – The triangle-area threshold, in squared length units (not a distance). Defaults to 0.001.
-
Polyline2 to_polyline() const#
Converts the outer boundary to a Polyline2.
The polyline is closed by repeating the first point at the end. Holes are dropped.
- Returns:
The perimeter as a sequence of line segments.
-
std::shared_ptr<Profile> to_profile() const#
Converts the polygon and its holes to a Profile (the general closed 2D region).
- Returns:
The profile; its loops are closed PolylineCurves.
-
void translate(glm::dvec2 translation)#
Translates the polygon and its holes by a vector.
- Parameters:
translation – The offset to add to every point.
Public Static Functions
-
static std::pair<std::vector<Polygon2>, std::vector<Polyline2>> Clip(const std::vector<Polygon2> &polygons, const std::vector<Polyline2> &polylines)#
Clips polylines to the region covered by a set of polygons.
The polylines are clipped as open paths against the polygons and their holes (even-odd fill), keeping the parts inside the region. Only open paths are clipped, so the closed result is always empty.
- Parameters:
polygons – The clipping polygons.
polylines – The polylines to clip.
- Throws:
std::runtime_error – If Clipper2 fails.
- Returns:
A pair of (closed polygons, clipped polylines). The first element is always empty.
-
static std::vector<Polygon2> Difference(const std::vector<Polygon2> &polygons, const std::vector<Polygon2> &others)#
Difference of two sets of polygons:
polygonsminusothers.Fill rule and output format as in Union().
- Parameters:
polygons – Base set of polygons.
others – Polygons to subtract.
- Returns:
The result contours.
-
static std::vector<Polygon2> Intersection(const std::vector<Polygon2> &polygons, const std::vector<Polygon2> &others)#
Intersection of two sets of polygons.
Fill rule and output format as in Union().
- Parameters:
polygons – The first set of polygons.
others – The second set of polygons.
- Returns:
The result contours.
-
static std::vector<Polygon2> Offset(const std::vector<Polygon2> &polygons, double distance)#
Offsets a set of polygons, with their holes, by one distance.
Outer boundaries are made counter-clockwise and holes clockwise, then offset with Clipper2 using miter joins (Clipper2’s default miter limit of 2), so convex corners stay sharp rather than rounded. Coordinates are snapped to a 1e-6 integer grid (INT_POINT_MULTIPLIER) for the offset. Each counter-clockwise result is returned as an outer polygon; each clockwise result is attached as a hole to the first outer polygon that contains its first point.
- Parameters:
polygons – The polygons to offset.
distance – Positive grows the regions, negative shrinks them.
- Returns:
The offset outer polygons with their holes attached.
-
static std::vector<Polygon2> Union(const std::vector<Polygon2> &polygons, const std::vector<Polygon2> &others)#
Union of two sets of polygons.
Uses Clipper2 with the even-odd fill rule and 6 decimal places of precision. Each set (with its holes) is filled even-odd, so polygons that overlap inside one set cancel (XOR) before the union. Each output contour becomes its own Polygon2: outer contours are counter-clockwise and holes are separate clockwise polygons (holes() is empty on all of them).
- Parameters:
polygons – The first set of polygons.
others – The second set of polygons.
- Returns:
The result contours.
-
void add_hole(const Polygon2 &hole)#
-
class Polyline2 : public PolylineCurve#
- #include <polyline2.h>
A class for storing and manipulating polylines in the XY plane.
A polyline is a sequence of line segments, defined by a sequence of points.
Polyline2 is an open PolylineCurve at z = 0, so it answers every Curve query (point at t, closest point, arc length, frames) and can be used wherever a curve is accepted. It keeps its original interface in the exact CGAL types used by Polygon2 and Arrangement2. Coordinates are stored in double precision. The in-place edits (reverse, prepend, append, simplify, translate) rebuild the curve; do not edit a Polyline2 while it is being evaluated elsewhere.
Note
Polyline2 used to derive from std::vector<Segment_2>; iterate segments() instead.
Public Functions
-
void append(const Polyline2 &polyline)#
Appends another polyline’s points to the end of this polyline.
A shared end point is kept once; otherwise a segment joins the two polylines.
- Parameters:
polyline – The polyline to append.
-
std::vector<Point_2> points() const#
Returns the points of the polyline.
- Returns:
The points of the polyline.
-
Polyline2(const std::vector<glm::dvec2> &points)#
Constructor.
Creates a Polyline2 object from a sequence of points with double precision.
Note
The polyline is always open. If the last point repeats the first, the result is an open curve that ends where it starts (Polygon2::to_polyline builds one this way); use Polygon2 for a region.
- Parameters:
points – The points defining the polyline as double precision.
- Pre:
There must be at least 2 points in the sequence.
-
Polyline2(const std::vector<glm::vec2> &points)#
Constructor.
Creates a Polyline2 object from a sequence of points with single precision.
Note
The polyline is always open. If the last point repeats the first, the result is an open curve that ends where it starts (Polygon2::to_polyline builds one this way); use Polygon2 for a region.
- Parameters:
points – The points defining the polyline as single precision.
- Pre:
There must be at least 2 points in the sequence.
-
Polyline2(const std::vector<Point_2> &points)#
Constructor.
Creates a Polyline2 object from a sequence of points.
Note
The polyline is always open. If the last point repeats the first, the result is an open curve that ends where it starts (Polygon2::to_polyline builds one this way); use Polygon2 for a region.
- Parameters:
points – The points defining the polyline.
- Pre:
There must be at least 2 points in the sequence.
-
void prepend(const Polyline2 &polyline)#
Prepends another polyline’s points to the start of this polyline.
A shared end point is kept once; otherwise a segment joins the two polylines.
- 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)#
Removes nearly collinear interior points from the polyline.
Walks the interior points in order and drops a point when the triangle it forms with the previous kept point and the next point has an area below
tolerance. The end points are always kept. Polylines with fewer than 3 points are left unchanged.- Parameters:
tolerance – The triangle-area threshold, in squared length units (not a distance).
-
void translate(const Point_2 &translation)#
Translates all points in the polyline by a given vector.
- Parameters:
translation – The vector to translate by.
-
inline virtual std::string type_name() const override#
Returns the curve type name, such as “BSplineCurve”.
- Returns:
The type name.
-
void append(const Polyline2 &polyline)#
-
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
- 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
- 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 std::shared_ptr<Profile> ComputeStitchedProfile(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)#
Traces the closed iso-lines of a 2D scalar field slice into a Profile.
The closed contours become the profile’s loops; nested contours become holes. Open contours, which reach the edge of the grid, are dropped, so pad the grid around the shape. The arguments are those of ComputeStitchedIsoLinesGeometry.
- Parameters:
evaluator – The scalar field, evaluated at (x, y, z).
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 trace.
epsilon – The epsilon value to use when comparing floating point numbers.
- Returns:
The region of the slice where the field is below iso_value.
-
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 ComputeIsoLinesGeometry() or ComputeIsoLinesDistribution() 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. Components whose two ends are adjacent are closed into counter-clockwise polygons; the rest become open polylines.
- 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.
epsilon – When the two values differ by less than this, p1 is returned.
- Returns:
The interpolated point.
-
typedef std::pair<std::vector<Polygon2>, std::vector<Polyline2>> CrossSection#