Nail Sharipov

Posted on Sep 24 • Edited on Nov 20 • Originally published at ishape-rust.github.io

2D Polygon Boolean Operations

#algorithms #computerscience #rust #programming

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.

Outer contours are extracted in a clockwise direction.
Inner contours are extracted in a counterclockwise direction.

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 contours:

Draw a line downward from any point on the inner (target) contour.
Identify the first segment encountered along the line that does not belong to the target contour.
If the segment belongs to an outer contour, that contour is the container for the target contour.
If the segment belongs to another inner contour, the container of that inner contour is also the container for the target 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 y_m at the point of intersection M, where a vertical line is dropped from P onto AB (i.e., x_p = x_m):

y_{m} = \frac{y_{a} - y_{b}}{x_{a} - x_{b}}\cdot(x_{m} - x_{a}) + y_{a}

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:

a \times b = a_x b_y - a_y b_x

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 B₀, B₁, and A form a clockwise pattern, then AB₀ is closer to P than AB₁.

Right Case

When both segments share a common right vertex B, we check the positions of their left endpoints. If the vertices A₀, A₁, and B form a clockwise pattern, then A₁B is closer to P than A₀B.

Middle Case

In this case, one of the vertices (e.g., A₁ or B₀) 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:

DEV Community