Boolean operations on two-dimensional bodies
As a child, I was always fascinated by games with dynamic landscapes: The Castle and Worms Armageddon. At that time, I did not understand how this amazing mechanics of destruction and world change was implemented. Later I learned that the secret was in the use of raster graphics, but I was interested in how to implement the same thing without resorting to raster. In this article, I want to talk about one of such vector solutions.
Statement of the problem
So, imagine that we have 2 bodies: A (red) and B (blue). We define such a body by a group of contours. A contour is a list of successively connected vertices, always closed and allowing self-intersections.
Our goal is to get a new body C(green), which is one of the following combinations:
Unification C = A or B
Intersection C = A and B
Exception C = A xor B
Difference C = A – B or B – A
Overlay graph
Let's do the following manipulation with A And B.
Let's split all the segments so that there are no self-intersections left.
For each segment, we add information about whether it belongs to the body. A or Band if it does, then from which side.
This structure is called an overlay graph and allows extracting contours based on Boolean filters. Those who want to understand it better can play with this example in the online editor Here.
Now let's look at how to extract contours using a simple example.
Difference A – B
As can be seen from the figure, the segments C cannot be located inside the body B and must belong to the body on one side A. Moreover, we can always determine where the segments are C the inner part, and where is the outer.
Combination A or B
Here are the segments C cannot be located inside the body A or B and must belong on one side either A or B either at once and A And B.
Intersection of A and B
Segment C cannot be inside both bodies at the same time, but must belong to one side and AAnd B.
Contour construction
After filtering the segments, the next step is to build the body contours. C. Let's consider this using the example of the difference A – B.
We will traverse the graph only along segments/edges of the body. WITH
Let's start the traversal from the leftmost vertex and select the topmost edge. Then we'll move from edge to vertex and to the next edge so that the inner part of the body WITH always remained on one side of the movement. Sooner or later we will return to the beginning, having completed the construction of the first contour.
After that, we move on to finding the next contour. The algorithm is the same: we start from the leftmost vertex. The process continues until there are unvisited edges.
As a result, we can get several closed contours. Some of them describe the outer perimeter, and some – the inner (holes).
The first segment from which the contour began can always determine the type of perimeter: external or internal. If the cavity is on top, it is an external perimeter, otherwise it is internal (a hole).
Matching the holes
Now we need to match each hole with its outer contour. To do this, we can use the leftmost corner of the hole and find the closest segment below it. The contour of this segment will be the outer contour for this hole.
Defining a segment under a point
Initially it may seem that in order to determine whether a segment is A.B. under the point Pit is enough to drop the perpendicular from P on A.B. and by the position of the intersection point M judge about it. However, due to the division operation, this method can give errors. Therefore, a more reliable method is to use the order of traversing the vertices of the triangle APB. If the segment A.B. is located under the point Pthen the vertices A, P And B will go counterclockwise.
This method is related to the vector product of vectors PA And PBwhich is calculated using the formula:
Since there is no division operation involved, the method is not subject to accuracy problems, making it absolutely stable.
We have determined that the segment is below the point, but how do we know if it is the closest? For this, we need another method that determines if one segment is above another.
Comparison of segments by height
This case breaks down into 3:
The left end matches
In this case, both segments A.B.0 And A.B.1 have a common left vertex, and we check which one is located lower in relation to the point PTo do this, we construct a triangle with vertices A, B0 And B1. If the vertices go counterclockwise, the segment A.B.1 below A.B.0.
The right end matches
When both segments have a common right vertex Bsimilarly, we check the location of their left ends. If the vertices A0, A1 And B follow counterclockwise, segment A0B below A1B.
General case
Here you can use the method of comparing one of the vertices (for example, A1 or B0), which is located inside the opposite segment. By applying the rule of comparison of a point and a segment, we can accurately determine which segment is higher.
Final decision
Solutions are usually grouped by outer contours. One outer contour may contain several holes, and it is important to match them correctly. Often the direction of the vertices in the outer and inner contours is opposite: the outer contour is listed clockwise, and the inner contour is counterclockwise. This opposite direction is useful in polygon processing algorithms such as triangulation or bottleneck detection, as it simplifies the process by eliminating the need to think about whether a segment belongs to an outer or inner contour.
What's left behind the scenes
EvenOdd/NonZero Filling Rule: Depending on the filling rule selected, the result of the operation may differ significantly. This is an important nuance that must be taken into account in complex geometry.
Construction of the overlay graph: I've only briefly mentioned the overlay graph, but haven't covered how to build it. This process deserves a separate article.
Guarantee of graph convergence: To get the correct result, the overlay graph must always converge, but this requires a special approach to data processing and calculations to avoid errors and inaccuracies.
The problem of error and accuracy: Geometric calculations often encounter the problem of inaccuracy, especially when working with floating point numbers. One solution to this problem is to use integer (int) calculations instead of floating point (float) calculations.
Implementation: I have only revealed the idea of the algorithm, but I have not touched upon how it is implemented. What are its weak and strong points.
Advertising rights
If you find this topic interesting, I will be glad to offer you my implementation available in several languages:
