Commits

Anonymous committed 5ac4453

Many bug fixes and a couple of enhancements to deal with self-intersecting graphs. This work was funded by the fine folks at Mapdiva (http://www.mapdiva.com/), makers of Artboard.

  • Participants
  • Parent commits 93d82e4

Comments (0)

Files changed (20)

File VectorBoolean.xcodeproj/project.pbxproj

 	objects = {
 
 /* Begin PBXBuildFile section */
+		A106B9711737496A00697FF3 /* FBBezierIntersectRange.m in Sources */ = {isa = PBXBuildFile; fileRef = A106B96E1737496A00697FF3 /* FBBezierIntersectRange.m */; };
+		A106B9721737496A00697FF3 /* FBContourOverlap.m in Sources */ = {isa = PBXBuildFile; fileRef = A106B9701737496A00697FF3 /* FBContourOverlap.m */; };
 		A11131E513960B9D00C9395C /* NSBezierPath+Boolean.m in Sources */ = {isa = PBXBuildFile; fileRef = A11131E413960B9D00C9395C /* NSBezierPath+Boolean.m */; };
 		A192AB53139D843C00AF40BA /* FBBezierCurve.m in Sources */ = {isa = PBXBuildFile; fileRef = A192AB52139D843B00AF40BA /* FBBezierCurve.m */; };
 		A192AB56139D863A00AF40BA /* FBBezierIntersection.m in Sources */ = {isa = PBXBuildFile; fileRef = A192AB55139D863900AF40BA /* FBBezierIntersection.m */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXFileReference section */
+		A106B96D1737496A00697FF3 /* FBBezierIntersectRange.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBBezierIntersectRange.h; sourceTree = "<group>"; };
+		A106B96E1737496A00697FF3 /* FBBezierIntersectRange.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBBezierIntersectRange.m; sourceTree = "<group>"; };
+		A106B96F1737496A00697FF3 /* FBContourOverlap.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBContourOverlap.h; sourceTree = "<group>"; };
+		A106B9701737496A00697FF3 /* FBContourOverlap.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBContourOverlap.m; sourceTree = "<group>"; };
 		A11131E313960B9D00C9395C /* NSBezierPath+Boolean.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "NSBezierPath+Boolean.h"; sourceTree = "<group>"; };
 		A11131E413960B9D00C9395C /* NSBezierPath+Boolean.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "NSBezierPath+Boolean.m"; sourceTree = "<group>"; };
 		A192AB51139D843B00AF40BA /* FBBezierCurve.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBBezierCurve.h; sourceTree = "<group>"; };
 				A192AB52139D843B00AF40BA /* FBBezierCurve.m */,
 				A192AB54139D863900AF40BA /* FBBezierIntersection.h */,
 				A192AB55139D863900AF40BA /* FBBezierIntersection.m */,
+				A106B96D1737496A00697FF3 /* FBBezierIntersectRange.h */,
+				A106B96E1737496A00697FF3 /* FBBezierIntersectRange.m */,
+				A106B96F1737496A00697FF3 /* FBContourOverlap.h */,
+				A106B9701737496A00697FF3 /* FBContourOverlap.m */,
 				A1A3D0A513A9BCB800678AA9 /* FBBezierGraph.h */,
 				A1A3D0A613A9BCB900678AA9 /* FBBezierGraph.m */,
 				A1A3D0A913A9CE0E00678AA9 /* FBBezierContour.h */,
 				A1A3D0AE13A9CE3D00678AA9 /* FBContourEdge.m in Sources */,
 				A1A3D0B113A9CE5400678AA9 /* FBEdgeCrossing.m in Sources */,
 				A1A3D0B413AC0F3600678AA9 /* FBDebug.m in Sources */,
+				A106B9711737496A00697FF3 /* FBBezierIntersectRange.m in Sources */,
+				A106B9721737496A00697FF3 /* FBContourOverlap.m in Sources */,
 			);
 			runOnlyForDeploymentPostprocessing = 0;
 		};

File VectorBoolean/FBBezierContour.h

 
 @class FBBezierCurve;
 @class FBEdgeCrossing;
+@class FBContourEdge;
+@class FBContourOverlap;
 
 typedef enum FBContourInside {
     FBContourInsideFilled,
     FBContourInsideHole
 } FBContourInside;
 
+
+typedef enum FBContourDirection
+{
+	FBContourClockwise,
+	FBContourAntiClockwise
+}
+FBContourDirection;
+
 // FBBezierContour represents a closed path of bezier curves (aka edges). Contours
 //  can be filled or represent a hole in another contour.
 @interface FBBezierContour : NSObject<NSCopying> {
-    NSMutableArray *_edges;
-    NSRect _bounds;
+    NSMutableArray*	_edges;
+    NSRect			_bounds;
     FBContourInside _inside;
+    NSMutableArray  *_overlaps;
+	NSBezierPath*	_bezPathCache;	// GPC: added
 }
 
++ (id) bezierContourWithCurve:(FBBezierCurve *)curve;
+
 // Methods for building up the contour. The reverse forms flip points in the bezier curve before adding them
 //  to the contour. The crossing to crossing methods assuming the crossings are on the same edge. One of
 //  crossings can be nil, but not both.
 - (void) addReverseCurve:(FBBezierCurve *)curve;
 - (void) addReverseCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing;
 
+- (NSArray *) intersectionsWithRay:(FBContourEdge *)testEdge;
+- (NSUInteger) numberOfIntersectionsWithRay:(FBContourEdge *)testEdge;
 - (BOOL) containsPoint:(NSPoint)point;
 - (void) markCrossingsAsEntryOrExitWithContour:(FBBezierContour *)otherContour markInside:(BOOL)markInside;
 
-- (void) round;
+- (NSBezierPath*)		bezierPath;		// GPC: added
+- (void)				close;			// GPC: added
+
+- (FBBezierContour*)	reversedContour;	// GPC: added
+- (FBContourDirection)	direction;
+- (FBBezierContour*)	contourMadeClockwiseIfNecessary;
+
+- (void) addOverlap:(FBContourOverlap *)overlap;
+- (void) removeAllOverlaps;
+- (BOOL) isEquivalent:(FBBezierContour *)other;
 
 @property (readonly) NSArray *edges;
 @property (readonly) NSRect bounds;
 @property FBContourInside inside;
 @property (readonly) NSArray *intersectingContours;
 
+
+- (NSBezierPath*) debugPathForIntersectionType:(NSInteger) ti;
+
 @end

File VectorBoolean/FBBezierContour.m

 #import "FBBezierCurve.h"
 #import "FBContourEdge.h"
 #import "FBEdgeCrossing.h"
+#import "FBContourOverlap.h"
 #import "FBDebug.h"
+#import "Geometry.h"
 #import "FBBezierIntersection.h"
+#import "NSBezierPath+Utilities.h"
+
+@interface FBBezierContour ()
+
+- (FBContourEdge *) startEdge;
+- (BOOL) contourAndSelfIntersectingContoursContainPoint:(NSPoint)point;
+- (void) addSelfIntersectingContoursToArray:(NSMutableArray *)contours originalContour:(FBBezierContour *)originalContour;
+
+@property (readonly) NSArray *selfIntersectingContours;
+
+@end
 
 @implementation FBBezierContour
 
 @synthesize edges=_edges;
 @synthesize inside=_inside;
 
++ (id) bezierContourWithCurve:(FBBezierCurve *)curve
+{
+    FBBezierContour *contour = [[[FBBezierContour alloc] init] autorelease];
+    [contour addCurve:curve];
+    return contour;
+}
+
 - (id)init
 {
     self = [super init];
     if ( self != nil ) {
         _edges = [[NSMutableArray alloc] initWithCapacity:12];
+        _overlaps = [[NSMutableArray alloc] initWithCapacity:12];
     }
     
     return self;
 - (void)dealloc
 {
     [_edges release];
-    
+    [_overlaps release];
+    [_bezPathCache release];
     [super dealloc];
 }
 
     edge.index = [_edges count];
     [_edges addObject:edge];
     _bounds = NSZeroRect; // force the bounds to be recalculated
+	[_bezPathCache release];
+	_bezPathCache = nil;
 }
 
 - (void) addCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing
     //  on the next edge.
     if ( curve == nil )
         return;
-    FBBezierCurve *reverseCurve = [FBBezierCurve bezierCurveWithEndPoint1:curve.endPoint2 controlPoint1:curve.controlPoint2 controlPoint2:curve.controlPoint1 endPoint2:curve.endPoint1];
-    [self addCurve:reverseCurve];
+
+    [self addCurve:[curve reversedCurve]];
 }
 
 - (void) addReverseCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing
     if ( [_edges count] == 0 )
         return NSZeroRect;
     
-    // Start with the first point to set the topLeft and bottom right points
-    FBContourEdge *firstEdge = [_edges objectAtIndex:0];
-    NSPoint topLeft = firstEdge.curve.endPoint1;
-    NSPoint bottomRight = topLeft;
-    
-    // All the edges are connected, so only add on based on the second end point
+    NSRect totalBounds = NSZeroRect;    
     for (FBContourEdge *edge in _edges) {
-        NSPoint point = edge.curve.endPoint2;
-        if ( point.x < topLeft.x )
-            topLeft.x = point.x;
-        if ( point.x > bottomRight.x )
-            bottomRight.x = point.x;
-        if ( point.y < topLeft.y )
-            topLeft.y = point.y;
-        if ( point.y > bottomRight.y )
-            bottomRight.y = point.y;
+        NSRect bounds = edge.curve.bounds;
+        if ( NSEqualRects(totalBounds, NSZeroRect) )
+            totalBounds = bounds;
+        else
+            totalBounds = FBUnionRect(totalBounds, bounds);
     }
     
-    _bounds = NSMakeRect(topLeft.x, topLeft.y, bottomRight.x - topLeft.x, bottomRight.y - topLeft.y);
+    _bounds = totalBounds;
 
     return _bounds;
 }
 
 - (BOOL) containsPoint:(NSPoint)testPoint
 {
-    // Create a test line from our point to somewhere outside our graph. We'll see how many times the test
+	// Create a test line from our point to somewhere outside our graph. We'll see how many times the test
     //  line intersects edges of the graph. Based on the even/odd rule, if it's an odd number, we're inside
     //  the graph, if even, outside.
     NSPoint lineEndPoint = NSMakePoint(testPoint.x > NSMinX(self.bounds) ? NSMinX(self.bounds) - 10 : NSMaxX(self.bounds) + 10, testPoint.y); /* just move us outside the bounds of the graph */
     FBBezierCurve *testCurve = [FBBezierCurve bezierCurveWithLineStartPoint:testPoint endPoint:lineEndPoint];
+    FBBezierContour *testContour = [FBBezierContour bezierContourWithCurve:testCurve];
+    FBContourEdge *testEdge = [testContour.edges objectAtIndex:0];
     
-    NSUInteger intersectCount = 0;
+    NSUInteger intersectCount = [self numberOfIntersectionsWithRay:testEdge];
+    return (intersectCount & 1) == 1;
+}
+
+- (NSUInteger) numberOfIntersectionsWithRay:(FBContourEdge *)testEdge
+{
+    return [[self intersectionsWithRay:testEdge] count];
+}
+
+- (NSArray *) intersectionsWithRay:(FBContourEdge *)testEdge
+{
+    FBBezierCurve *testCurve = testEdge.curve;
+    NSMutableArray *allIntersections = [NSMutableArray array];
+    
+    // Count how many times we intersect with this particular contour
     for (FBContourEdge *edge in _edges) {
+        // Check for intersections between our test ray and the rest of the bezier graph
         NSArray *intersections = [testCurve intersectionsWithBezierCurve:edge.curve];
         for (FBBezierIntersection *intersection in intersections) {
-            if ( intersection.isTangent )
+            // Make sure this is a proper crossing
+            if ( ![testEdge crossesEdge:edge atIntersection:intersection] ) // don't count tangents
                 continue;
-            intersectCount++;
-        }
+            
+            // Make sure we don't count the same intersection twice. This happens when the ray crosses at
+            //  start or end of an edge.
+            if ( intersection.isAtStartOfCurve2 && [allIntersections count] > 0 ) {
+                FBBezierIntersection *previousIntersection = [allIntersections lastObject];
+                FBContourEdge *previousEdge = edge.previous;
+                if ( previousIntersection.isAtEndPointOfCurve2 && previousEdge.curve == previousIntersection.curve2 )
+                    continue;
+            } else if ( intersection.isAtEndPointOfCurve2 && [allIntersections count] > 0 ) {
+                FBBezierIntersection *nextIntersection = [allIntersections objectAtIndex:0];
+                FBContourEdge *nextEdge = edge.next;
+                if ( nextIntersection.isAtStartOfCurve2 && nextEdge.curve == nextIntersection.curve2 )
+                    continue;                
+            }
+            
+            [allIntersections addObject:intersection];
+        }            
     }
+    return allIntersections;
+}
+
+- (FBContourEdge *) startEdge
+{
+    // When marking we need to start at a point that is clearly either inside or outside
+    //  the other graph, otherwise we could mark the crossings exactly opposite of what
+    //  they're supposed to be.
+    if ( [self.edges count] == 0 )
+        return nil;
     
-    return (intersectCount % 2) == 1;
+    FBContourEdge *startEdge = [self.edges objectAtIndex:0];
+    FBContourEdge *stopValue = startEdge;
+    while ( startEdge.isStartShared ) {
+        startEdge = startEdge.next;
+        if ( startEdge == stopValue )
+            break; // for safety. But if we're here, we could be hosed
+    }
+    return startEdge;
 }
 
 - (void) markCrossingsAsEntryOrExitWithContour:(FBBezierContour *)otherContour markInside:(BOOL)markInside
     // When marking we need to start at a point that is clearly either inside or outside
     //  the other graph, otherwise we could mark the crossings exactly opposite of what
     //  they're supposed to be.
-    FBContourEdge *startEdge = [self.edges objectAtIndex:0];
-    FBContourEdge *stopValue = startEdge;
-    while ( startEdge.isStartShared ) {
-        startEdge = startEdge.next;
-        if ( startEdge == stopValue )
-            break; // for safety. But if we're here, we could be hosed
-    }
-    
+    FBContourEdge *startEdge = [self startEdge];
+    NSPoint startPoint = startEdge.curve.endPoint1;
+        
     // Calculate the first entry value. We need to determine if the edge we're starting
     //  on is inside or outside the otherContour.
-    BOOL contains = [otherContour containsPoint:startEdge.curve.endPoint1];
+    BOOL contains = [otherContour contourAndSelfIntersectingContoursContainPoint:startPoint];
     BOOL isEntry = markInside ? !contains : contains;
+    NSArray *otherContours = [otherContour.selfIntersectingContours arrayByAddingObject:otherContour];
     
     // Walk all the edges in this contour and mark the crossings
     FBContourEdge *edge = startEdge;
         // Mark all the crossings on this edge
         for (FBEdgeCrossing *crossing in edge.crossings) {
             // skip over other contours
-            if ( crossing.counterpart.edge.contour != otherContour )
+            if ( crossing.isSelfCrossing || ![otherContours containsObject:crossing.counterpart.edge.contour] )
                 continue;
             crossing.entry = isEntry;
             isEntry = !isEntry; // toggle.
     } while ( edge != startEdge );
 }
 
-- (void) round
+- (BOOL) contourAndSelfIntersectingContoursContainPoint:(NSPoint)point
 {
-    // Go through and round all the end points to integral value
-    for (FBContourEdge *edge in _edges)
-        [edge round];
+    NSUInteger containerCount = 0;
+    if ( [self containsPoint:point] )
+        containerCount++;
+    NSArray *intersectingContours = self.selfIntersectingContours;
+    for (FBBezierContour *contour in intersectingContours) {
+        if ( [contour containsPoint:point] )
+            containerCount++;
+    }
+    return (containerCount & 1) != 0;
 }
 
+- (NSBezierPath*) bezierPath		// GPC: added
+{
+	if ( _bezPathCache == nil ) {
+		NSBezierPath* path = [NSBezierPath bezierPath];
+		BOOL firstPoint = YES;        
+		
+		for ( FBContourEdge *edge in self.edges ) {
+			if ( firstPoint ) {
+				[path moveToPoint:edge.curve.endPoint1];
+				firstPoint = NO;
+			}
+			
+			if ( edge.curve.isStraightLine )
+				[path lineToPoint:edge.curve.endPoint2];
+			else
+				[path curveToPoint:edge.curve.endPoint2 controlPoint1:edge.curve.controlPoint1 controlPoint2:edge.curve.controlPoint2];
+		}
+		
+		[path closePath];
+		[path setWindingRule:NSEvenOddWindingRule];
+		_bezPathCache = [path retain];
+    }
+	
+    return _bezPathCache;
+}
+
+
+- (void) close
+{
+	// adds an element to connect first and last points on the contour
+	if ( [_edges count] == 0 )
+        return;
+    
+    FBContourEdge *first = [_edges objectAtIndex:0];
+    FBContourEdge *last = [_edges lastObject];
+    
+    if ( !FBArePointsClose(first.curve.endPoint1, last.curve.endPoint2) )
+        [self addCurve:[FBBezierCurve bezierCurveWithLineStartPoint:last.curve.endPoint2 endPoint:first.curve.endPoint1]];
+}
+
+
+- (FBBezierContour*) reversedContour	// GPC: added
+{
+	FBBezierContour *revContour = [[[self class] alloc] init];
+	
+	for ( FBContourEdge *edge in _edges )
+		[revContour addReverseCurve:edge.curve];
+	
+	return [revContour autorelease];
+}
+
+
+- (FBContourDirection) direction
+{
+	NSPoint lastPoint = NSZeroPoint, currentPoint = NSZeroPoint;
+	BOOL firstPoint = YES;
+	CGFloat	a = 0.0;
+	
+	for ( FBContourEdge* edge in _edges ) {
+		if ( firstPoint ) {
+			lastPoint = edge.curve.endPoint1;
+			firstPoint = NO;
+		} else {
+			currentPoint = edge.curve.endPoint2;
+			a += ((lastPoint.x * currentPoint.y) - (currentPoint.x * lastPoint.y));
+			lastPoint = currentPoint;
+		}
+	}
+
+	return ( a >= 0 ) ? FBContourClockwise : FBContourAntiClockwise;
+}
+
+
+- (FBBezierContour *) contourMadeClockwiseIfNecessary
+{
+	FBContourDirection dir = [self direction];
+	
+	if( dir == FBContourClockwise )
+		return self;
+	
+    return [self reversedContour];
+}
+
+
 - (NSArray *) intersectingContours
 {
     // Go and find all the unique contours that intersect this specific contour
     return contours;
 }
 
+- (NSArray *) selfIntersectingContours
+{
+    // Go and find all the unique contours that intersect this specific contour from our own graph
+    NSMutableArray *contours = [NSMutableArray arrayWithCapacity:3];
+    [self addSelfIntersectingContoursToArray:contours originalContour:self];
+    return contours;
+}
+
+- (void) addSelfIntersectingContoursToArray:(NSMutableArray *)contours originalContour:(FBBezierContour *)originalContour
+{
+    for (FBContourEdge *edge in _edges) {
+        NSArray *intersectingEdges = edge.selfIntersectingEdges;
+        for (FBContourEdge *intersectingEdge in intersectingEdges) {
+            if ( intersectingEdge.contour != originalContour && ![contours containsObject:intersectingEdge.contour] ) {
+                [contours addObject:intersectingEdge.contour];
+                [intersectingEdge.contour addSelfIntersectingContoursToArray:contours originalContour:originalContour];
+            }
+        }
+    }
+}
+
+- (void) addOverlap:(FBContourOverlap *)overlap
+{
+    [_overlaps addObject:overlap];
+}
+
+- (void) removeAllOverlaps
+{
+    [_overlaps removeAllObjects];
+}
+
+- (BOOL) isEquivalent:(FBBezierContour *)other
+{
+    for (FBContourOverlap *overlap in _overlaps) {
+        if ( [overlap isBetweenContour:self andContour:other] && [overlap isComplete] )
+            return YES;
+    }
+    return NO;
+}
+
 - (id)copyWithZone:(NSZone *)zone
 {
     FBBezierContour *copy = [[FBBezierContour allocWithZone:zone] init];
             FBArrayDescription(_edges)
             ];
 }
+
+
+
+- (NSBezierPath *) debugPathForIntersectionType:(NSInteger)itersectionType
+{
+	// returns a path consisting of small circles placed at the intersections that match <ti>
+	// this allows the internal state of a contour to be rapidly visualized so that bugs with
+	// boolean ops are easier to spot at a glance
+	
+	NSBezierPath *path = [NSBezierPath bezierPath];
+	
+	for ( FBContourEdge* edge in _edges ) {
+		for ( FBEdgeCrossing* crossing in [edge crossings] ) {
+			switch ( itersectionType ) {
+				default:	// match any
+					break;
+				
+				case 1:		// looking for entries
+					if ( !crossing.isEntry )
+						continue;
+					break;
+					
+				case 2:		// looking for exits
+					if ( crossing.isEntry )
+						continue;
+					break;
+			}
+			
+			// if the crossing is flagged as "entry", show a circle, otherwise a rectangle
+			[path appendBezierPath:crossing.isEntry? [NSBezierPath circleAtPoint:crossing.location] : [NSBezierPath rectAtPoint:crossing.location]];
+		}
+	}
+	
+    // Add the start point and direction for marking
+    FBContourEdge *startEdge = [self startEdge];
+    NSPoint startEdgeTangent = FBNormalizePoint(FBSubtractPoint(startEdge.curve.controlPoint1, startEdge.curve.endPoint1));
+    [path appendBezierPath:[NSBezierPath triangleAtPoint:startEdge.curve.endPoint1 direction:startEdgeTangent]];
+    
+	// add the contour's entire path to make it easy to see which one owns which crossings (these can be colour-coded when drawing the paths)
+	[path appendBezierPath:[self bezierPath]];
+	
+	// if this countour is flagged as "inside", the debug path is shown dashed, otherwise solid
+	if ( self.inside == FBContourInsideHole ) {
+        CGFloat dashes[] = { 2, 3 };
+		[path setLineDash:dashes count:2 phase:0];
+    }
+	
+	return path;
+}
+
 @end

File VectorBoolean/FBBezierCurve.h

 //
 
 #import <Cocoa/Cocoa.h>
+#import "Geometry.h"
 
-// FBRange is a range of parameter (t)
-typedef struct FBRange {
-    CGFloat minimum;
-    CGFloat maximum;
-} FBRange;
-
-extern FBRange FBRangeMake(CGFloat minimum, CGFloat maximum);
-extern BOOL FBRangeHasConverged(FBRange range, NSUInteger places);
-extern CGFloat FBRangeGetSize(FBRange range);
-extern CGFloat FBRangeAverage(FBRange range);
-extern CGFloat FBRangeScaleNormalizedValue(FBRange range, CGFloat value);
+@class FBBezierIntersectRange;
 
 // FBBezierCurve is one cubic 2D bezier curve. It represents one segment of a bezier path, and is where
 //  the intersection calculation happens
     NSPoint _controlPoint1;
     NSPoint _controlPoint2;
     NSPoint _endPoint2;
+	BOOL _isStraightLine;		// GPC: flag when curve came from a straight line segment
 }
 
 + (NSArray *) bezierCurvesFromBezierPath:(NSBezierPath *)path;
 @property NSPoint controlPoint1;
 @property NSPoint controlPoint2;
 @property NSPoint endPoint2;
+@property BOOL isStraightLine;
+@property (readonly) NSRect bounds;
 
 - (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve;
+- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve overlapRange:(FBBezierIntersectRange **)intersectRange;
 
 - (NSPoint) pointAtParameter:(CGFloat)parameter leftBezierCurve:(FBBezierCurve **)leftBezierCurve rightBezierCurve:(FBBezierCurve **)rightBezierCurve;
 - (FBBezierCurve *) subcurveWithRange:(FBRange)range;
+- (NSArray *) splitSubcurvesWithRange:(FBRange)range;
 
-- (void) round;
+- (CGFloat) lengthAtParameter:(CGFloat)parameter;
+- (CGFloat) length;
+
+- (FBBezierCurve *) reversedCurve;	// GPC: added
+
+- (NSBezierPath *) bezierPath;
 
 @end

File VectorBoolean/FBBezierCurve.m

 #import "NSBezierPath+Utilities.h"
 #import "Geometry.h"
 #import "FBBezierIntersection.h"
+#import "FBBezierIntersectRange.h"
 
 //////////////////////////////////////////////////////////////////////////////////
 // Normalized lines
 static FBNormalizedLine FBNormalizedLineMake(NSPoint point1, NSPoint point2)
 {
     FBNormalizedLine line = { point1.y - point2.y, point2.x - point1.x, point1.x * point2.y - point2.x * point1.y };
-    CGFloat distance = sqrtf(line.b * line.b + line.a * line.a);
-    line.a /= distance;
-    line.b /= distance;
-    line.c /= distance;
+    CGFloat distance = sqrt(line.b * line.b + line.a * line.a);
+	
+	// GPC: prevent divide-by-zero from putting NaNs into the values which cause trouble further on. I'm not sure
+	// what cases trigger this, but sometimes point1 == point2 so distance is 0.
+	if( distance != 0.0 ) {
+		line.a /= distance;
+		line.b /= distance;
+		line.c /= distance;
+	} else
+		line.a = line.b = line.c = 0;
+
     return line;
 }
 
     return line.a * point.x + line.b * point.y + line.c;
 }
 
-//////////////////////////////////////////////////////////////////////////////////
-// Parameter ranges
-//
-FBRange FBRangeMake(CGFloat minimum, CGFloat maximum)
-{
-    FBRange range = { minimum, maximum };
-    return range;
-}
-
-BOOL FBRangeHasConverged(FBRange range, NSUInteger places)
-{
-    CGFloat factor = powf(10.0, places);
-    NSInteger minimum = (NSInteger)(range.minimum * factor);
-    NSInteger maxiumum = (NSInteger)(range.maximum * factor);
-    return minimum == maxiumum;
-}
-
-CGFloat FBRangeGetSize(FBRange range)
-{
-    return range.maximum - range.minimum;
-}
-
-CGFloat FBRangeAverage(FBRange range)
-{
-    return (range.minimum + range.maximum) / 2.0;
-}
-
-CGFloat FBRangeScaleNormalizedValue(FBRange range, CGFloat value)
-{
-    return (range.maximum - range.minimum) * value + range.minimum;
-}
 
 //////////////////////////////////////////////////////////////////////////////////
 // Helper functions
 static BOOL LineIntersectsHorizontalLine(NSPoint startPoint, NSPoint endPoint, CGFloat y, NSPoint *intersectPoint)
 {
     // Do a quick test to see if y even falls on the startPoint,endPoint line
-    if ( y < MIN(startPoint.y, endPoint.y) || y > MAX(startPoint.y, endPoint.y) )
+    CGFloat minY = MIN(startPoint.y, endPoint.y);
+    CGFloat maxY = MAX(startPoint.y, endPoint.y);
+    if ( (y < minY && !FBAreValuesClose(y, minY)) || (y > maxY && !FBAreValuesClose(y, maxY)) )
         return NO;
     
     // There's an intersection here somewhere
     return points[0];
 }
 
+static NSArray *FBComputeCubicFirstDerivativeRoots(CGFloat a, CGFloat b, CGFloat c, CGFloat d)
+{
+    // See http://processingjs.nihongoresources.com/bezierinfo/#bounds for where the formulas come from
+    CGFloat denominator = -a + 3.0 * b - 3.0 * c + d;
+    if ( !FBAreValuesClose(denominator, 0.0) ) {
+        CGFloat numeratorLeft = -a + 2.0 * b - c;
+        CGFloat numeratorRight = -sqrt(-a * (c - d) + b * b - b * (c + d) + c * c);
+        CGFloat t1 = (numeratorLeft + numeratorRight) / denominator;
+        CGFloat t2 = (numeratorLeft - numeratorRight) / denominator;
+        return [NSArray arrayWithObjects:[NSNumber numberWithFloat:t1], [NSNumber numberWithFloat:t2], nil];
+    }
+    
+    // If denominator == 0, fall back to 
+    CGFloat t = (a - b) / (2.0 * (a - 2.0 * b + c));
+    return [NSArray arrayWithObject:[NSNumber numberWithFloat:t]];
+}
+
+// Legendre-Gauss abscissae (xi values, defined at i=n as the roots of the nth order Legendre polynomial Pn(x))
+static CGFloat FBLegendreGaussAbscissaeValues[][24] = {{},{},
+    {-0.5773502691896257310588680411456152796745,0.5773502691896257310588680411456152796745},
+    {0.0000000000000000000000000000000000000000,-0.7745966692414834042779148148838430643082,0.7745966692414834042779148148838430643082},
+    {-0.3399810435848562573113440521410666406155,0.3399810435848562573113440521410666406155,-0.8611363115940525725378051902225706726313,0.8611363115940525725378051902225706726313},
+    {0.0000000000000000000000000000000000000000,-0.5384693101056831077144693153968546539545,0.5384693101056831077144693153968546539545,-0.9061798459386639637003213465504813939333,0.9061798459386639637003213465504813939333},
+    {0.6612093864662644815410885712481103837490,-0.6612093864662644815410885712481103837490,-0.2386191860831969047129774708082550205290,0.2386191860831969047129774708082550205290,-0.9324695142031520500580654697841964662075,0.9324695142031520500580654697841964662075},
+    {0.0000000000000000000000000000000000000000,0.4058451513773971841558818596240598708391,-0.4058451513773971841558818596240598708391,-0.7415311855993944600839995473506860435009,0.7415311855993944600839995473506860435009,-0.9491079123427584862682238053821492940187,0.9491079123427584862682238053821492940187},
+    {-0.1834346424956498078362443493460887111723,0.1834346424956498078362443493460887111723,-0.5255324099163289908176466269651427865028,0.5255324099163289908176466269651427865028,-0.7966664774136267279658341067261062562466,0.7966664774136267279658341067261062562466,-0.9602898564975362871720676594122778624296,0.9602898564975362871720676594122778624296},
+    {0.0000000000000000000000000000000000000000,-0.8360311073266357695388251158874481916428,0.8360311073266357695388251158874481916428,-0.9681602395076260858530758923734538257122,0.9681602395076260858530758923734538257122,-0.3242534234038089158147499801998492330313,0.3242534234038089158147499801998492330313,-0.6133714327005903577116896485676988959312,0.6133714327005903577116896485676988959312},
+    {-0.1488743389816312157059030596428783610463,0.1488743389816312157059030596428783610463,-0.4333953941292472133994806426926515996456,0.4333953941292472133994806426926515996456,-0.6794095682990244355892173189204186201096,0.6794095682990244355892173189204186201096,-0.8650633666889845363456856830453034490347,0.8650633666889845363456856830453034490347,-0.9739065285171717434309357486199587583542,0.9739065285171717434309357486199587583542},
+    {0.0000000000000000000000000000000000000000,-0.2695431559523449593918087430211016908288,0.2695431559523449593918087430211016908288,-0.5190961292068118071441062966187018901110,0.5190961292068118071441062966187018901110,-0.7301520055740493564400139803183265030384,0.7301520055740493564400139803183265030384,-0.8870625997680953167545681026240345090628,0.8870625997680953167545681026240345090628,-0.9782286581460569729884468870295677334070,0.9782286581460569729884468870295677334070},
+    {-0.1252334085114689132822718420356977730989,0.1252334085114689132822718420356977730989,-0.3678314989981801841345543380157323554158,0.3678314989981801841345543380157323554158,-0.5873179542866174829285341729701030999422,0.5873179542866174829285341729701030999422,-0.7699026741943046925342741815256886184216,0.7699026741943046925342741815256886184216,-0.9041172563704749087776235683122649788857,0.9041172563704749087776235683122649788857,-0.9815606342467192435563561048184055835009,0.9815606342467192435563561048184055835009},
+    {0.0000000000000000000000000000000000000000,-0.2304583159551348015003924274424207396805,0.2304583159551348015003924274424207396805,-0.4484927510364468683512484403763664886355,0.4484927510364468683512484403763664886355,-0.6423493394403402279024817289609927684069,0.6423493394403402279024817289609927684069,-0.8015780907333098781464286730624735355377,0.8015780907333098781464286730624735355377,-0.9175983992229779229177211163914762437344,0.9175983992229779229177211163914762437344,-0.9841830547185881350458203087328001856804,0.9841830547185881350458203087328001856804},
+    {-0.1080549487073436676354276642086915671825,0.1080549487073436676354276642086915671825,-0.3191123689278897446186533670697826892138,0.3191123689278897446186533670697826892138,-0.5152486363581540995681962158414535224438,0.5152486363581540995681962158414535224438,-0.6872929048116854788830210054584313184023,0.6872929048116854788830210054584313184023,-0.8272013150697650196718768711434677243233,0.8272013150697650196718768711434677243233,-0.9284348836635735180422557277779560536146,0.9284348836635735180422557277779560536146,-0.9862838086968123141318187663273420184851,0.9862838086968123141318187663273420184851},
+    {0.0000000000000000000000000000000000000000,-0.2011940939974345143870237961891689337790,0.2011940939974345143870237961891689337790,-0.3941513470775633853904196257644798606634,0.3941513470775633853904196257644798606634,-0.5709721726085388304738899023504927754402,0.5709721726085388304738899023504927754402,-0.7244177313601700696210627938853576779366,0.7244177313601700696210627938853576779366,-0.8482065834104272061821916395274456590414,0.8482065834104272061821916395274456590414,-0.9372733924007059513883177714888006448746,0.9372733924007059513883177714888006448746,-0.9879925180204853774057482951320707798004,0.9879925180204853774057482951320707798004},
+    {-0.0950125098376374405129141109682677779347,0.0950125098376374405129141109682677779347,-0.2816035507792589154263396267197094857693,0.2816035507792589154263396267197094857693,-0.4580167776572273696800152720243204385042,0.4580167776572273696800152720243204385042,-0.6178762444026437705701937375124543905258,0.6178762444026437705701937375124543905258,-0.7554044083550029986540153004170861095190,0.7554044083550029986540153004170861095190,-0.8656312023878317551961458775622304528952,0.8656312023878317551961458775622304528952,-0.9445750230732326002680565579794347286224,0.9445750230732326002680565579794347286224,-0.9894009349916499385102497399202547967434,0.9894009349916499385102497399202547967434},
+    {0.0000000000000000000000000000000000000000,-0.1784841814958478545261044700964703224599,0.1784841814958478545261044700964703224599,-0.3512317634538763000406902392569463700056,0.3512317634538763000406902392569463700056,-0.5126905370864769384553483178024180233479,0.5126905370864769384553483178024180233479,-0.6576711592166907260903485621383879333735,0.6576711592166907260903485621383879333735,-0.7815140038968013680431567991035990417004,0.7815140038968013680431567991035990417004,-0.8802391537269859123071569229068700224161,0.8802391537269859123071569229068700224161,-0.9506755217687677950166857954172883182764,0.9506755217687677950166857954172883182764,-0.9905754753144173641032921295845881104469,0.9905754753144173641032921295845881104469},
+    {-0.0847750130417353059408824833553808275610,0.0847750130417353059408824833553808275610,-0.2518862256915054831374334298743633553386,0.2518862256915054831374334298743633553386,-0.4117511614628426297457508553634397685528,0.4117511614628426297457508553634397685528,-0.5597708310739475390249708652845583856106,0.5597708310739475390249708652845583856106,-0.6916870430603532238222896921797655522823,0.6916870430603532238222896921797655522823,-0.8037049589725231424353069087374024093151,0.8037049589725231424353069087374024093151,-0.8926024664975557021406871172075625509024,0.8926024664975557021406871172075625509024,-0.9558239495713977129653926567698363214731,0.9558239495713977129653926567698363214731,-0.9915651684209308980300079383596312254667,0.9915651684209308980300079383596312254667},
+    {0.0000000000000000000000000000000000000000,-0.1603586456402253668240831530056311748922,0.1603586456402253668240831530056311748922,-0.3165640999636298302810644145210972055793,0.3165640999636298302810644145210972055793,-0.4645707413759609383241411251219687983394,0.4645707413759609383241411251219687983394,-0.6005453046616809897884081692609470337629,0.6005453046616809897884081692609470337629,-0.7209661773352293856476080691209062933922,0.7209661773352293856476080691209062933922,-0.8227146565371428188484514976153150200844,0.8227146565371428188484514976153150200844,-0.9031559036148179009373393455462064594030,0.9031559036148179009373393455462064594030,-0.9602081521348300174878431789693422615528,0.9602081521348300174878431789693422615528,-0.9924068438435843519940249279898125678301,0.9924068438435843519940249279898125678301},
+    {-0.0765265211334973383117130651953630149364,0.0765265211334973383117130651953630149364,-0.2277858511416450681963397073559463024139,0.2277858511416450681963397073559463024139,-0.3737060887154195487624974703066982328892,0.3737060887154195487624974703066982328892,-0.5108670019508271264996324134699534624815,0.5108670019508271264996324134699534624815,-0.6360536807265150249790508496516849845648,0.6360536807265150249790508496516849845648,-0.7463319064601507957235071444301865994930,0.7463319064601507957235071444301865994930,-0.8391169718222187823286617458506952971220,0.8391169718222187823286617458506952971220,-0.9122344282513259461353527512983419001102,0.9122344282513259461353527512983419001102,-0.9639719272779138092843709273438435047865,0.9639719272779138092843709273438435047865,-0.9931285991850948846604296704754233360291,0.9931285991850948846604296704754233360291},
+    {0.0000000000000000000000000000000000000000,-0.1455618541608950933241573011400760151446,0.1455618541608950933241573011400760151446,-0.2880213168024011172185794293909566476941,0.2880213168024011172185794293909566476941,-0.4243421202074387776903563462838064879179,0.4243421202074387776903563462838064879179,-0.5516188358872198271853903861483559012413,0.5516188358872198271853903861483559012413,-0.6671388041974123384036943207320291548967,0.6671388041974123384036943207320291548967,-0.7684399634756778896260698275000322610140,0.7684399634756778896260698275000322610140,-0.8533633645833172964856316866644192487001,0.8533633645833172964856316866644192487001,-0.9200993341504007938524978271743748337030,0.9200993341504007938524978271743748337030,-0.9672268385663063128276917268522083759308,0.9672268385663063128276917268522083759308,-0.9937521706203894522602126926358323544264,0.9937521706203894522602126926358323544264},
+    {-0.0697392733197222253194169638845778536052,0.0697392733197222253194169638845778536052,-0.2078604266882212725509049278116435743868,0.2078604266882212725509049278116435743868,-0.3419358208920842412403828802780481055379,0.3419358208920842412403828802780481055379,-0.4693558379867570073962212973128771409392,0.4693558379867570073962212973128771409392,-0.5876404035069116016387624767958186566830,0.5876404035069116016387624767958186566830,-0.6944872631866827461522007070016115903854,0.6944872631866827461522007070016115903854,-0.7878168059792081123759999172762036323547,0.7878168059792081123759999172762036323547,-0.8658125777203001804949167308222968131304,0.8658125777203001804949167308222968131304,-0.9269567721871739829353487039043102413416,0.9269567721871739829353487039043102413416,-0.9700604978354286922481719557254109531641,0.9700604978354286922481719557254109531641,-0.9942945854823992402060639506089501082897,0.9942945854823992402060639506089501082897},
+    {0.0000000000000000000000000000000000000000,-0.1332568242984661088801345840693102218211,0.1332568242984661088801345840693102218211,-0.2641356809703449548543119362875586375594,0.2641356809703449548543119362875586375594,-0.3903010380302908144400930723350029438734,0.3903010380302908144400930723350029438734,-0.5095014778460075222099590064317453652620,0.5095014778460075222099590064317453652620,-0.6196098757636461229481028567533940076828,0.6196098757636461229481028567533940076828,-0.7186613631319501704908248029823880642653,0.7186613631319501704908248029823880642653,-0.8048884016188398993207897547108586877584,0.8048884016188398993207897547108586877584,-0.8767523582704416229560706597112584859133,0.8767523582704416229560706597112584859133,-0.9329710868260161493736859483760781586170,0.9329710868260161493736859483760781586170,-0.9725424712181152120393790028174407780170,0.9725424712181152120393790028174407780170,-0.9947693349975521570627279288601130247116,0.9947693349975521570627279288601130247116},
+    {-0.0640568928626056299791002857091370970011,0.0640568928626056299791002857091370970011,-0.1911188674736163106704367464772076345980,0.1911188674736163106704367464772076345980,-0.3150426796961633968408023065421730279922,0.3150426796961633968408023065421730279922,-0.4337935076260451272567308933503227308393,0.4337935076260451272567308933503227308393,-0.5454214713888395626995020393223967403173,0.5454214713888395626995020393223967403173,-0.6480936519369755455244330732966773211956,0.6480936519369755455244330732966773211956,-0.7401241915785543579175964623573236167431,0.7401241915785543579175964623573236167431,-0.8200019859739029470802051946520805358887,0.8200019859739029470802051946520805358887,-0.8864155270044010714869386902137193828821,0.8864155270044010714869386902137193828821,-0.9382745520027327978951348086411599069834,0.9382745520027327978951348086411599069834,-0.9747285559713094738043537290650419890881,0.9747285559713094738043537290650419890881,-0.9951872199970213106468008845695294439793,0.9951872199970213106468008845695294439793}
+};
+
+// Legendre-Gauss weights (wi values, defined by a function linked to in the Bezier primer article)
+static const CGFloat FBLegendreGaussWeightValues[][24] = {{},{},
+    {1.0000000000000000000000000000000000000000,1.0000000000000000000000000000000000000000},
+    {0.8888888888888888395456433499930426478386,0.5555555555555555802271783250034786760807,0.5555555555555555802271783250034786760807},
+    {0.6521451548625460947761212082696147263050,0.6521451548625460947761212082696147263050,0.3478548451374538497127275604725582525134,0.3478548451374538497127275604725582525134},
+    {0.5688888888888888883954564334999304264784,0.4786286704993664709029133064177585765719,0.4786286704993664709029133064177585765719,0.2369268850561890848993584768322762101889,0.2369268850561890848993584768322762101889},
+    {0.3607615730481386062677984227775596082211,0.3607615730481386062677984227775596082211,0.4679139345726910370615314604947343468666,0.4679139345726910370615314604947343468666,0.1713244923791703566706701167277060449123,0.1713244923791703566706701167277060449123},
+    {0.4179591836734694032529091600736137479544,0.3818300505051189230876218516641529276967,0.3818300505051189230876218516641529276967,0.2797053914892766446342875497066415846348,0.2797053914892766446342875497066415846348,0.1294849661688697028960604029634851031005,0.1294849661688697028960604029634851031005},
+    {0.3626837833783619902128236844873754307628,0.3626837833783619902128236844873754307628,0.3137066458778872690693617641954915598035,0.3137066458778872690693617641954915598035,0.2223810344533744820516574236535234376788,0.2223810344533744820516574236535234376788,0.1012285362903762586661571276636095717549,0.1012285362903762586661571276636095717549},
+    {0.3302393550012597822629345500899944454432,0.1806481606948573959137149813614087179303,0.1806481606948573959137149813614087179303,0.0812743883615744122650426106702070683241,0.0812743883615744122650426106702070683241,0.3123470770400028628799304897256661206484,0.3123470770400028628799304897256661206484,0.2606106964029354378098446431977208703756,0.2606106964029354378098446431977208703756},
+    {0.2955242247147528700246255084493895992637,0.2955242247147528700246255084493895992637,0.2692667193099963496294435572053771466017,0.2692667193099963496294435572053771466017,0.2190863625159820415877476307286997325718,0.2190863625159820415877476307286997325718,0.1494513491505805868886369580650352872908,0.1494513491505805868886369580650352872908,0.0666713443086881379917585377370414789766,0.0666713443086881379917585377370414789766},
+    {0.2729250867779006162194832540990319103003,0.2628045445102466515230332788632949814200,0.2628045445102466515230332788632949814200,0.2331937645919904822378043718344997614622,0.2331937645919904822378043718344997614622,0.1862902109277342621584949711177614517510,0.1862902109277342621584949711177614517510,0.1255803694649046120535018644659430719912,0.1255803694649046120535018644659430719912,0.0556685671161736631007421749472996452823,0.0556685671161736631007421749472996452823},
+    {0.2491470458134027732288728884668671526015,0.2491470458134027732288728884668671526015,0.2334925365383548057085505433860816992819,0.2334925365383548057085505433860816992819,0.2031674267230659247651658461109036579728,0.2031674267230659247651658461109036579728,0.1600783285433462210800570346691529266536,0.1600783285433462210800570346691529266536,0.1069393259953184266430881166343169752508,0.1069393259953184266430881166343169752508,0.0471753363865118277575838590109924552962,0.0471753363865118277575838590109924552962},
+    {0.2325515532308738975153517003491288051009,0.2262831802628972321933531475224299356341,0.2262831802628972321933531475224299356341,0.2078160475368885096170146198346628807485,0.2078160475368885096170146198346628807485,0.1781459807619457380578609217991470359266,0.1781459807619457380578609217991470359266,0.1388735102197872495199959530509659089148,0.1388735102197872495199959530509659089148,0.0921214998377284516317686779984796885401,0.0921214998377284516317686779984796885401,0.0404840047653158771612247335269785253331,0.0404840047653158771612247335269785253331},
+    {0.2152638534631577948985636794532183557749,0.2152638534631577948985636794532183557749,0.2051984637212956041896205761076998896897,0.2051984637212956041896205761076998896897,0.1855383974779378219999159682629397138953,0.1855383974779378219999159682629397138953,0.1572031671581935463599677404999965801835,0.1572031671581935463599677404999965801835,0.1215185706879031851679329179205524269491,0.1215185706879031851679329179205524269491,0.0801580871597602079292599341897584963590,0.0801580871597602079292599341897584963590,0.0351194603317518602714208952875196700916,0.0351194603317518602714208952875196700916},
+    {0.2025782419255612865072180284187197685242,0.1984314853271115786093048427574103698134,0.1984314853271115786093048427574103698134,0.1861610000155622113293674146916600875556,0.1861610000155622113293674146916600875556,0.1662692058169939202105780395868350751698,0.1662692058169939202105780395868350751698,0.1395706779261543240000520427201990969479,0.1395706779261543240000520427201990969479,0.1071592204671719394948325998484506271780,0.1071592204671719394948325998484506271780,0.0703660474881081243747615872052847407758,0.0703660474881081243747615872052847407758,0.0307532419961172691358353148416426847689,0.0307532419961172691358353148416426847689},
+    {0.1894506104550685021692402187909465283155,0.1894506104550685021692402187909465283155,0.1826034150449235837765371570640127174556,0.1826034150449235837765371570640127174556,0.1691565193950025358660127494658809155226,0.1691565193950025358660127494658809155226,0.1495959888165767359691216142891789786518,0.1495959888165767359691216142891789786518,0.1246289712555338768940060845125117339194,0.1246289712555338768940060845125117339194,0.0951585116824927856882254673109855502844,0.0951585116824927856882254673109855502844,0.0622535239386478936318702892549481475726,0.0622535239386478936318702892549481475726,0.0271524594117540964133272751723779947497,0.0271524594117540964133272751723779947497},
+    {0.1794464703562065333031227964966092258692,0.1765627053669926449508409405098063871264,0.1765627053669926449508409405098063871264,0.1680041021564500358653759803928551264107,0.1680041021564500358653759803928551264107,0.1540457610768102836296122859494062140584,0.1540457610768102836296122859494062140584,0.1351363684685254751283167706787935458124,0.1351363684685254751283167706787935458124,0.1118838471934039680011352402289048768580,0.1118838471934039680011352402289048768580,0.0850361483171791776580761279547004960477,0.0850361483171791776580761279547004960477,0.0554595293739872027827253475606994470581,0.0554595293739872027827253475606994470581,0.0241483028685479314545681006620725383982,0.0241483028685479314545681006620725383982},
+    {0.1691423829631436004383715498988749459386,0.1691423829631436004383715498988749459386,0.1642764837458327298325144738555536605418,0.1642764837458327298325144738555536605418,0.1546846751262652419622867228099494241178,0.1546846751262652419622867228099494241178,0.1406429146706506538855308008351130411029,0.1406429146706506538855308008351130411029,0.1225552067114784593471199514169711619616,0.1225552067114784593471199514169711619616,0.1009420441062871681703327908508072141558,0.1009420441062871681703327908508072141558,0.0764257302548890515847546112127020023763,0.0764257302548890515847546112127020023763,0.0497145488949697969549568199454370187595,0.0497145488949697969549568199454370187595,0.0216160135264833117019200869890482863411,0.0216160135264833117019200869890482863411},
+    {0.1610544498487836984068621859478298574686,0.1589688433939543399375793342187535017729,0.1589688433939543399375793342187535017729,0.1527660420658596696075193221986410208046,0.1527660420658596696075193221986410208046,0.1426067021736066031678547005867585539818,0.1426067021736066031678547005867585539818,0.1287539625393362141547726196222356520593,0.1287539625393362141547726196222356520593,0.1115666455473339896409257221421285066754,0.1115666455473339896409257221421285066754,0.0914900216224499990280705219447554554790,0.0914900216224499990280705219447554554790,0.0690445427376412262931992813719261903316,0.0690445427376412262931992813719261903316,0.0448142267656995996194524423117400147021,0.0448142267656995996194524423117400147021,0.0194617882297264781221723950466184760444,0.0194617882297264781221723950466184760444},
+    {0.1527533871307258372951309866039082407951,0.1527533871307258372951309866039082407951,0.1491729864726037413369397199858212843537,0.1491729864726037413369397199858212843537,0.1420961093183820411756101975697674788535,0.1420961093183820411756101975697674788535,0.1316886384491766370796739238357986323535,0.1316886384491766370796739238357986323535,0.1181945319615184120110029653005767613649,0.1181945319615184120110029653005767613649,0.1019301198172404415709380032240005675703,0.1019301198172404415709380032240005675703,0.0832767415767047547436874310733401216567,0.0832767415767047547436874310733401216567,0.0626720483341090678353069165495980996639,0.0626720483341090678353069165495980996639,0.0406014298003869386621822457072994438931,0.0406014298003869386621822457072994438931,0.0176140071391521178811867542890468030237,0.0176140071391521178811867542890468030237},
+    {0.1460811336496904144777175815761438570917,0.1445244039899700461138110085812513716519,0.1445244039899700461138110085812513716519,0.1398873947910731496691028041823301464319,0.1398873947910731496691028041823301464319,0.1322689386333374683690777828815043903887,0.1322689386333374683690777828815043903887,0.1218314160537285334440227302366110961884,0.1218314160537285334440227302366110961884,0.1087972991671483785625085261017375160009,0.1087972991671483785625085261017375160009,0.0934444234560338621298214434318651910871,0.0934444234560338621298214434318651910871,0.0761001136283793039316591944043466355652,0.0761001136283793039316591944043466355652,0.0571344254268572049326735395879950374365,0.0571344254268572049326735395879950374365,0.0369537897708524937234741969405149575323,0.0369537897708524937234741969405149575323,0.0160172282577743345377552230957007850520,0.0160172282577743345377552230957007850520},
+    {0.1392518728556319806966001806358690373600,0.1392518728556319806966001806358690373600,0.1365414983460151721050834794368711300194,0.1365414983460151721050834794368711300194,0.1311735047870623838139891859100316651165,0.1311735047870623838139891859100316651165,0.1232523768105124178928733158500108402222,0.1232523768105124178928733158500108402222,0.1129322960805392156435900119504367467016,0.1129322960805392156435900119504367467016,0.1004141444428809648581335522976587526500,0.1004141444428809648581335522976587526500,0.0859416062170677286236042391465161927044,0.0859416062170677286236042391465161927044,0.0697964684245204886048341563764552120119,0.0697964684245204886048341563764552120119,0.0522933351526832859712534684604179346934,0.0522933351526832859712534684604179346934,0.0337749015848141515006020085820637177676,0.0337749015848141515006020085820637177676,0.0146279952982721998810955454928262042813,0.0146279952982721998810955454928262042813},
+    {0.1336545721861061852830943053049850277603,0.1324620394046966131984532921705977059901,0.1324620394046966131984532921705977059901,0.1289057221880821613169132433540653437376,0.1289057221880821613169132433540653437376,0.1230490843067295336776822978208656422794,0.1230490843067295336776822978208656422794,0.1149966402224113642960290349037677515298,0.1149966402224113642960290349037677515298,0.1048920914645414120824895576333801727742,0.1048920914645414120824895576333801727742,0.0929157660600351542612429511791560798883,0.0929157660600351542612429511791560798883,0.0792814117767189491248203125906002242118,0.0792814117767189491248203125906002242118,0.0642324214085258499151720457120973151177,0.0642324214085258499151720457120973151177,0.0480376717310846690356385124687221832573,0.0480376717310846690356385124687221832573,0.0309880058569794447631551292943186126649,0.0309880058569794447631551292943186126649,0.0134118594871417712993677540112003043760,0.0134118594871417712993677540112003043760},
+    {0.1279381953467521593204025975865079089999,0.1279381953467521593204025975865079089999,0.1258374563468283025002847352880053222179,0.1258374563468283025002847352880053222179,0.1216704729278033914052770114722079597414,0.1216704729278033914052770114722079597414,0.1155056680537255991980671865348995197564,0.1155056680537255991980671865348995197564,0.1074442701159656343712356374453520402312,0.1074442701159656343712356374453520402312,0.0976186521041138843823858906034729443491,0.0976186521041138843823858906034729443491,0.0861901615319532743431096832864568568766,0.0861901615319532743431096832864568568766,0.0733464814110802998392557583429152145982,0.0733464814110802998392557583429152145982,0.0592985849154367833380163688161701429635,0.0592985849154367833380163688161701429635,0.0442774388174198077483545432642131345347,0.0442774388174198077483545432642131345347,0.0285313886289336633705904233693217975087,0.0285313886289336633705904233693217975087,0.0123412297999872001830201639904771582223,0.0123412297999872001830201639904771582223}
+};
+
+static CGFloat FBGaussQuadratureBaseForCubic(CGFloat t, CGFloat p1, CGFloat p2, CGFloat p3, CGFloat p4)
+{
+    float t1 = -3.0 * p1 + 9.0 * p2 - 9.0 * p3 + 3.0 * p4;
+    float t2 = t * t1 + 6.0 * p1 - 12.0 * p2 + 6.0 * p3;
+    return t * t2 - 3.0 * p1 + 3.0 * p2;
+    //return t * (t * (-3 * p1 + 9 * p2 - 9 * p3 + 3 * p4) + 6 * p1 + 12 * p2 + 3 * p3) - 3 * p1 + 3 * p2;
+}
+
+static CGFloat FBGaussQuadratureFOfTForCubic(CGFloat t, CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4)
+{
+    CGFloat baseX = FBGaussQuadratureBaseForCubic(t, p1.x, p2.x, p3.x, p4.x);
+    CGFloat baseY = FBGaussQuadratureBaseForCubic(t, p1.y, p2.y, p3.y, p4.y);
+    
+    return sqrtf(baseX * baseX + baseY * baseY);
+}
+
+static CGFloat FBGaussQuadratureComputeCurveLengthForCubic(CGFloat z, NSUInteger steps, CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4)
+{
+    CGFloat z2 = z / 2.0;
+    CGFloat sum = 0.0;
+    for (NSUInteger i = 0; i < steps; i++) {
+        CGFloat correctedT = z2 * FBLegendreGaussAbscissaeValues[steps][i] + z2;
+        sum += FBLegendreGaussWeightValues[steps][i] * FBGaussQuadratureFOfTForCubic(correctedT, p1, p2, p3, p4);
+    }
+    return z2 * sum;
+}
+
 //////////////////////////////////////////////////////////////////////////////////
 // FBBezierCurve
 //
 - (NSArray *) splitCurveAtParameter:(CGFloat)t;
 - (NSArray *) convexHull;
 - (FBBezierCurve *) bezierClipWithBezierCurve:(FBBezierCurve *)curve original:(FBBezierCurve *)originalCurve rangeOfOriginal:(FBRange *)originalRange intersects:(BOOL *)intersects;
-- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve usRange:(FBRange *)usRange themRange:(FBRange *)themRange originalUs:(FBBezierCurve *)originalUs originalThem:(FBBezierCurve *)originalThem;
+- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve usRange:(FBRange *)usRange themRange:(FBRange *)themRange originalUs:(FBBezierCurve *)originalUs originalThem:(FBBezierCurve *)originalThem overlapRange:(FBBezierIntersectRange **)intersectRange depth:(NSUInteger)depth;
 - (CGFloat) refineParameter:(CGFloat)parameter forPoint:(NSPoint)point;
 
 @property (readonly, getter = isPoint) BOOL point;
 @synthesize controlPoint1=_controlPoint1;
 @synthesize controlPoint2=_controlPoint2;
 @synthesize endPoint2=_endPoint2;
+@synthesize isStraightLine = _isStraightLine;
 
 + (NSArray *) bezierCurvesFromBezierPath:(NSBezierPath *)path
 {
         _controlPoint2 = FBAddPoint(startPoint, FBUnitScalePoint(leftTangent, 2.0 * distance / 3.0));
         _endPoint1 = startPoint;
         _endPoint2 = endPoint;
+		
+		// GPC: flag that this is a straight line. Later, we can use this to restore the segment to a lineTo: rather than a curveTo: element.
+		_isStraightLine = YES;
     }
     
     return self;
     [super dealloc];
 }
 
+- (BOOL) isEqual:(id)object
+{
+    if ( ![object isKindOfClass:[FBBezierCurve class]] )
+        return NO;
+    
+    FBBezierCurve *other = object;
+    if ( self.isPoint || other.isPoint )
+        return NO;
+    if ( self.isStraightLine != other.isStraightLine )
+        return NO;
+    
+    if ( self.isStraightLine )
+        return FBArePointsClose(self.endPoint1, other.endPoint1) && FBArePointsClose(self.endPoint2, other.endPoint2);
+    return FBArePointsClose(self.endPoint1, other.endPoint1) && FBArePointsClose(self.controlPoint1, other.controlPoint1) && FBArePointsClose(self.controlPoint2, other.controlPoint2) && FBArePointsClose(self.endPoint2, other.endPoint2);
+}
+
 - (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve
 {
+    return [self intersectionsWithBezierCurve:curve overlapRange:nil];
+}
+
+- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve overlapRange:(FBBezierIntersectRange **)intersectRange
+{
     FBRange usRange = FBRangeMake(0, 1);
     FBRange themRange = FBRangeMake(0, 1);
-    return [self intersectionsWithBezierCurve:curve usRange:&usRange themRange:&themRange originalUs:self originalThem:curve];
+    return [self intersectionsWithBezierCurve:curve usRange:&usRange themRange:&themRange originalUs:self originalThem:curve overlapRange:intersectRange depth:0];
 }
 
-- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve usRange:(FBRange *)usRange themRange:(FBRange *)themRange originalUs:(FBBezierCurve *)originalUs originalThem:(FBBezierCurve *)originalThem
+- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve usRange:(FBRange *)usRange themRange:(FBRange *)themRange originalUs:(FBBezierCurve *)originalUs originalThem:(FBBezierCurve *)originalThem overlapRange:(FBBezierIntersectRange **)intersectRange depth:(NSUInteger)depth
 {
     // This is the main work loop. At a high level this method sits in a loop and removes sections (ranges) of the two bezier curves that it knows
     //  don't intersect (how it knows that is covered in the appropriate method). The idea is to whittle the curves down to the point where they
     
     static const NSUInteger places = 6; // How many decimals place to calculate the solution out to
     static const NSUInteger maxIterations = 500; // how many iterations to allow before we just give up
+    static const NSUInteger maxDepth = 10; // how many recursive calls to allow before we just give up
     static const CGFloat minimumChangeNeeded = 0.20; // how much to clip off for a given iteration minimum before we subdivide the curve
 
     FBBezierCurve *us = self; // us is self, but clipped down to where the intersection is
     FBBezierCurve *them = curve; // them is the other curve we're intersecting with, but clipped down to where the intersection is
-    FBBezierCurve *previousUs = us;
-    FBBezierCurve *previousThem = them;
+    FBBezierCurve *nonpointUs = us;
+    FBBezierCurve *nonpointThem = them;
     
     // Don't check for convergence until we actually see if we intersect or not. i.e. Make sure we go through at least once, otherwise the results
     //  don't mean anything. Be sure to stop as soon as either range converges, otherwise calculations for the other range goes funky because one
     //  curve is essentially a point.
     NSUInteger iterations = 0;
-    while ( iterations < maxIterations && ((iterations == 0) || (!FBRangeHasConverged(*usRange, places) && !FBRangeHasConverged(*themRange, places))) ) {
+    while ( iterations < maxIterations && ((iterations == 0) || (!FBRangeHasConverged(*usRange, places) || !FBRangeHasConverged(*themRange, places))) ) {
         // Remember what the current range is so we can calculate how much it changed later
         FBRange previousUsRange = *usRange;
         FBRange previousThemRange = *themRange;
         // Remove the range from ourselves that doesn't intersect with them. If the other curve is already a point, use the previous iteration's
         //  copy of them so calculations still work.
         BOOL intersects = NO;
-        us = [us bezierClipWithBezierCurve:them.isPoint ? previousThem : them original:originalUs rangeOfOriginal:usRange intersects:&intersects];
+        if ( !them.isPoint )
+            nonpointThem = them;
+        us = [nonpointUs bezierClipWithBezierCurve:nonpointThem original:originalUs rangeOfOriginal:usRange intersects:&intersects];
         if ( !intersects )
             return [NSArray array]; // If they don't intersect at all stop now
+        if ( iterations > 0 && (us.isPoint || them.isPoint) )
+            break;
+        
         // Remove the range of them that doesn't intersect with us
-        them = [them bezierClipWithBezierCurve:us.isPoint ? previousUs : us original:originalThem rangeOfOriginal:themRange intersects:&intersects];
+        if ( !us.isPoint )
+            nonpointUs = us;
+        them = [nonpointThem bezierClipWithBezierCurve:nonpointUs original:originalThem rangeOfOriginal:themRange intersects:&intersects];
         if ( !intersects )
             return [NSArray array];  // If they don't intersect at all stop now
-        
-        // If either curve has been reduced to a point, stop now even if the range hasn't properly converged. Once curves become points, the math
-        //  falls apart.
-        if ( us.isPoint || them.isPoint )
+        if ( iterations > 0 && (us.isPoint || them.isPoint) )
             break;
         
         // See if either of curves ranges is reduced by less than 20%.
         CGFloat percentChangeInUs = (FBRangeGetSize(previousUsRange) - FBRangeGetSize(*usRange)) / FBRangeGetSize(previousUsRange);
         CGFloat percentChangeInThem = (FBRangeGetSize(previousThemRange) - FBRangeGetSize(*themRange)) / FBRangeGetSize(previousThemRange);
+        BOOL didNotSplit = NO;
         if ( percentChangeInUs < minimumChangeNeeded && percentChangeInThem < minimumChangeNeeded ) {
-            // We're not converging fast enough, likely because there are multiple intersections here. So
-            //  divide and conquer. Divide the longer curve in half, and recurse
+            // We're not converging fast enough, likely because there are multiple intersections here. 
+            //  Or the curves are the same, check for that first
+            if ( [us isEqual:them] ) {
+                if ( intersectRange != nil ) {
+                    *intersectRange = [FBBezierIntersectRange intersectRangeWithCurve1:originalUs parameterRange1:*usRange curve2:originalThem parameterRange2:*themRange reversed:NO];
+                }
+                return [NSArray array];
+            }
+            if ( [us isEqual:[them reversedCurve]] ) {
+                if ( intersectRange != nil ) {
+                    *intersectRange = [FBBezierIntersectRange intersectRangeWithCurve1:originalUs parameterRange1:*usRange curve2:originalThem parameterRange2:*themRange reversed:YES];
+                }
+                return [NSArray array];
+            }
+
+            // Divide and conquer. Divide the longer curve in half, and recurse
             if ( FBRangeGetSize(*usRange) > FBRangeGetSize(*themRange) ) {
                 // Since our remaining range is longer, split the remains of us in half at the midway point
                 FBRange usRange1 = FBRangeMake(usRange->minimum, (usRange->minimum + usRange->maximum) / 2.0);
                 FBBezierCurve *us2 = [originalUs subcurveWithRange:usRange2];
                 FBRange themRangeCopy2 = *themRange; // make a local copy because it'll get modified when we recurse
                 
-                // Compute the intersections between the two halves of us and them
-                NSArray *intersections1 = [us1 intersectionsWithBezierCurve:them usRange:&usRange1 themRange:&themRangeCopy1 originalUs:originalUs originalThem:originalThem];
-                NSArray *intersections2 = [us2 intersectionsWithBezierCurve:them usRange:&usRange2 themRange:&themRangeCopy2 originalUs:originalUs originalThem:originalThem];
+                BOOL range1ConvergedAlready = FBRangeHasConverged(usRange1, places) && FBRangeHasConverged(*themRange, places);
+                BOOL range2ConvergedAlready = FBRangeHasConverged(usRange2, places) && FBRangeHasConverged(*themRange, places);
                 
-                return [intersections1 arrayByAddingObjectsFromArray:intersections2];
+                if ( !range1ConvergedAlready && !range2ConvergedAlready && depth < maxDepth ) {
+                    // Compute the intersections between the two halves of us and them
+                    NSArray *intersections1 = [us1 intersectionsWithBezierCurve:them usRange:&usRange1 themRange:&themRangeCopy1 originalUs:originalUs originalThem:originalThem overlapRange:intersectRange depth:depth + 1];
+                    NSArray *intersections2 = [us2 intersectionsWithBezierCurve:them usRange:&usRange2 themRange:&themRangeCopy2 originalUs:originalUs originalThem:originalThem overlapRange:intersectRange depth:depth + 1];
+                    
+                    return [intersections1 arrayByAddingObjectsFromArray:intersections2];
+                } else
+                    didNotSplit = YES;
             } else {
                 // Since their remaining range is longer, split the remains of them in half at the midway point
                 FBRange themRange1 = FBRangeMake(themRange->minimum, (themRange->minimum + themRange->maximum) / 2.0);
                 FBBezierCurve *them2 = [originalThem subcurveWithRange:themRange2];
                 FBRange usRangeCopy2 = *usRange;  // make a local copy because it'll get modified when we recurse
 
-                // Compute the intersections between the two halves of them and us
-                NSArray *intersections1 = [us intersectionsWithBezierCurve:them1 usRange:&usRangeCopy1 themRange:&themRange1 originalUs:originalUs originalThem:originalThem];
-                NSArray *intersections2 = [us intersectionsWithBezierCurve:them2 usRange:&usRangeCopy2 themRange:&themRange2 originalUs:originalUs originalThem:originalThem];
-                
-                return [intersections1 arrayByAddingObjectsFromArray:intersections2];
+                BOOL range1ConvergedAlready = FBRangeHasConverged(themRange1, places) && FBRangeHasConverged(*usRange, places);
+                BOOL range2ConvergedAlready = FBRangeHasConverged(themRange2, places) && FBRangeHasConverged(*usRange, places);
+
+                if ( !range1ConvergedAlready && !range2ConvergedAlready && depth < maxDepth ) {
+                    // Compute the intersections between the two halves of them and us
+                    NSArray *intersections1 = [us intersectionsWithBezierCurve:them1 usRange:&usRangeCopy1 themRange:&themRange1 originalUs:originalUs originalThem:originalThem overlapRange:intersectRange depth:depth + 1];
+                    NSArray *intersections2 = [us intersectionsWithBezierCurve:them2 usRange:&usRangeCopy2 themRange:&themRange2 originalUs:originalUs originalThem:originalThem overlapRange:intersectRange depth:depth + 1];
+                    
+                    return [intersections1 arrayByAddingObjectsFromArray:intersections2];
+                } else 
+                    didNotSplit = YES;
+            }
+            
+            if ( didNotSplit && (FBRangeGetSize(previousUsRange) - FBRangeGetSize(*usRange) == 0) && (FBRangeGetSize(previousThemRange) - FBRangeGetSize(*themRange) == 0) ) {
+                // We're not converging at _all_ and we can't split, so we need to bail out. 
+                return [NSArray array]; // no intersections
             }
         }
         
         iterations++;
-        previousUs = us;
-        previousThem = them;
     }
     
+    
     // It's possible that one of the curves has converged, but the other hasn't. Since the math becomes wonky once a curve becomes a point,
     //  the loop stops as soon as either curve converges. However for our purposes we need _both_ curves to converge; that is we need
     //  the parameter for each curve where they intersect. Fortunately, since one curve did converge we know the 2D point where they converge,
     //  plus we have a reasonable approximation for the parameter for the curve that didn't. That means we can use Newton's method to refine
     //  the parameter of the curve that did't converge.
+    BOOL hadConverged = YES;
+    if ( !FBRangeHasConverged(*usRange, places) || !FBRangeHasConverged(*themRange, places) ) {
+        // We bail out of the main loop as soon as we know things intersect, but before the math falls apart. Unfortunately sometimes this
+        //  means we don't always get the best estimate of the parameters. Below we fall back to Netwon's method, but it's accuracy is 
+        //  dependant on our previous calculations. So here assume things intersect and just try to tighten up the parameters. If the
+        //  math falls apart because everything's a point, that's OK since we already have a "reasonable" estimation of the parameters.
+        for (int i = 0; i < 3; i++) {
+            BOOL intersects = NO;
+            us = [us bezierClipWithBezierCurve:them original:originalUs rangeOfOriginal:usRange intersects:&intersects];  
+            if ( !intersects )
+                us = [nonpointUs bezierClipWithBezierCurve:nonpointThem original:originalUs rangeOfOriginal:usRange intersects:&intersects];
+            them = [them bezierClipWithBezierCurve:us original:originalThem rangeOfOriginal:themRange intersects:&intersects];
+            if ( !intersects )
+                them = [nonpointThem bezierClipWithBezierCurve:nonpointUs original:originalThem rangeOfOriginal:themRange intersects:&intersects];
+            if ( !them.isPoint )
+                nonpointThem = them;
+            if ( !us.isPoint )
+                nonpointUs = us;
+        }
+    }
     if ( FBRangeHasConverged(*usRange, places) && !FBRangeHasConverged(*themRange, places) ) {
         // Refine the them range since it didn't converge
-        NSPoint intersectionPoint = [originalUs pointAtParameter:usRange->minimum leftBezierCurve:nil rightBezierCurve:nil];
+        NSPoint intersectionPoint = [originalUs pointAtParameter:FBRangeAverage(*usRange) leftBezierCurve:nil rightBezierCurve:nil];
         CGFloat refinedParameter = FBRangeAverage(*themRange); // Although the range didn't converge, it should be a reasonable approximation which is all Newton needs
-        for (NSUInteger i = 0; i < 3; i++)
+        for (NSUInteger i = 0; i < 3; i++) {
             refinedParameter = [originalThem refineParameter:refinedParameter forPoint:intersectionPoint];
+            refinedParameter = MIN(themRange->maximum, MAX(themRange->minimum, refinedParameter));
+        }
         themRange->minimum = refinedParameter;
         themRange->maximum = refinedParameter;
+        hadConverged = NO;
     } else if ( !FBRangeHasConverged(*usRange, places) && FBRangeHasConverged(*themRange, places) ) {
         // Refine the us range since it didn't converge
-        NSPoint intersectionPoint = [originalThem pointAtParameter:themRange->minimum leftBezierCurve:nil rightBezierCurve:nil];
+        NSPoint intersectionPoint = [originalThem pointAtParameter:FBRangeAverage(*themRange) leftBezierCurve:nil rightBezierCurve:nil];
         CGFloat refinedParameter = FBRangeAverage(*usRange); // Although the range didn't converge, it should be a reasonable approximation which is all Newton needs
-        for (NSUInteger i = 0; i < 3; i++)
+        for (NSUInteger i = 0; i < 3; i++) {
             refinedParameter = [originalUs refineParameter:refinedParameter forPoint:intersectionPoint];
+            refinedParameter = MIN(usRange->maximum, MAX(usRange->minimum, refinedParameter));
+        }
         usRange->minimum = refinedParameter;
-        usRange->maximum = refinedParameter;        
+        usRange->maximum = refinedParameter; 
+        hadConverged = NO;
     }
-    
+    if ( !hadConverged ) {
+        // Since one of them didn't converge, we need to make sure they actually intersect. Compute the point from both and compare
+        NSPoint intersectionPoint = [originalUs pointAtParameter:FBRangeAverage(*usRange) leftBezierCurve:nil rightBezierCurve:nil];
+        NSPoint checkPoint = [originalThem pointAtParameter:FBRangeAverage(*themRange) leftBezierCurve:nil rightBezierCurve:nil];
+        if ( !FBArePointsCloseWithOptions(intersectionPoint, checkPoint, 1e-3) )
+            return [NSArray array];
+    }
     // Return the final intersection, which we represent by the original curves and the parameters where they intersect. The parameter values are useful
     //  later in the boolean operations, plus it allows us to do lazy calculations.
-    return [NSArray arrayWithObject:[FBBezierIntersection intersectionWithCurve1:originalUs parameter1:usRange->minimum curve2:originalThem parameter2:themRange->minimum]];
+    return [NSArray arrayWithObject:[FBBezierIntersection intersectionWithCurve1:originalUs parameter1:FBRangeAverage(*usRange) curve2:originalThem parameter2:FBRangeAverage(*themRange)]];
 }
 
 - (FBBezierCurve *) bezierClipWithBezierCurve:(FBBezierCurve *)curve original:(FBBezierCurve *)originalCurve rangeOfOriginal:(FBRange *)originalRange intersects:(BOOL *)intersects
     
     // Combine to form Voltron. Take the intersection of the regular fat line range and the perpendicular one.
     FBRange clippedRange = FBRangeMake(MAX(regularClippedRange.minimum, perpendicularClippedRange.minimum), MIN(regularClippedRange.maximum, perpendicularClippedRange.maximum));    
-    
+            
     // Right now the clipped range is relative to ourself, not the original curve. So map the newly clipped range onto the original range
     FBRange newRange = FBRangeMake(FBRangeScaleNormalizedValue(*originalRange, clippedRange.minimum), FBRangeScaleNormalizedValue(*originalRange, clippedRange.maximum));    
     *originalRange = newRange;
     return [curves2 objectAtIndex:0];
 }
 
+- (NSArray *) splitSubcurvesWithRange:(FBRange)range
+{
+    // Return a bezier curve representing the parameter range specified. We do this by splitting
+    //  twice: once on the minimum, the splitting the result of that on the maximum.
+    NSMutableArray *subcurves = [NSMutableArray arrayWithCapacity:3];
+    NSArray *curves1 = [self splitCurveAtParameter:range.minimum];
+    if ( range.minimum == 0.0 )
+        [subcurves addObject:[NSNull null]];
+    else
+        [subcurves addObject:[curves1 objectAtIndex:0]];
+    FBBezierCurve *upperCurve = [curves1 objectAtIndex:1];
+    if ( range.minimum == 1.0 ) {
+        [subcurves addObject:upperCurve];
+        [subcurves addObject:[NSNull null]];
+        return subcurves; // avoid the divide by zero below
+    }
+    // We need to adjust the maximum parameter to fit on the new curve before we split again
+    CGFloat adjustedMaximum = (range.maximum - range.minimum) / (1.0 - range.minimum);
+    NSArray *curves2 = [upperCurve splitCurveAtParameter:adjustedMaximum];
+    [subcurves addObjectsFromArray:curves2];
+    return subcurves;
+}
+
+- (FBBezierCurve *) reversedCurve
+{
+	FBBezierCurve *reversedCurve = [[[self class] alloc] initWithEndPoint1:self.endPoint2 controlPoint1:self.controlPoint2 controlPoint2:self.controlPoint1 endPoint2:self.endPoint1];
+	[reversedCurve setIsStraightLine:self.isStraightLine];
+	return [reversedCurve autorelease];
+}
+
+
+
 - (NSPoint) pointAtParameter:(CGFloat)parameter leftBezierCurve:(FBBezierCurve **)leftBezierCurve rightBezierCurve:(FBBezierCurve **)rightBezierCurve
 {    
     // This method is a simple wrapper around the BezierWithPoints() helper function. It computes the 2D point at the given parameter,
 
     NSPoint point = BezierWithPoints(3, points, parameter, leftCurve, rightCurve);
     
-    if ( leftBezierCurve != nil )
+    if ( leftBezierCurve != nil ) {
         *leftBezierCurve = [FBBezierCurve bezierCurveWithEndPoint1:leftCurve[0] controlPoint1:leftCurve[1] controlPoint2:leftCurve[2] endPoint2:leftCurve[3]];
-    if ( rightBezierCurve != nil )
+		[*leftBezierCurve setIsStraightLine:self.isStraightLine];	// GPC: propagate straight line flag to subcurves
+	}
+    if ( rightBezierCurve != nil ) {
         *rightBezierCurve = [FBBezierCurve bezierCurveWithEndPoint1:rightCurve[0] controlPoint1:rightCurve[1] controlPoint2:rightCurve[2] endPoint2:rightCurve[3]];
+		[*rightBezierCurve setIsStraightLine:self.isStraightLine];	// GPC: propagate straight line flag to subcurves
+	}
     return point;
 }
 
     return [NSArray arrayWithObjects:leftCurve, rightCurve, nil];
 }
 
+- (CGFloat) length
+{
+    return [self lengthAtParameter:1.0];
+}
+
+- (CGFloat) lengthAtParameter:(CGFloat)parameter
+{
+    return FBGaussQuadratureComputeCurveLengthForCubic(parameter, 12, _endPoint1, _controlPoint1, _controlPoint2, _endPoint2);
+}
+
 - (NSArray *) convexHull
 {
     // Compute the convex hull for this bezier curve. The convex hull is made up of the end and control points.
     NSPoint lowestValue = [[points objectAtIndex:0] pointValue];
     for (NSUInteger i = 0; i < [points count]; i++) {
         NSPoint point = [[points objectAtIndex:i] pointValue];
-        if ( point.y < lowestValue.y || (point.y == lowestValue.y && point.x > lowestValue.x) ) {
+        if ( point.y < lowestValue.y || (FBAreValuesClose(point.y, lowestValue.y) && point.x > lowestValue.x) ) {
             lowestIndex = i;
             lowestValue = point;
         }
                 [pointsToDelete addObject:obj2];
                 return NSOrderedDescending;
             }
-            [pointsToDelete addObject:obj1];            
+            // At this point, the decision is somewhat arbitrary since the distances are the
+            //  same. However, we should prefer deleting an interior point over an exterior
+            if ( point1.x == 0.0 || point1.x == 1.0 )
+                [pointsToDelete addObject:obj2];
+            else
+                [pointsToDelete addObject:obj1];            
             return NSOrderedSame;
         } else if ( area < 0.0 )
             // point2 is to the right of the line formed by lowestValue, point1
             // Turning left is good, so keep going
             [results addObject:[points objectAtIndex:i]];
             i++;
-        } else 
+        } else {
             // Turning right is bad, so remove the top point
             [results removeLastObject];
+            // We have to have at least two points, so if we drop below that, just take the
+            //  one under consideration, and move on
+            if ( [results count] < 2 ) {
+                [results addObject:[points objectAtIndex:i]];
+                i++;
+            }
+        }
     }
     
     return results;    
 {
     // If the two end points are close together, then we're a point. Ignore the control
     //  points.
-    return FBArePointsClose(_endPoint1, _endPoint2);
+    static const CGFloat FBClosenessThreshold = 1e-5;
+    
+    return FBArePointsCloseWithOptions(_endPoint1, _endPoint2, FBClosenessThreshold) 
+        && FBArePointsCloseWithOptions(_endPoint1, _controlPoint1, FBClosenessThreshold) 
+        && FBArePointsCloseWithOptions(_endPoint1, _controlPoint2, FBClosenessThreshold);
 }
 
-- (void) round
+- (NSRect) bounds
+{    
+    // Start with the end points
+    NSPoint topLeft = [self pointAtParameter:0 leftBezierCurve:nil rightBezierCurve:nil];
+    NSPoint bottomRight = topLeft;
+    NSPoint lastPoint = [self pointAtParameter:1 leftBezierCurve:nil rightBezierCurve:nil];
+    FBExpandBoundsByPoint(&topLeft, &bottomRight, lastPoint);
+    
+    // Find the roots, which should be the extremities
+    NSArray *xRoots = FBComputeCubicFirstDerivativeRoots(_endPoint1.x, _controlPoint1.x, _controlPoint2.x, _endPoint2.x);
+    for (NSNumber *root in xRoots) {
+        CGFloat t = [root floatValue];
+        if ( t < 0 || t > 1 )
+            continue;
+        
+        NSPoint location = [self pointAtParameter:t leftBezierCurve:nil rightBezierCurve:nil];
+        FBExpandBoundsByPoint(&topLeft, &bottomRight, location);
+    }
+    
+    NSArray *yRoots = FBComputeCubicFirstDerivativeRoots(_endPoint1.y, _controlPoint1.y, _controlPoint2.y, _endPoint2.y);
+    for (NSNumber *root in yRoots) {
+        CGFloat t = [root floatValue];
+        if ( t < 0 || t > 1 )
+            continue;
+        
+        NSPoint location = [self pointAtParameter:t leftBezierCurve:nil rightBezierCurve:nil];
+        FBExpandBoundsByPoint(&topLeft, &bottomRight, location);
+    }
+    
+    return NSMakeRect(topLeft.x, topLeft.y, bottomRight.x - topLeft.x, bottomRight.y - topLeft.y);
+}
+
+- (NSBezierPath *) bezierPath
 {
-    // Round the end and control points to the nearest integral value.
-    _endPoint1 = FBRoundPoint(_endPoint1);
-    _controlPoint1 = FBRoundPoint(_controlPoint1);
-    _controlPoint2 = FBRoundPoint(_controlPoint2);
-    _endPoint2 = FBRoundPoint(_endPoint2);
+    NSBezierPath *path = [NSBezierPath bezierPath];
+    [path moveToPoint:_endPoint1];
+    [path curveToPoint:_endPoint2 controlPoint1:_controlPoint1 controlPoint2:_controlPoint2];
+    return path;
 }
 
 - (NSString *) description
 {
-    return [NSString stringWithFormat:@"<%@ (%f, %f)-[%f, %f] curve to [%f, %f]-(%f, %f)>", 
+    return [NSString stringWithFormat:@"<%@ (%.18f, %.18f)-[%.18f, %.18f] curve to [%.18f, %.18f]-(%.18f, %.18f)>", 
             NSStringFromClass([self class]), 
             _endPoint1.x, _endPoint1.y, _controlPoint1.x, _controlPoint1.y,
             _controlPoint2.x, _controlPoint2.y, _endPoint2.x, _endPoint2.y];

File VectorBoolean/FBBezierGraph.h

 
 #import <Cocoa/Cocoa.h>
 
+@class FBBezierContour;
+
 // FBBezierGraph is more or less an exploded version of an NSBezierPath, and
 //  the two can be converted between easily. FBBezierGraph allows boolean
 //  operations to be performed by allowing the curves to be annotated with
 
 - (NSBezierPath *) bezierPath;
 
+@property (readonly) NSArray* contours;
+
+- (void) debuggingInsertCrossingsForUnionWithBezierGraph:(FBBezierGraph *)otherGraph;
+- (void) debuggingInsertCrossingsForIntersectWithBezierGraph:(FBBezierGraph *)otherGraph;
+- (void) debuggingInsertCrossingsForDifferenceWithBezierGraph:(FBBezierGraph *)otherGraph;
+- (void) debuggingInsertIntersectionsWithBezierGraph:(FBBezierGraph *)otherGraph;
+- (NSBezierPath *) debugPathForContainmentOfContour:(FBBezierContour *)contour;
+- (NSBezierPath *) debugPathForJointsOfContour:(FBBezierContour *)testContour;
+
 @end

File VectorBoolean/FBBezierGraph.m

 #import "FBContourEdge.h"
 #import "FBBezierIntersection.h"
 #import "FBEdgeCrossing.h"
+#import "FBContourOverlap.h"
 #import "FBDebug.h"
 #import "Geometry.h"
 #import <math.h>
 
-//////////////////////////////////////////////////////////////////////////
-// Helper methods for angles
-//
-static const CGFloat FB2PI = 2.0 * M_PI;
 
-// Normalize the angle between 0 and 2pi
-static CGFloat NormalizeAngle(CGFloat value)
-{
-    while ( value < 0.0 )
-        value += FB2PI;
-    while ( value >= FB2PI )
-        value -= FB2PI;
-    return value;
-}
-
-// Compute the polar angle from the cartesian point
-static CGFloat PolarAngle(NSPoint point)
-{
-    CGFloat value = 0.0;
-    if ( point.x > 0.0 )
-        value = atanf(point.y / point.x);
-    else if ( point.x < 0.0 ) {
-        if ( point.y >= 0.0 )
-            value = atanf(point.y / point.x) + M_PI;
-        else
-            value = atanf(point.y / point.x) - M_PI;
-    } else {
-        if ( point.y > 0.0 )
-            value =  M_PI_2;
-        else if ( point.y < 0.0 )
-            value =  -M_PI_2;
-        else
-            value = 0.0;
-    }
-    return NormalizeAngle(value);
-}
-
-//////////////////////////////////////////////////////////////////////////
-// Angle Range structure provides a simple way to store angle ranges
-//  and determine if a specific angle falls within. 
-//
-typedef struct FBAngleRange {
-    CGFloat minimum;
-    CGFloat maximum;
-} FBAngleRange;
-
-static FBAngleRange FBAngleRangeMake(CGFloat minimum, CGFloat maximum)
-{
-    FBAngleRange range = { minimum, maximum };
-    return range;
-}
-
-static BOOL FBAngleRangeContainsAngle(FBAngleRange range, CGFloat angle)
-{
-    if ( range.minimum <= range.maximum )
-        return angle > range.minimum && angle < range.maximum;
-    
-    // The range wraps around 0. See if the angle falls in the first half
-    if ( angle > range.minimum && angle <= FB2PI )
-        return YES;
-    
-    return angle >= 0.0 && angle < range.maximum;
-}
 
 //////////////////////////////////////////////////////////////////////////
 // FBBezierGraph
 @interface FBBezierGraph ()
 
 - (void) removeDuplicateCrossings;
-- (BOOL) doesEdge:(FBContourEdge *)edge1 crossEdge:(FBContourEdge *)edge2 atIntersection:(FBBezierIntersection *)intersection;
 - (void) insertCrossingsWithBezierGraph:(FBBezierGraph *)other;
 - (FBEdgeCrossing *) firstUnprocessedCrossing;
 - (void) markCrossingsAsEntryOrExitWithBezierGraph:(FBBezierGraph *)otherGraph markInside:(BOOL)markInside;
 - (FBBezierGraph *) bezierGraphFromIntersections;
 - (void) removeCrossings;
+- (void) removeOverlaps;
+
+- (void) insertSelfCrossings;
+- (void) removeSelfCrossings;
+
+- (void) unionEquivalentNonintersectingContours:(NSMutableArray *)ourNonintersectingContours withContours:(NSMutableArray *)theirNonintersectingContours results:(NSMutableArray *)results;
+- (void) intersectEquivalentNonintersectingContours:(NSMutableArray *)ourNonintersectingContours withContours:(NSMutableArray *)theirNonintersectingContours results:(NSMutableArray *)results;
+- (void) differenceEquivalentNonintersectingContours:(NSMutableArray *)ourNonintersectingContours withContours:(NSMutableArray *)theirNonintersectingContours results:(NSMutableArray *)results;
 
 - (void) addContour:(FBBezierContour *)contour;
-- (void) round;
 - (FBContourInside) contourInsides:(FBBezierContour *)contour;
 
 - (NSArray *) nonintersectingContours;
 - (BOOL) containsContour:(FBBezierContour *)contour;
-- (FBBezierContour *) containerForContour:(FBBezierContour *)testContour;
 - (BOOL) eliminateContainers:(NSMutableArray *)containers thatDontContainContour:(FBBezierContour *)testContour usingRay:(FBBezierCurve *)ray;
 - (BOOL) findBoundsOfContour:(FBBezierContour *)testContour onRay:(FBBezierCurve *)ray minimum:(NSPoint *)testMinimum maximum:(NSPoint *)testMaximum;
 - (void) removeContoursThatDontContain:(NSMutableArray *)crossings;
 - (BOOL) findCrossingsOnContainers:(NSArray *)containers onRay:(FBBezierCurve *)ray beforeMinimum:(NSPoint)testMinimum afterMaximum:(NSPoint)testMaximum crossingsBefore:(NSMutableArray *)crossingsBeforeMinimum crossingsAfter:(NSMutableArray *)crossingsAfterMaximum;
 - (void) removeCrossings:(NSMutableArray *)crossings forContours:(NSArray *)containersToRemove;
 - (void) removeContourCrossings:(NSMutableArray *)crossings1 thatDontAppearIn:(NSMutableArray *)crossings2;
-- (NSArray *) minimumCrossings:(NSArray *)crossings onRay:(FBBezierCurve *)ray;
-- (NSArray *) maximumCrossings:(NSArray *)crossings onRay:(FBBezierCurve *)ray;
 - (NSArray *) contoursFromCrossings:(NSArray *)crossings;
 - (NSUInteger) numberOfTimesContour:(FBBezierContour *)contour appearsInCrossings:(NSArray *)crossings;
 
-@property (readonly) NSArray *contours;
+- (void) debuggingInsertCrossingsWithBezierGraph:(FBBezierGraph *)otherGraph markInside:(BOOL)markInside markOtherInside:(BOOL)markOtherInside;
+
+//@property (readonly) NSArray *contours;
 @property (readonly) NSRect bounds;
 
 @end
     if ( self != nil ) {
         // A bezier graph is made up of contours, which are closed paths of curves. Anytime we
         //  see a move to in the NSBezierPath, that's a new contour.
+		
         NSPoint lastPoint = NSZeroPoint;
+		BOOL	wasClosed = NO;
         _contours = [[NSMutableArray alloc] initWithCapacity:2];
             
         FBBezierContour *contour = nil;
             
             switch (element.kind) {
                 case NSMoveToBezierPathElement:
-                    // Start a new contour
+				{
+                    // if previous contour wasn't closed, close it
+					
+					if( !wasClosed && contour != nil )
+						[contour close];
+					
+					wasClosed = NO;
+										
+					// Start a new contour
                     contour = [[[FBBezierContour alloc] init] autorelease];
                     [self addContour:contour];
                     
                     lastPoint = element.point;
                     break;
-                    
+				}
+					
                 case NSLineToBezierPathElement: {
                     // [MO] skip degenerate line segments
                     if (!NSEqualPoints(element.point, lastPoint)) {
                 }
                     
                 case NSCurveToBezierPathElement:
-                    [contour addCurve:[FBBezierCurve bezierCurveWithEndPoint1:lastPoint controlPoint1:element.controlPoints[0] controlPoint2:element.controlPoints[1] endPoint2:element.point]];
+				{
+                    // GPC: skip degenerate case where all points are equal
+					
+					if( NSEqualPoints( element.point, lastPoint ) && NSEqualPoints( element.point, element.controlPoints[0] ) && NSEqualPoints( element.point, element.controlPoints[1] ))
+						continue;
+
+					[contour addCurve:[FBBezierCurve bezierCurveWithEndPoint1:lastPoint controlPoint1:element.controlPoints[0] controlPoint2:element.controlPoints[1] endPoint2:element.point]];
                     
                     lastPoint = element.point;
                     break;
-                    
+				}   
                 case NSClosePathBezierPathElement:
                     // [MO] attempt to close the bezier contour by
                     // mapping closepaths to equivalent lineto operations,
                         NSPoint        firstPoint = [[firstEdge curve] endPoint1];
                         
                         // Skip degenerate line segments
-                        if (!CGPointEqualToPoint(lastPoint, firstPoint)) {
+                        if (!NSEqualPoints(lastPoint, firstPoint))
+						{
                             [contour addCurve:[FBBezierCurve bezierCurveWithLineStartPoint:lastPoint endPoint:firstPoint]];
+							wasClosed = YES;
                         }
                     }
-                    lastPoint = CGPointZero;
+                    lastPoint = NSZeroPoint;
                     break;
             }
         }
-        
-        // Go through and mark each contour if its a hole or filled region
+
+		if( !wasClosed && contour != nil )
+			[contour close];
+
+		// Go through and mark each contour if its a hole or filled region
         for (contour in _contours)
             contour.inside = [self contourInsides:contour];
     }
     // First insert FBEdgeCrossings into both graphs where the graphs
     //  cross.
     [self insertCrossingsWithBezierGraph:graph];
+    [self insertSelfCrossings];
+    [graph insertSelfCrossings];
     
     // Handle the parts of the graphs that intersect first. Mark the parts
     //  of the graphs that are outside the other for the final result.
     [self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:NO];
     [graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:NO];
 
+    [self removeSelfCrossings];
+    [graph removeSelfCrossings];
+
     // Walk the crossings and actually compute the final result for the intersecting parts
     FBBezierGraph *result = [self bezierGraphFromIntersections];
-    [result round]; // decimal values make things messy, so round in case the result is used as input elsewhere, like XOR
-    
+
     // Finally, process the contours that don't cross anything else. They're either
     //  completely contained in another contour, or disjoint.
-    NSArray *ourNonintersectingContours = [self nonintersectingContours];
-    NSArray *theirNonintersectinContours = [graph nonintersectingContours];
+    NSMutableArray *ourNonintersectingContours = [[[self nonintersectingContours] mutableCopy] autorelease];
+    NSMutableArray *theirNonintersectinContours = [[[graph nonintersectingContours] mutableCopy] autorelease];
+    NSMutableArray *finalNonintersectingContours = [[ourNonintersectingContours mutableCopy] autorelease];
+    [finalNonintersectingContours addObjectsFromArray:theirNonintersectinContours];
+    [self unionEquivalentNonintersectingContours:ourNonintersectingContours withContours:theirNonintersectinContours results:finalNonintersectingContours];
+    
     // Since we're doing a union, assume all the non-crossing contours are in, and remove
     //  by exception when they're contained by another contour.
-    NSMutableArray *finalNonintersectingContours = [[ourNonintersectingContours mutableCopy] autorelease];
-    [finalNonintersectingContours addObjectsFromArray:theirNonintersectinContours];
     for (FBBezierContour *ourContour in ourNonintersectingContours) {
         // If the other graph contains our contour, it's redundant and we can just remove it
         BOOL clipContainsSubject = [graph containsContour:ourContour];
     // Append the final nonintersecting contours
     for (FBBezierContour *contour in finalNonintersectingContours)
         [result addContour:contour];
-    
+
     // Clean up crossings so the graphs can be reused, e.g. XOR will reuse graphs.
     [self removeCrossings];
     [graph removeCrossings];
-    
+    [self removeOverlaps];
+    [graph removeOverlaps];
+
     return result;
 }
 
+- (void) unionEquivalentNonintersectingContours:(NSMutableArray *)ourNonintersectingContours withContours:(NSMutableArray *)theirNonintersectingContours results:(NSMutableArray *)results
+{
+    for (NSUInteger ourIndex = 0; ourIndex < [ourNonintersectingContours count]; ourIndex++) {
+        FBBezierContour *ourContour = [ourNonintersectingContours objectAtIndex:ourIndex];
+        for (NSUInteger theirIndex = 0; theirIndex < [theirNonintersectingContours count]; theirIndex++) {
+            FBBezierContour *theirContour = [theirNonintersectingContours objectAtIndex:theirIndex];
+            
+            if ( ![ourContour isEquivalent:theirContour] )
+                continue;
+        
+            if ( ourContour.inside == theirContour.inside ) {
+                // Redundant, so just remove one of them from the results
+                [results removeObject:theirContour];
+            } else {
+                // One is a hole, one is a fill, so they cancel each other out. Remove both from the results
+                [results removeObject:theirContour];
+                [results removeObject:ourContour];
+            }
+            
+            // Remove both from the inputs so they aren't processed later
+            [theirNonintersectingContours removeObjectAtIndex:theirIndex];
+            [ourNonintersectingContours removeObjectAtIndex:ourIndex];
+            ourIndex--;
+            break;
+        }
+    }
+}
+
 - (FBBezierGraph *) intersectWithBezierGraph:(FBBezierGraph *)graph
 {
     // First insert FBEdgeCrossings into both graphs where the graphs cross.
     [self insertCrossingsWithBezierGraph:graph];
-    
+    [self insertSelfCrossings];
+    [graph insertSelfCrossings];
+
     // Handle the parts of the graphs that intersect first. Mark the parts
     //  of the graphs that are inside the other for the final result.
     [self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:YES];
     [graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:YES];
     
+    [self removeSelfCrossings];
+    [graph removeSelfCrossings];
+
     // Walk the crossings and actually compute the final result for the intersecting parts
     FBBezierGraph *result = [self bezierGraphFromIntersections];
-    [result round]; // decimal values make things messy, so round in case the result is used as input elsewhere, like XOR
     
     // Finally, process the contours that don't cross anything else. They're either
     //  completely contained in another contour, or disjoint.
-    NSArray *ourNonintersectingContours = [self nonintersectingContours];
-    NSArray *theirNonintersectinContours = [graph nonintersectingContours];
+    NSMutableArray *ourNonintersectingContours = [[[self nonintersectingContours] mutableCopy] autorelease];
+    NSMutableArray *theirNonintersectinContours = [[[graph nonintersectingContours] mutableCopy] autorelease];
+    NSMutableArray *finalNonintersectingContours = [NSMutableArray arrayWithCapacity:[ourNonintersectingContours count] + [theirNonintersectinContours count]];
+    [self intersectEquivalentNonintersectingContours:ourNonintersectingContours withContours:theirNonintersectinContours results:finalNonintersectingContours];
     // Since we're doing an intersect, assume that most of these non-crossing contours shouldn't be in
     //  the final result.
-    NSMutableArray *finalNonintersectingContours = [NSMutableArray arrayWithCapacity:[ourNonintersectingContours count] + [theirNonintersectinContours count]];
     for (FBBezierContour *ourContour in ourNonintersectingContours) {
         // If their graph contains ourContour, then the two graphs intersect (logical AND) at ourContour, so
         //  add it to the final result.
     // Clean up crossings so the graphs can be reused, e.g. XOR will reuse graphs.
     [self removeCrossings];
     [graph removeCrossings];
-    
+    [self removeOverlaps];
+    [graph removeOverlaps];
+
     return result;
 }
 
+- (void) intersectEquivalentNonintersectingContours:(NSMutableArray *)ourNonintersectingContours withContours:(NSMutableArray *)theirNonintersectingContours results:(NSMutableArray *)results
+{
+    for (NSUInteger ourIndex = 0; ourIndex < [ourNonintersectingContours count]; ourIndex++) {
+        FBBezierContour *ourContour = [ourNonintersectingContours objectAtIndex:ourIndex];
+        for (NSUInteger theirIndex = 0; theirIndex < [theirNonintersectingContours count]; theirIndex++) {
+            FBBezierContour *theirContour = [theirNonintersectingContours objectAtIndex:theirIndex];
+            
+            if ( ![ourContour isEquivalent:theirContour] )
+                continue;
+            
+            if ( ourContour.inside == theirContour.inside ) {
+                // Redundant, so just add one of them to our results
+                [results addObject:ourContour];
+            } else {
+                // One is a hole, one is a fill, so the hole cancels the fill. Add the hole to the results
+                if ( theirContour.inside == FBContourInsideHole ) {
+                    // theirContour is the hole, so add it
+                    [results addObject:theirContour];
+                } else {
+                    // ourContour is the hole, so add it
+                    [results addObject:ourContour];
+                }
+            }
+            
+            // Remove both from the inputs so they aren't processed later
+            [theirNonintersectingContours removeObjectAtIndex:theirIndex];
+            [ourNonintersectingContours removeObjectAtIndex:ourIndex];
+            ourIndex--;
+            break;
+        }
+    }
+}
+
 - (FBBezierGraph *) differenceWithBezierGraph:(FBBezierGraph *)graph
 {
     // First insert FBEdgeCrossings into both graphs where the graphs cross.
     [self insertCrossingsWithBezierGraph:graph];
-    
+    [self insertSelfCrossings];
+    [graph insertSelfCrossings];
+
     // Handle the parts of the graphs that intersect first. We're subtracting
     //  graph from outselves. Mark the outside parts of ourselves, and the inside
     //  parts of them for the final result.
     [self markCrossingsAsEntryOrExitWithBezierGraph:graph markInside:NO];
     [graph markCrossingsAsEntryOrExitWithBezierGraph:self markInside:YES];
     
+    [self removeSelfCrossings];
+    [graph removeSelfCrossings];
+
     // Walk the crossings and actually compute the final result for the intersecting parts
     FBBezierGraph *result = [self bezierGraphFromIntersections];
-    [result round]; // decimal values make things messy, so round in case the result is used as input elsewhere, like XOR
     
     // Finally, process the contours that don't cross anything else. They're either
     //  completely contained in another contour, or disjoint.
-    NSArray *ourNonintersectingContours = [self nonintersectingContours];
-    NSArray *theirNonintersectinContours = [graph nonintersectingContours];
+    NSMutableArray *ourNonintersectingContours = [[[self nonintersectingContours] mutableCopy] autorelease];
+    NSMutableArray *theirNonintersectinContours = [[[graph nonintersectingContours] mutableCopy] autorelease];
+    NSMutableArray *finalNonintersectingContours = [NSMutableArray arrayWithCapacity:[ourNonintersectingContours count] + [theirNonintersectinContours count]];
+    [self differenceEquivalentNonintersectingContours:ourNonintersectingContours withContours:theirNonintersectinContours results:finalNonintersectingContours];
+    
     // We're doing an subtraction, so assume none of the contours should be in the final result
-    NSMutableArray *finalNonintersectingContours = [NSMutableArray arrayWithCapacity:[ourNonintersectingContours count] + [theirNonintersectinContours count]];
     for (FBBezierContour *ourContour in ourNonintersectingContours) {
         // If ourContour isn't subtracted away (contained by) the other graph, it should stick around,
         //  so add it to our final result.
     // Clean up crossings so the graphs can be reused
     [self removeCrossings];
     [graph removeCrossings];
-    
+    [self removeOverlaps];
+    [graph removeOverlaps];
+
     return result;  
 }
 
+- (void) differenceEquivalentNonintersectingContours:(NSMutableArray *)ourNonintersectingContours withContours:(NSMutableArray *)theirNonintersectingContours results:(NSMutableArray *)results
+{
+    for (NSUInteger ourIndex = 0; ourIndex < [ourNonintersectingContours count]; ourIndex++) {
+        FBBezierContour *ourContour = [ourNonintersectingContours objectAtIndex:ourIndex];
+        for (NSUInteger theirIndex = 0; theirIndex < [theirNonintersectingContours count]; theirIndex++) {
+            FBBezierContour *theirContour = [theirNonintersectingContours objectAtIndex:theirIndex];
+            
+            if ( ![ourContour isEquivalent:theirContour] )
+                continue;
+            
+            if ( ourContour.inside != theirContour.inside ) {
+                // Trying to subtract a hole from a fill or vice versa does nothing, so add the original to the results
+                [results addObject:ourContour];
+            } else if ( ourContour.inside == FBContourInsideHole && theirContour.inside == FBContourInsideHole ) {
+                // Subtracting a hole from a hole is redundant, so just add one of them to the results
+                [results addObject:ourContour];
+            } else {
+                // Both are fills, and subtracting a fill from a fill removes both. So add neither to the results
+                //  Intentionally do nothing for this case.
+            }
+            
+            // Remove both from the inputs so they aren't processed later
+            [theirNonintersectingContours removeObjectAtIndex:theirIndex];
+            [ourNonintersectingContours removeObjectAtIndex:ourIndex];
+            ourIndex--;
+            break;
+        }
+    }
+}
+
 - (void) markCrossingsAsEntryOrExitWithBezierGraph:(FBBezierGraph *)otherGraph markInside:(BOOL)markInside
 {
     // Walk each contour in ourself and mark the crossings with each intersecting contour as entering
     NSBezierPath *path = [NSBezierPath bezierPath];
     [path setWindingRule:NSEvenOddWindingRule];
 
-    for (FBBezierContour *contour in _contours) {
+    for (FBBezierContour *contour in _contours) 
+	{
         BOOL firstPoint = YES;        
-        for (FBContourEdge *edge in contour.edges) {
+        for (FBContourEdge *edge in contour.edges)
+		{
             if ( firstPoint ) {
                 [path moveToPoint:edge.curve.endPoint1];
                 firstPoint = NO;
             }
             
-            [path curveToPoint:edge.curve.endPoint2 controlPoint1:edge.curve.controlPoint1 controlPoint2:edge.curve.controlPoint2];
+			if( edge.curve.isStraightLine)
+				[path lineToPoint:edge.curve.endPoint2];
+			else
+				[path curveToPoint:edge.curve.endPoint2 controlPoint1:edge.curve.controlPoint1 controlPoint2:edge.curve.controlPoint2];
         }
+		[path closePath];	// GPC: close each contour
     }
     
     return path;
 }
 
-- (void) round
-{
-    // Round off all end and control points to integral values
-    for (FBBezierContour *contour in _contours)
-        [contour round];
-}
-
 - (void) insertCrossingsWithBezierGraph:(FBBezierGraph *)other
 {
     // Find all intersections and, if they cross the other graph, create crossings for them, and insert
     //  them into each graph's edges.
     for (FBBezierContour *ourContour in self.contours) {
-        for (FBContourEdge *ourEdge in ourContour.edges) {
-            for (FBBezierContour *theirContour in other.contours) {
-                for (FBContourEdge *theirEdge in theirContour.edges) {
+        for (FBBezierContour *theirContour in other.contours) {
+            FBContourOverlap *overlap = [FBContourOverlap contourOverlap];
+
+            for (FBContourEdge *ourEdge in ourContour.edges) {
+               for (FBContourEdge *theirEdge in theirContour.edges) {
                     // Find all intersections between these two edges (curves)
-                    NSArray *intersections = [ourEdge.curve intersectionsWithBezierCurve:theirEdge.curve];
+                    FBBezierIntersectRange *intersectRange = nil;
+                    NSArray *intersections = [ourEdge.curve intersectionsWithBezierCurve:theirEdge.curve overlapRange:&intersectRange];
                     for (FBBezierIntersection *intersection in intersections) {
                         // If this intersection happens at one of the ends of the edges, then mark
                         //  that on the edge. We do this here because not all intersections create
                         //  crossings, but we still need to know when the intersections fall on end points
                         //  later on in the algorithm.
-                        if ( intersection.isAtStartOfCurve1 ) {
+                        if ( intersection.isAtStartOfCurve1 )
                             ourEdge.startShared = YES;
-                            ourEdge.previous.stopShared = YES;
-                        } else if ( intersection.isAtStopOfCurve1 ) {
-                            ourEdge.stopShared = YES;
+                        else if ( intersection.isAtStopOfCurve1 )
                             ourEdge.next.startShared = YES;
-                        }
-                        if ( intersection.isAtStartOfCurve2 ) {
+                        if ( intersection.isAtStartOfCurve2 )
                             theirEdge.startShared = YES;
-                            theirEdge.previous.stopShared = YES;
-                        } else if ( intersection.isAtStopOfCurve2 ) {
-                            theirEdge.stopShared = YES;
+                        else if ( intersection.isAtStopOfCurve2 )
                             theirEdge.next.startShared = YES;
-                        }
 
                         // Don't add a crossing unless one edge actually crosses the other
-                        if ( ![self doesEdge:ourEdge crossEdge:theirEdge atIntersection:intersection] )
+                        if ( ![ourEdge crossesEdge:theirEdge atIntersection:intersection] )
                             continue;
 
                         // Add crossings to both graphs for this intersection, and point them at each other
                         [ourEdge addCrossing:ourCrossing];
                         [theirEdge addCrossing:theirCrossing];
                     }
+                    if ( intersectRange != nil )
+                        [overlap addOverlap:intersectRange forEdge1:ourEdge edge2:theirEdge];
+                } // end theirEdges                
+            } //end ourEdges
+            
+            // At this point we've found all intersections/overlaps between ourContour and theirContour
+            
+            // Determine if the overlaps constitute crossings
+            if ( ![overlap isComplete] ) {
+                // The contours aren't equivalent so see if they're crossings
+                for (FBEdgeOverlapRun *run in overlap.runs) {
+                    if ( ![run isCrossing] ) 
+                        continue;
+                    
+                    // The two ends of the overlap run should serve as crossings
+                    [run addCrossings];
                 }
             }
             
-        }
-    }
+            [ourContour addOverlap:overlap];
+            [theirContour addOverlap:overlap];
+        } // end theirContours
+    } // end ourContours
  
     // Remove duplicate crossings that can happen at end points of edges
     [self removeDuplicateCrossings];
     }
 }
 
+- (void) insertSelfCrossings
+{
+    // Find all intersections and, if they cross other contours in this graph, create crossings for them, and insert
+    //  them into each contour's edges.
+    NSMutableArray *remainingContours = [[self.contours mutableCopy] autorelease];
+    while ( [remainingContours count] > 0 ) {
+        FBBezierContour *firstContour = [remainingContours lastObject];
+        for (FBBezierContour *secondContour in remainingContours) {
+            // We don't handle self-intersections on the contour this way, so skip them here
+            if ( firstContour == secondContour )
+                continue;
+
+            // Compare all the edges between these two contours looking for crossings
+            for (FBContourEdge *firstEdge in firstContour.edges) {
+                for (FBContourEdge *secondEdge in secondContour.edges) {
+                    // Find all intersections between these two edges (curves)
+                    NSArray *intersections = [firstEdge.curve intersectionsWithBezierCurve:secondEdge.curve];
+                    for (FBBezierIntersection *intersection in intersections) {
+                        // If this intersection happens at one of the ends of the edges, then mark
+                        //  that on the edge. We do this here because not all intersections create
+                        //  crossings, but we still need to know when the intersections fall on end points
+                        //  later on in the algorithm.
+                        if ( intersection.isAtStartOfCurve1 )
+                            firstEdge.startShared = YES;
+                        else if ( intersection.isAtStopOfCurve1 )
+                            firstEdge.next.startShared = YES;
+                        if ( intersection.isAtStartOfCurve2 )
+                            secondEdge.startShared = YES;
+                        else if ( intersection.isAtStopOfCurve2 )
+                            secondEdge.next.startShared = YES;
+                        
+                        // Don't add a crossing unless one edge actually crosses the other
+                        if ( ![firstEdge crossesEdge:secondEdge atIntersection:intersection] )
+                            continue;
+                        
+                        // Add crossings to both graphs for this intersection, and point them at each other
+                        FBEdgeCrossing *firstCrossing = [FBEdgeCrossing crossingWithIntersection:intersection];
+                        FBEdgeCrossing *secondCrossing = [FBEdgeCrossing crossingWithIntersection:intersection];
+                        firstCrossing.selfCrossing = YES;
+                        secondCrossing.selfCrossing = YES;
+                        firstCrossing.counterpart = secondCrossing;
+                        secondCrossing.counterpart = firstCrossing;
+                        [firstEdge addCrossing:firstCrossing];
+                        [secondEdge addCrossing:secondCrossing];
+                    }
+                }
+            }
+        }
+        
+        // We just compared this contour to all the others, so we don't need to do it again
+        [remainingContours removeLastObject]; // do this at the end of the loop when we're done with it
+    }
+    
+    // Remove duplicate crossings that can happen at end points of edges
+    [self removeDuplicateCrossings];
+}
+
 - (BOOL) doesEdge:(FBContourEdge *)edge1 crossEdge:(FBContourEdge *)edge2 atIntersection:(FBBezierIntersection *)intersection
 {
     // If it's tangent, then it doesn't cross
     return _bounds;
 }
 
+
 - (FBContourInside) contourInsides:(FBBezierContour *)testContour
 {
     // Determine if this contour, which should reside in this graph, is a filled region or
     
     // Create the line from the first point in the contour to outside the graph
     NSPoint testPoint = testContour.firstPoint;
+	
     NSPoint lineEndPoint = NSMakePoint(testPoint.x > NSMinX(self.bounds) ? NSMinX(self.bounds) - 10 : NSMaxX(self.bounds) + 10, testPoint.y); /* just move us outside the bounds of the graph */
     FBBezierCurve *testCurve = [FBBezierCurve bezierCurveWithLineStartPoint:testPoint endPoint:lineEndPoint];
+    FBBezierContour *testCurveContour = [FBBezierContour bezierContourWithCurve:testCurve];
+    FBContourEdge *testEdge = [testCurveContour.edges objectAtIndex:0];
 
     NSUInteger intersectCount = 0;
     for (FBBezierContour *contour in self.contours) {
         if ( contour == testContour )
-            continue; // don't test self intersections
+            continue; // don't test self intersections 
+
+        // Check for self-intersections between this contour and other contours in the same graph
+        //  If there are intersections, then don't consider the intersecting contour for the purpose
+        //  of determining if we are "filled" or a "hole"
+        BOOL intersectsWithThisContour = NO;
         for (FBContourEdge *edge in contour.edges) {
-            NSArray *intersections = [testCurve intersectionsWithBezierCurve:edge.curve];
-            for (FBBezierIntersection *intersection in intersections) {
-                if ( intersection.isTangent ) // don't count tangents
-                    continue;
-                intersectCount++;
+            for (FBContourEdge *testEdge in testContour.edges) {
+                NSArray *intersections = [testEdge.curve intersectionsWithBezierCurve:edge.curve];
+                if ( [intersections count] > 0 ) {
+                    intersectsWithThisContour = YES;
+                    break;
+                }
             }
         }
+        if ( intersectsWithThisContour )
+            continue; // skip it
+        
+        intersectCount += [contour numberOfIntersectionsWithRay:testEdge];
+    }
+    return (intersectCount & 1) == 1 ? FBContourInsideHole : FBContourInsideFilled;
+}
+
+- (NSBezierPath *) debugPathForContainmentOfContour:(FBBezierContour *)testContour
+{
+    NSBezierPath *path = [NSBezierPath bezierPath];
+    
+    // Create the line from the first point in the contour to outside the graph
+    NSPoint testPoint = testContour.firstPoint;
+	
+    NSPoint lineEndPoint = NSMakePoint(testPoint.x > NSMinX(self.bounds) ? NSMinX(self.bounds) - 10 : NSMaxX(self.bounds) + 10, testPoint.y); /* just move us outside the bounds of the graph */
+    FBBezierCurve *testCurve = [FBBezierCurve bezierCurveWithLineStartPoint:testPoint endPoint:lineEndPoint];
+    FBBezierContour *testCurveContour = [FBBezierContour bezierContourWithCurve:testCurve];
+    FBContourEdge *testEdge = [testCurveContour.edges objectAtIndex:0];
+
+    NSUInteger intersectCount = 0;
+    for (FBBezierContour *contour in self.contours) {
+        if ( contour == testContour )
+            continue; // don't test self intersections 
+