Index: developer/polybool2/algo.txt
===================================================================
--- developer/polybool2/algo.txt	(nonexistent)
+++ developer/polybool2/algo.txt	(revision 36884)
@@ -0,0 +1,91 @@
+Binary boolean operation between multi-island polygons A and B specified by contour
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+Def: input polygons are A and B for binary ops and A for unary ops
+Def: canon: an unary operator on a single input polygon that resolves the
+     self intersections and irregularities of that polygon
+Def: segment is a line or an arc
+Def: curve is an ordered list of segments with no intersection
+Def: region: a closed loop of curves (represented by an ordered list of
+     curve IDs)
+Def: clean region: a region that has no curve crossing its perimeter curves
+Def: output tree [of regions]: a tree of regions; each node is a region with
+     child nodes that are smaller regions fully within
+
+1. switch to topology
+	1.1. compute intersections of any two segments (using both A and B)
+	1.2. split segments at intersections; mark the new vertex introduced
+	     at the intersection as "intersected"
+	1.3. collect segments into curves between intersections
+	1.4. remove curves that are in full overlap with one another
+
+2. split: list clean regions:
+	2.1. map all possible regions
+	2.2. for each region starting frome ach intersection (curve-endpoint)
+	     check each curve that's not part of the region permiter; if that
+	     curve goes into the region, discard the region (as it is non-clean)
+	2.3. for curves of clean regions, each curve should have a list of
+	     regions that use the curve (this is at most two regions per curve)
+
+3. mark input polarity: for each clean region
+	3.1. choose an internal point of the region
+	3.2. region->inA := 1 or 0 depending on if the point is inside input polygon A
+	3.3. region->inB := 1 or 0 depending on if the point is inisde input polygon B
+
+4. compute polarity of regions: for each clean region compute region->out from
+   region->inA and region->inB, depending on the operator, as:
+		- A union B:     out = inA or inB
+		- A sub B:       out = inA and not inB
+		- A intersect B: out = inA and inB
+		- A xor B:       out = inA xor inB
+		- canon A:       out = inA
+
+5. figure which curves to keep: for each curve:
+	- if the curve has two adjacent regions, keep the curve the ->out of those
+	  two regions are not equal
+	- if the curve has only one adjacent region, keep the curve if the
+	  region's ->out is 1
+	Discarded curves are removed and freed.
+
+6. gather curves into output regions:
+	6.1. take a the leftmost/topmost curve and put it on an output curve list
+	     list, and mark the curve visited
+	6.2. check the adjacent curves on the other endpoint:
+		- if any of the curves is already marked visited, we have a closed region;
+		  convert the output curve list into an output region, clear the output region
+		  and start over at 6.1.
+		- ignore any curves that are already marked visited
+		- pick one of the remaining curves, append it to the outpt curve list
+		  and jump back to 6.2
+
+	The result is an unordered "list of output regions".
+
+7. stack output regions, building the output tree of regions:
+	7.0. create an output tree with the root node being an infinitely large
+	     negative region
+	7.1. take the largest remaining output region "off the list of output regions"
+	7.2. iterate over the existing tree to see whether the output region is
+	     within any of the leaves
+		- if yes: insert the output region as a child region of that leaf region,
+		  with polarity being the inverse of the leaf region
+		- if not: the output region is a new root in the output tree with
+		  positive polarity
+	7.3. go back to 7.1. if "list of output regions" is not empty
+
+	The result is the output tree.
+
+	(This is to figure the polarity of each output region)
+
+8. flatten the tree:
+	Iterate over each region in the output tree; for positive regions create
+	a polygon island; for negative regions create a polygon hole within the
+	island previously created for the parent region.
+
+9. cleanup
+	9.1. optional: visit each output contour and look at each interesected 
+	     vertex; if the two segments on the two sides can be converted into
+	     a single segment (e.g. coaxial lines or arcs on the same circle), merge
+	     them to reduce the number of vertices
+	9.2. discard and free the output tree (created in 7.)
+	9.3. discard and free the list of output region (created in 6., should be empty by now)
+	9.4. free all curves and regions used