|Extract Result for Operation
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
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.
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.
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.
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.