Calculate Intersections 

The general idea general

The following actions are performed to calculate all intersections:
  1. Merging nodes with other nodes. All nodes that are within MARGE distance are merged together into one node.
  2. Merge node to link. All links that are within MARGE distance to a node, are split in such a manner that the node becomes part of the link. Vertical links are ignored. For non vertical links, the distance from a link to a node is calculated only in vertical direction. If this distance is within MARGE, it is taken as an intersection.
  3. Rotate the drawing 90 degrees.
  4. And call Merge node to link again. This takes care of all nodes that were within MARGE to a link in horizontal direction.
  5. Rotate back (not really needed)
  6. Calculate Link to Link crossings. All links that are really crossing in between the nodes, are found here.
  7. Because in the previous steps links are split in pieces to contain the new nodes, this can introduce new nodes that are within MARGE distance to eachother so once more MergeNodes is preformed as the last step.

General

During this stage intersections between links are calculated and added as new nodes into the graph structure. In the end this will lead to a graph describing enclosed areas that do not overlap each other, in order to determine for each area the boolean end result.

The intersections are found using scanbeam algorithms ( See Scanbeams. ). Snapping nodes to lines and nodes to nodes is an integrated part of this. The whole procedure to calculate intersections looks to much complicated. But this is all due to the integrated snapping feature, which is essential to reach a stable algorithm that can be used for extremely complicated drawings. Snapping a node to a link is done by looking at the distance in vertical and horizontal direction, because this can be done quickly. The effect is that in reality we check if the node is within 1/sqrt(MARGE) distance to the link, this is acceptable. intersecting links steps. gives an example of the steps involved

intersecting links steps

During all the intersection stages, new crossings that are found, are directly inserted into the graph. Each link in the graph has a linecrosslist, this list contains pointers to the nodes that this link is intersecting with. Every new intersection point found is added to this list. This intersection point can be a begin or endnode of another link, or a new node, that is the intersection point for two links. In the last case the new node is added to both links that intersect.
The process crossings routine checks a link for new intersections found, and splits the link into new links with the new nodes in between.

The end result is a bigger graph, since links are added to it. All of this is happening during the process of scanning the graph with a scanbeam. At the moment a link is removed from the scanbeam (at the most to the left node of this link, which is the _low of the current scanbeam), the link is checked for interscetions.

If there are interscetion with this link, they are inserted into the graph directly, the new links generated because of this are inserted at the beginning of the graph (sorted list of links), so they will not effect the rest of the graph that is more to the right and still needs to be scanned.

Merge node to node

When nodes are within MARGE distance to eachother, they are merged into one node. For this the links are sorted on the X and Y of the beginnode. The bin flag in the link is used to tell if that beginnode is already processed. Using the sort information we can merge the beginnodes of coming links to the beginnode of the current link. Merging nodes can result in links that are reduced to zero lenght, they are removed at the end.

Since nodes are moved in position during a merge of two nodes, there is always a change that new intersections between links will occur. This is the case in general, snapping nodes to lines also may cause extra intersection somewhere else in the graph. This is why the snapping process is not integrated with the calculation of the intersections between links (Link to Link), and also that (Node to Link) is after (Node to Node). This sequence of steps minimizes the change of generating weird intersections.

The whole idea is to generate a graph inclusif all intersections, in order to form enclosed areas that do not and may not overlap. If because of bad calculation of intersections, those enclosed areas do overlap, the boolean result will be wrong or even fail.

Merge Node to Link

Nodes within MARGE distance to a link, are merged with the link. The link is broken in two pieces to contain the node. The algorithm uses a scanbeam ( See Scanbeams. ) to achive this, actually it is a scanline algorithm here because only the first scanline is used. Also the links of the previous scanbeam are not removed directly when moving to the next scanbeam. So while processing the first scanline, the links of the previous and the current scanbeam are both in the beam.

For each scanbeam all the records are checked, to see if the link of the record is within MARGE distance to the low node (only in vertical direction). Only the low node needs to be checked, since this is the only new node inserted in the new beam. If the link of a record has as the begin or end node the low itself it will be skipped. If a node is too close to a link, the node is put in the crosslist of the link (the crosslist is maintained as part of the each link). The nodes put into the crosslist will be processes if the link is removed from the beam, it will split the link into several links containing the nodes.
Checking for close links to the current low node is done at the moment new links are inserted in the beam or when old links are removed from the beam. Every node in the graph will be checked this way, since every beginnode of a link is the endnode of another link. This is because the input is a set of polygons, so looping.

Link Ysp within MARGE to low.

scanbeams for node to link


 

scanbeams for rotated graph

Link to Link crossings

Finding crossings between links, is also done using a scanbeam. This time both scanlines in the beam are used. First the records are sorted on the Ysp (crossing of link with first scanline) of the records, using mergesort. After this the records are sorted on Ysn (crossing of link with second scanline), using a cocktailsort.
Cocktail sort uses a swap function for each record that is not in the right order. It swaps the record with other records until it is at the right position. Each record swaped leads to an intersection of links. Calculating the intersection of the links is part of the swap function.

crossing links

Sorting on the first scanlines gives the following order of records: abcd
Sorting on the second scanline makes a cross b,c and b cross c to get the following order: cbad

The following cases can be optimized:

parallel links