Boolean operations on 2D polygons — union, intersection, difference, and XOR — are crucial for applications in computer graphics, CAD, and GIS. These operations allow us to manipulate complex shapes, but the challenge is implementing them efficiently while maintaining stability and accuracy.
Choosing the Right Arithmetic
Selecting the right arithmetic is key to balancing performance and precision in geometry algorithms. After considering the pros and cons of floating-point and fixed-point arithmetic, I opted for i32
for point coordinates. Here's why:
Fixed-Point (i32) Pros:
- No rounding errors, ensuring consistent and exact values.
- Simplifies comparisons like determining if a point lies on a line or if two lines are parallel.
- Results are deterministic across platforms, making debugging easier.
i32
strikes a balance between memory efficiency and precision, while still allowing dot and cross products to fit comfortably into i64
, avoiding overflow concerns.
Problem Statement
Imagine we have two bodies: A (red) and B (blue). Each body is defined by a group of contours - a list of successively connected vertices. These contours are always closed and can allow self-intersections.
Our goal is to compute a new body C (green), which represents one of the following Boolean combinations:
- Union: C = A ∪ B
- Intersection: C = A ∩ B
- Exclusion: C = A ⊕ B
- Difference: C = A - B or B - A
Overlay Graph
Let's start by manipulating bodies A and B to create an overlay graph that will allow us to perform Boolean operations.
The steps to construct this graph are as follows:
Split segments:
Break down all the segments of both bodies A and B so that there are no self-intersections. This ensures each contour is composed of non-intersecting segments.Tag segments with metadata:
For each segment, store additional information indicating whether it belongs to body A, body B, or both, and record which side of the segment is part of the body.Combine everything into a graph structure:
This graph consists of nodes and links. Each node represents a point (an intersection or endpoint), and each link represents a segment between two points, along with metadata about which body the segment belongs to.
struct OverlayGraph {
nodes: Vec<Node>, // A list of nodes (points) in the graph
links: Vec<Link> // A list of links (edges) connecting the nodes
}
struct Node {
indices: Vec<usize> // Indices pointing to links connected to this node
}
struct Link {
a: IdPoint // The start point of the segment
b: IdPoint // The end point of the segment
fill: SegmentFill // Metadata about which sides belong to body A or B
}
type SegmentFill = u8;
In this structure:
- Nodes represent the points of intersection or the endpoints of segments.
- Links represent the segments themselves, connecting two nodes and carrying information about whether they belong to A, B, or both.
By organizing the segments and their metadata into an overlay graph, we can now efficiently extract contours based on Boolean filters (union, intersection, difference, etc.).
You can explore this concept with an example in the online editor.
Boolean Filter
Now that we've constructed the overlay graph, let's see how different Boolean operations are applied to bodies A and B. We will extract the resulting body C for each operation based on segment properties within the overlay graph.
Difference, C = A - B
- The resulting segments of C must not be inside body B and must belong to body A on one side.
- The side associated solely with body A will represent the inner part of the resulting shape.
Difference, C = B - A
- The resulting segments of C must not be inside body A and must belong to body B on one side.
- The side associated solely with body B will represent the inner part of the resulting shape.
Union, C = A or B
- The resulting segments of C must belong to either body A or body B, or to both.
- The opposite side of each segment must not belong to anybody.
- The side associated with one of the bodies will represent the inner part of the resulting shape.
Intersection, C = A and B
- The resulting segments of C must belong to both bodies A and B.
- The opposite side of each segment must not belong to both bodies simultaneously.
- The side associated with both bodies A and B will represent the inner part of the resulting shape.
Exclusion, C = A xor B
- The resulting segments of C must belong to either body A or body B, but not to both simultaneously.
- The opposite side of each segment must either belong to both bodies or to neither.
- The side associated with one of the bodies (A or B) will represent the inner part of the resulting shape.
Extract Shapes
Once we apply the desired Boolean filter to the Overlay Graph, we can begin extracting contours for the resulting shape.
Building a Contour
The algorithm follows a systematic process to build both outer and inner contours from the graph:
Start with the leftmost node:
The algorithm begins by selecting the leftmost node in the graph. From there, it looks for the topmost segment connected to this node.Traverse along segments:
The algorithm proceeds by traversing the selected segment to the next node. At each node, the next segment is selected by rotating around the current node in a counterclockwise direction, choosing the nearest segment that hasn't been visited yet.Mark segments as visited:
To prevent revisiting segments, each one is marked as visited when traversed.Complete the contour:
This process continues until a full loop is formed, completing the contour. Depending on the orientation of the segments, the contour will be classified as either outer or inner.
Define Contour
A shape is defined as a group of contours, with the first contour always being an outer contour. Any subsequent contours within the shape are classified as inner contours.
To define a contour, the algorithm begins by identifying the leftmost and topmost segment in the contour. The classification of the contour is determined as follows:
- If the left-top side of the segment is classified as the outer side, then the contour is an outer contour.
- If the left-top side of the segment is classified as the inner side, then the contour is an inner contour.
This method ensures each contour is correctly classified based on its orientation in 2D space.
Define Shape
A shape is defined as a group of contours, where the first contour is always an outer contour, and the subsequent contours (if any) are inner contours.
Matching Contours
To match inner contours to their corresponding outer contour, the following approach is used:
- A line is drawn from any point on the inner contour.
- The algorithm traces downward, and the first segment encountered from an outer contour beneath this point belongs to the outer contour that contains the inner contour.
Define Segment under Point
To determine whether a segment AB is below a point P, one may be tempted to compute the value of ym at the point of intersection M, where a vertical line is dropped from P onto AB (i.e., xp = xm):
However, this method can introduce precision issues due to the division operation involved.
A more reliable method involves using the order of traversal around the vertices of the triangle APB. If segment AB is below point P, the vertices A, P, and B will appear in a clockwise order.
This method uses the cross product of vectors PA and PB:
Since this method avoids division, it eliminates precision issues, making it stable for determining whether a segment is below a point.
Selecting the Closest Segment under Point
When multiple segments are positioned below point P, the next challenge is to identify which segment is closest to point P. This scenario can be categorized into three cases based on the relative configuration of the segments:
- Left Case
When both segments share a common left vertex A, we compare the positions of their right endpoints. If the vertices B0, B1, and A form a clockwise pattern, then AB0 is closer to P than AB1.
- Right Case
When both segments share a common right vertex B, we check the positions of their left endpoints. If the vertices A0, A1, and B form a clockwise pattern, then A1B is closer to P than A0B.
- Middle Case
In this case, one of the vertices (e.g., A1 or B0) lies inside the opposite segment. We use the point-segment comparison method to determine which of the segments is closer to P.
Final Solution
The final result of polygon Boolean operations is typically grouped by outer contours. One outer contour may contain several holes, and it is essential to match these correctly. In many cases, the direction of the vertices in outer and inner contours is opposite: the outer contour is listed in a clockwise direction, while the inner contours (holes) are listed counterclockwise.
This opposite orientation is especially useful in polygon processing algorithms like triangulation or bottleneck detection, as it simplifies the logic by removing the need to distinguish between segments belonging to outer or inner contours.
What Was Left Behind
Some important aspects were only briefly mentioned:
- Constructing an Overlay Graph: The process of reliably building the graph, handling intersections, and splitting segments is complex and deserves a deeper dive in a separate article.
- Graph Convergence: Ensuring the overlay graph converges correctly requires careful data handling to avoid errors during Boolean operations.
- Filling Rules (EvenOdd/NonZero): The filling rule can significantly affect the outcome of polygon operations, especially in complex or overlapping shapes.
Implementing in iOverlay
These concepts are fully implemented in iOverlay, a library designed for efficient 2D polygon Boolean operations. iOverlay delivers stable, deterministic results and is available under the MIT license across multiple platforms:
Top comments (0)