index

Extract Result for Operation

remove not needed
extract the resulting graphs for a given operation.
convert the result graphs back to polygons.

Extracting the result of a given boolean operation from the total graph, in principle means, find a suitable link marked for the operation given and follow links connected to this one that are also marked for the operation. When we arrive at the starting link again, we extracted one polygon. Repeat this until all polygons for a certain operation are extracted. This will result into two types of polygons. The first type is a polygon describing the outercountour of an area. The second type describes an innercontour of an area. The first type can contain many of the second type. The second type will always be surounded by a polygon of the first type. The innercontours can be seen as holes in the outercontour. It is possible to describe the complete area with one polygon, by linking the holes into the outercontour, using two extra segment for each hole.

Inner and Outercontours linked into one polygon

All this is done in 5 steps:

Remove not needed links
Extract Simples - extract all inner and outer contours from the total graph and put them in a list of graphs. Mark innercontours as being a hole.
MakeOneGraph - Merge all contour graphs back into one graph (needed for scanbeam to link holes).
LinkHoles - Use a scanbeam to link the innercontour graphs into the outercontours.
Extract Simples - Extract the linked graphs (outer + inner contour as one graph) from the total graph.
Convert graph back to polygons

remove not needed links

Remove links that are not set for this operation.

Extract Simples

The first extract simples, searches in the total graph for a MostTopLeftNode. This is the beginnode of a link that belongs to a given operation, and is the mostleft and highest node of all the unmarked links. The extraction of a contour starts at this node. All the links we pass are marked, at the same time a new graph describing the followed contour is generated. When we arrive at the start node again, the contour is complete. We put the generated graph into a list. Repeat extracting contours until no unmarked links are available.

At the start node we take a link coming from this node that is not vertical. This link will be used to find out if we are dealing with an inner or outer contour. If it is an innercontour this link will be marked as a tophole link, this will later be used to link the innercontour into the outercontour.

If we are on an outercontour we will follow it clockwise else counterclockwise, this is more convenient during the linking process of the holes. When more then one link on a node belongs to the given operation, we always choose the most left link to continue. The effect is that many enclosed areas will be gathered into one polygon/graph.

take mostright in Collecting a graph.

MakeOneGraph

For linking the holes into the outer contour, a scanbeam algorithm is used again. This is why we once more merge all the graphs into one big graph. The seperate graphs can still be recognized by the unique number given to the links of each graph.

LinkHoles

During the extraction of the contours, for all innercontours the most topleft link was marked as a tophole link. This tophole link will now be used to link the hole to the contour just above this link. This contour can be another hole or the outercontour. A scanbeam is used to find the clossest contour to a hole. All the links marked as tophole that are inside a beam will be linked to the link in the beam that is just above the tophole link. The highest node in the toplink will be used to create the link. As long as this highest node of the toplink is not part of the current beam, the linking will be postponed to a next beam.

The linking to the topnode of the toplink is not done directly. In the link just above the tophole link we add the topnode to the "linecrosslist" of that link. This list was used for calculating intersections before, but is know empty again. More then one hole can be linked to the same link, all the topnode of the seperate toplinks are gathered in the linecrosslist. After scanning of the hole graph, the links will be scanned to see if a link contains a non empty linecrosslist. If this is the case all the topnodes in this linecrosslist will be linked into the link.

linking topnodes of holes.

The link with the linecrosslist is split into link a and link b. Two new links are created (link c and link d), and the topnode is split into two nodes. The links (c,d) to connect the topnode to the closest link will always be vertical. In the end the hole will be part of the contour just above the hole, no matter if this was a hole are an outercontour.