Scanbeam approach

The scanbeam method is used several times in the boolean algorithm to calculate certain things. The idea is to scan the drawing with a vertical scanbeam. A scanbeam is defined as being the space between two sequential vertical scanlines. A scanline is generated for every node in the graph. First all the begin nodes of the links in the graph are sorted on minimum X coordinate (also on Y if X is equal). The beginnode of one link is always the endnode of another link, simply because all polygons are closed loops. So when generating a scanline for each beginnode of all links, we are sure to visit all the nodes.

When two sequential beginnodes have the same X coordinate, the resulting beam will be a flatbeam, the two scanlines are the same, else we will get a normal beam. The graph in scanbeams in a graph.. therefore results in 5 scanbeams. It contains one flatbeam (scanlines shown with a slope, but is in reality also vertical)

##### scanbeams in a graph.

A scanbeam is maintained as a C++ class that is a list of Record's.
Scanbeam is an inhereted class of a double linked list of void pointers, the static iterator only knows that the void pointers are really Record objects.
Each scanbeam is crossed by several links, those links are part of the scanbeam as follows. Each Record has a pointer to a Line, each such Line maintains a pointer to a Link in the graph. A scanbeam is always between two sequential nodes. The first is called the _low of the current scanbeam, the second is the _low for the next scanbeam. From now on i will refer to those nodes as the _low and _high, the _high node is not maintained as part of the scanbeam, but in the Graph object it is set and used to set the type of scanbeam (FLAT or NORMAL) that needs to handled next.
Because the graph is sorted, there can never be other nodes within a scanbeam. For a flatbeam the _low and _high node have the same X coordinate, the _low Y coordinate will always be higher then the _high Y coordinate. For normal beams this is not the case. While scanning the graph only one beam will be in memory, this scanbeam is updated to form the next scanbeam. Updating the links in a new scanbeam is easy:

- New links for the coming scan beam will always start or end at the _high node of the previous beam.
- Old links that are not part of the new beam will also always start or end at the _high node of the previous beam.

Notice that the _high node of the previous beam always will be the _low node of the next beam. As part of the Record object the intersection point of the links with the first scanline will be maintained. When moving to a new beam the intersection point for the new first scanline (old second scanline) will be updated.

###### Data members of object Scanbeam

Name | Type | decsription
--- | --- | ---
_low | Node* | A pointer to the node that forms the first scanline in the beam.
_type | BEAM_TYPE | Type of beam (NORMAL, FLAT)
_prevbeam | BEAM_TYPE | Type of the previous beam (NORMAL, FLAT)
static _BI | TDLI<record> | Iterator for Scanbeam itself

## Scanning a graph with scanbeams

Scanning the drawing (Graph) using a scanbeam object, is a standard loop the folowing is a copy from the code ( Scanning with a scanbeam. ).
Extra comment has been added, in order to understand this code without further knowledge.

##### Scanning with a scanbeam

`//the scantype parameter is used in the scanbeam class to perform specific tasks`
`//for the boolean operations`
`int Graph::ScanGraph2(SCANTYPE scantype)`
`{`
`//create an iterator to traverse the linklist of the graph`
`TDLI<Link> _LI=TDLI<Link>(_linklist);`
`int found=0;`
``

`//sort links on x and y value of the beginnode of each link`

`_LI.mergesort(linkXYsorter);`
``

`//bin flag is used in scanbeam so reset`

`_LI.foreach_mf(&Link::SetNotBeenHere);`
``

`//make a scanbeam instance`

`ScanBeam* scanbeam = new ScanBeam();`
``

`Node* _lowf; //the current _low node`

`Link* _highlink; //the link in the graph that has as beginnode the _high (_low for next scanbeam)`
`Link* _lowlink; //the link in the graph that has as beginnode the _lowf (_high of previous beam)`
`_LI.tohead(); //start with first link in the beam`
`_lowf = 0; //make it zero in order to skip the first if in the while loop`
``

`while (!_LI.hitroot())`

`{`
`//same node pointer as the previous node, we don't have to check this node again`
`if (_lowf == _LI.item()->GetBeginNode())`
`_LI++;`
`else`
`{ int i;`
``
`_lowlink=_LI.item();`
`_lowf=_lowlink->GetBeginNode();`
``

`//find a new high node, this should be a node not eqaul to _lowf`

`i=0;`
`do`
`{ _LI++;i++;}`
`while (!_LI.hitroot() && (_lowf == _LI.item()->GetBeginNode()));`
``

`//even the last _lowf node must be processed, no new links will be found`

`//only old links will be removed`
`if (_LI.hitroot())`
`{`
`_LI--;`
`_highlink=_LI.item();`
`_LI++;`
`}`
`else`
`_highlink=_LI.item();`
``

`//put _LI back at the _lowf`

`_LI << i;`
``
`//set the beam _low node and the type of the beam (FLAT or NORMAL)`
`scanbeam->Set(_lowlink->GetBeginNode(),_highlink->GetBeginNode());`
``

`//find new links for the new beam and remove the old links`

`//depending on the scantype parameter also other things will take place`
`if (scanbeam->Update(scantype,&_LI))`
`found++;`
``

`_LI++; //next link in the graph, sorted on beginnode so in fact the next _lowf`

`}`
`}`
``

``

`delete scanbeam;`
`return found;`
`}`

First the begin nodes of links in the graph are sorted on X and Y coordinate. Each unique beginnode will result in a scanline, so when some links share the same beginnode it will be skipped. This is the case at a crossing of several links. We set the low and high node for the beam and based on this if the scanbeam is of type FLAT or NORMAL. Now we can remove records that should not be part of the new beam (containing links to the _lowf node), and find new records for links to the _lowf node.

### Finding a new scanbeam .

Scanbeams are defined by there _low and _high node. Sorting the links on the X,Y coordinate of the beginnode, leads to scanlines through each beginnode. Because the drawing contains only polygons, each beginnode is the endnode of another link. So taking only beginnodes results in passing each node only once. After intersection of the graphs some links can share the same beginnode. A beginnode has only to be checked once for links in the new scanbeam. Because the graph is sorted on beginnodes, we can easely skip the next beginnode if it is equal to the previous.
The rest of the nodes, form flat beams and normal beams. Only the normal beams need to be processed. For the flat beams only new links will be inserted into the beam, and old links will be removed. To achive this, we search the high of the first coming normal beam.The low is now increased until it reaches the high node, in the mean time the new and old links in the beam are updated (skipping flatbeams. ).

#### skipping flatbeams

### Remove old and FindNew Links for beam.

New links for the coming beam are only to be found at the high node of the previous beam (low node of the new beam). Links to be removed are the links connected to the high node of the previous beam. Each Node has a list of links that are connected to the node. All links that have the bin flag set, where already used in a previous beams, the others all need to be put in the current beam as new records. Also the bin flag will be set at this moment for those links. Before inserting the new links in the beam, we better remove old links connected to the low node of the current beam, because they are the only ones connected to the new low node. In some cases the links to be removed are only marked for removal (_active flag of record object). So they can easily be removed later.

#### removing and inserting links in beam at low node.

##

## Record Object

The scanbeam is a list of Records, each record contains a pointer to a link in the graph. When the beam is up to date, all the records contain pointers to links that cross the the current scanbeam. Next to this, each record contains the Y value of the link its crossing with the first and the second scanline of the beam. Those crossings (Ysp,Ysn) are used in several ways, for instance to sort the records in a beam.
The Link has a direction flag (_dir) in the beam record. For a link in a normal beam, if the direction from begin to endnode is from left to right, the _dir flag is set to GO_RIGHT else to GO_LEFT. For a flat beam, a vertical link is said to GO_RIGHT if it points downwards else GO_LEFT. The _dir flag is used for calculating Left Right Group values for each link in the graph.

###### Datamembers of object Record

Naam | Type | Omschrijving
--- | --- | ---
_line | Line | Line object for calculating the intersection of two links in the beam.
_ysp | PointType | Y-value of the intersection point of the link with the first scanline (low node).
_dir | DIRECTION | Direction of the link (GO_RIGHT or GO_LEFT ).
_inc | G_BOOL | Used for calculating the left right values for links in the graph.

The most important functions or the record object will be discussed:

The constructor.

Record(Link *link)

Calculating Left and Right values for a Record/Link:
Calc_Set_Left_Right,
Calc_Left_Right.

Calculating _ysn value:
Calc_Ysn.

Setting direction:

Set_Flags.

### Constructor

Record::Record(Link* link)
The Record will be constructed for a given link. The Ysn and Ysp will be set later on, depending on the beam it's low and high nodes. The same Record can be part of several sequential beams, the Ysp,Ysn will be updated when moving to the following beam. If the link of the record is not part of the beam anymore, the record will be destroyed.

The constructor also creates a line object for the given link, it is used to calculate Ysn,Ysp and intersections with other links.

### Calc_Set_Left_Right

void Record::Calc_Left_Right(int& a,int &b)
This function calculates the Group Left and right values of the link, based on the Group Left Right values of the previous record/link in the beam. The principle behind this will be discussed in See Basic Steps for Boolean Operations. .

##### Calculating Group Left Right values.

### Calc_Left_Right

Used only when group Left and Right flags where already calculated before. This is for speed.

### Calc_Ysn

void Record::calc_Ysn(BEAM_TYPE thisbeam,Node* high)
This function calculates the intersection point of the link with the second scanline (at high node). Calculation is optimized. For instance if the link begins or ends at the high node, it is clear the intersection is the Y coordinate ot the high node. For Flat beams the intersection point is equal to the intersection point of the first scanline, which is already known. Except for vertical links in a Flatbeam. ( See calculating Ysn value.. )

##### calculating Ysn value.

### Set_Flags

void Record::Set_Flags(BEAM_TYPE type)
This function calculates the direction flag (_dir) for the link in the record, based on the Beamtype (FLAT or NORMAL). How this is done for Flatbeams (containing vertical links) is shown in Direction of links in a flatbeam. .

##### Direction of links in a flatbeam