Boolean principle using graphs

The boolean operation is performed on two sets of polygons, called group A and B. Each group describes areas on a 2D plane that belong to the group, using closed polygons. Those polygons may contain holes and can be selfintersecting/overlaping. The area that is represented by one polygon, is based on the filling method used, in the boolean algorithm the "winding method" is used. In Group A and Group B areas we see an example of 4 graphs. 2 in each group, the intersections are not yet calculated. After intersection of the graphs we get a surface divided in groupA and groupB areas. . Here the intersections have become nodes also. It is now possible to tell for each enclosed area formed by several links, wether it belongs to a certain group area or not. To get the result of a certain boolean operation, we just need to extract the right enclosed areas, and convert those areas back into polygons. For the boolean OR operation this would be all the areas tagged (A,B) (not A,B) (A, not B).This can be seen rom the Truth table for the OR operation.

###### Truth table for OR operation

A | B | A OR B
--- | --- | ---
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 1

The result can be seen in Result of OR operation. . Each blue area is a polygon. The advantage of this method is that the resulting polygons do not contain holes and are not selfintersecting. The disadvantage is that the result contains many polygons. This is why it is better to assemble as much as possible of the enclosed areas into one polygon. The result is shown in optimized result. . Only one polygon is used now to represent the complete result. In general this method leads to polygons that contain holes. Holes within a polygon are defined as empty areas that are within the outside boundary of the polygon. They can/are maintained as part of the polygon, by linking each hole into the outside boundary with two (extra) segments. Within the graph structure, outside boundaries and holes are available as separate graph structures, converting the graph structure back to polygons requires linking of the holes. A different polygon data structure that would maintain holes not directly as part of a polygon, could skip this step.

The two methods mentioned above are the the extreme cases, something in between could be used also. For instance avoiding holes still take as many polygons together as possible as in optimized result no holes. . It depends on the application which method is most suitable. For the moment only the second method is implemented.

## Group A and Group B areas

## surface divided in groupA and groupB areas

## Result of OR operation

## optimized result

##

## optimized result no holes

##