Commits

Anonymous committed 52c313e

Many bug fixes and numerous performance enhancements. This work was funded by the fine folks at Bohemian Coding (http://http://www.bohemiancoding.com/), makers of Sketch.

Comments (0)

Files changed (23)

VectorBoolean.xcodeproj/project.pbxproj

 		A192AB59139D8D6000AF40BA /* FBGeometry.m in Sources */ = {isa = PBXBuildFile; fileRef = A192AB58139D8D6000AF40BA /* FBGeometry.m */; };
 		A1A3D0A713A9BCBA00678AA9 /* FBBezierGraph.m in Sources */ = {isa = PBXBuildFile; fileRef = A1A3D0A613A9BCB900678AA9 /* FBBezierGraph.m */; };
 		A1A3D0AB13A9CE1200678AA9 /* FBBezierContour.m in Sources */ = {isa = PBXBuildFile; fileRef = A1A3D0AA13A9CE0F00678AA9 /* FBBezierContour.m */; };
-		A1A3D0AE13A9CE3D00678AA9 /* FBContourEdge.m in Sources */ = {isa = PBXBuildFile; fileRef = A1A3D0AD13A9CE3B00678AA9 /* FBContourEdge.m */; };
 		A1A3D0B113A9CE5400678AA9 /* FBEdgeCrossing.m in Sources */ = {isa = PBXBuildFile; fileRef = A1A3D0B013A9CE5200678AA9 /* FBEdgeCrossing.m */; };
 		A1A3D0B413AC0F3600678AA9 /* FBDebug.m in Sources */ = {isa = PBXBuildFile; fileRef = A1A3D0B313AC0F3100678AA9 /* FBDebug.m */; };
 		A1C48B381395FA380043E2C7 /* Cocoa.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = A1C48B371395FA380043E2C7 /* Cocoa.framework */; };
 		A1C48B621395FAE20043E2C7 /* NSBezierPath+Utilities.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B5E1395FAE20043E2C7 /* NSBezierPath+Utilities.m */; };
 		A1C48B65139602480043E2C7 /* CanvasView.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B64139602480043E2C7 /* CanvasView.m */; };
 		A1C48B68139602820043E2C7 /* Canvas.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B67139602810043E2C7 /* Canvas.m */; };
+		A1DFCC6E1892EB950026A403 /* FBBezierCurve+Edge.m in Sources */ = {isa = PBXBuildFile; fileRef = A1DFCC6B1892EB950026A403 /* FBBezierCurve+Edge.m */; };
+		A1DFCC6F1892EB950026A403 /* FBCurveLocation.m in Sources */ = {isa = PBXBuildFile; fileRef = A1DFCC6D1892EB950026A403 /* FBCurveLocation.m */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXFileReference section */
 		A1A3D0A613A9BCB900678AA9 /* FBBezierGraph.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBBezierGraph.m; sourceTree = "<group>"; };
 		A1A3D0A913A9CE0E00678AA9 /* FBBezierContour.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBBezierContour.h; sourceTree = "<group>"; };
 		A1A3D0AA13A9CE0F00678AA9 /* FBBezierContour.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBBezierContour.m; sourceTree = "<group>"; };
-		A1A3D0AC13A9CE3B00678AA9 /* FBContourEdge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBContourEdge.h; sourceTree = "<group>"; };
-		A1A3D0AD13A9CE3B00678AA9 /* FBContourEdge.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBContourEdge.m; sourceTree = "<group>"; };
 		A1A3D0AF13A9CE5100678AA9 /* FBEdgeCrossing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBEdgeCrossing.h; sourceTree = "<group>"; };
 		A1A3D0B013A9CE5200678AA9 /* FBEdgeCrossing.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBEdgeCrossing.m; sourceTree = "<group>"; };
 		A1A3D0B213AC0F2F00678AA9 /* FBDebug.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBDebug.h; sourceTree = "<group>"; };
 		A1C48B64139602480043E2C7 /* CanvasView.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = CanvasView.m; sourceTree = "<group>"; };
 		A1C48B66139602800043E2C7 /* Canvas.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Canvas.h; sourceTree = "<group>"; };
 		A1C48B67139602810043E2C7 /* Canvas.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = Canvas.m; sourceTree = "<group>"; };
+		A1DFCC6A1892EB950026A403 /* FBBezierCurve+Edge.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "FBBezierCurve+Edge.h"; sourceTree = "<group>"; };
+		A1DFCC6B1892EB950026A403 /* FBBezierCurve+Edge.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "FBBezierCurve+Edge.m"; sourceTree = "<group>"; };
+		A1DFCC6C1892EB950026A403 /* FBCurveLocation.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = FBCurveLocation.h; sourceTree = "<group>"; };
+		A1DFCC6D1892EB950026A403 /* FBCurveLocation.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FBCurveLocation.m; sourceTree = "<group>"; };
 /* End PBXFileReference section */
 
 /* Begin PBXFrameworksBuildPhase section */
 				A1A3D0A613A9BCB900678AA9 /* FBBezierGraph.m */,
 				A1A3D0A913A9CE0E00678AA9 /* FBBezierContour.h */,
 				A1A3D0AA13A9CE0F00678AA9 /* FBBezierContour.m */,
-				A1A3D0AC13A9CE3B00678AA9 /* FBContourEdge.h */,
-				A1A3D0AD13A9CE3B00678AA9 /* FBContourEdge.m */,
 				A1A3D0AF13A9CE5100678AA9 /* FBEdgeCrossing.h */,
 				A1A3D0B013A9CE5200678AA9 /* FBEdgeCrossing.m */,
 				A1A3D0B213AC0F2F00678AA9 /* FBDebug.h */,
 				A1A3D0B313AC0F3100678AA9 /* FBDebug.m */,
+				A1DFCC6A1892EB950026A403 /* FBBezierCurve+Edge.h */,
+				A1DFCC6B1892EB950026A403 /* FBBezierCurve+Edge.m */,
+				A1DFCC6C1892EB950026A403 /* FBCurveLocation.h */,
+				A1DFCC6D1892EB950026A403 /* FBCurveLocation.m */,
 				A1C48B4C1395FA390043E2C7 /* MyDocument.xib */,
 				A1C48B4F1395FA390043E2C7 /* MainMenu.xib */,
 				A1C48B3E1395FA390043E2C7 /* Supporting Files */,
 			isa = PBXSourcesBuildPhase;
 			buildActionMask = 2147483647;
 			files = (
+				A1DFCC6E1892EB950026A403 /* FBBezierCurve+Edge.m in Sources */,
 				A1C48B451395FA390043E2C7 /* main.m in Sources */,
 				A1C48B4B1395FA390043E2C7 /* MyDocument.m in Sources */,
 				A1C48B621395FAE20043E2C7 /* NSBezierPath+Utilities.m in Sources */,
 				A192AB59139D8D6000AF40BA /* FBGeometry.m in Sources */,
 				A1A3D0A713A9BCBA00678AA9 /* FBBezierGraph.m in Sources */,
 				A1A3D0AB13A9CE1200678AA9 /* FBBezierContour.m in Sources */,
-				A1A3D0AE13A9CE3D00678AA9 /* FBContourEdge.m in Sources */,
 				A1A3D0B113A9CE5400678AA9 /* FBEdgeCrossing.m in Sources */,
+				A1DFCC6F1892EB950026A403 /* FBCurveLocation.m in Sources */,
 				A1A3D0B413AC0F3600678AA9 /* FBDebug.m in Sources */,
 				A106B9711737496A00697FF3 /* FBBezierIntersectRange.m in Sources */,
 				A106B9721737496A00697FF3 /* FBContourOverlap.m in Sources */,

VectorBoolean/Canvas.m

         
         for (FBBezierCurve *curve1 in curves1) {
             for (FBBezierCurve *curve2 in curves2) {
-                NSArray *intersections = [curve1 intersectionsWithBezierCurve:curve2];
-                for (FBBezierIntersection *intersection in intersections) {
+                [curve1 intersectionsWithBezierCurve:curve2 overlapRange:nil withBlock:^(FBBezierIntersection *intersection, BOOL *stop) {
                     if ( intersection.isTangent )
                         [[NSColor purpleColor] set];
                     else
                         [[NSColor greenColor] set];
                     NSBezierPath *circle = [NSBezierPath bezierPathWithOvalInRect:BoxFrame(intersection.location)];
                     [circle stroke];
-                }
+                }];
             }
         }
     }

VectorBoolean/FBBezierContour.h

 
 @class FBBezierCurve;
 @class FBEdgeCrossing;
-@class FBContourEdge;
 @class FBContourOverlap;
+@class FBCurveLocation;
+@class FBEdgeOverlap;
+@class FBBezierIntersection;
 
 typedef enum FBContourInside {
     FBContourInsideFilled,
 @interface FBBezierContour : NSObject<NSCopying> {
     NSMutableArray*	_edges;
     NSRect			_bounds;
+    NSRect          _boundingRect;
     FBContourInside _inside;
     NSMutableArray  *_overlaps;
 	NSBezierPath*	_bezPathCache;	// GPC: added
 - (void) addReverseCurve:(FBBezierCurve *)curve;
 - (void) addReverseCurveFrom:(FBEdgeCrossing *)startCrossing to:(FBEdgeCrossing *)endCrossing;
 
-- (NSArray *) intersectionsWithRay:(FBContourEdge *)testEdge;
-- (NSUInteger) numberOfIntersectionsWithRay:(FBContourEdge *)testEdge;
+- (void) intersectionsWithRay:(FBBezierCurve *)testEdge withBlock:(void (^)(FBBezierIntersection *intersection))block;
+- (NSUInteger) numberOfIntersectionsWithRay:(FBBezierCurve *)testEdge;
 - (BOOL) containsPoint:(NSPoint)point;
 - (void) markCrossingsAsEntryOrExitWithContour:(FBBezierContour *)otherContour markInside:(BOOL)markInside;
 
 - (void) removeAllOverlaps;
 - (BOOL) isEquivalent:(FBBezierContour *)other;
 
+- (FBBezierCurve *) startEdge;
+- (NSPoint) testPointForContainment;
+
+- (FBCurveLocation *) closestLocationToPoint:(NSPoint)point;
+
 @property (readonly) NSArray *edges;
 @property (readonly) NSRect bounds;
+@property (readonly) NSRect boundingRect;
 @property (readonly) NSPoint firstPoint;
 @property FBContourInside inside;
 @property (readonly) NSArray *intersectingContours;
 
+- (BOOL) crossesOwnContour:(FBBezierContour *)contour;
 
 - (NSBezierPath*) debugPathForIntersectionType:(NSInteger) ti;
 
+- (void) forEachEdgeOverlapDo:(void (^)(FBEdgeOverlap *overlap))block;
+- (BOOL) doesOverlapContainCrossing:(FBEdgeCrossing *)crossing;
+- (BOOL) doesOverlapContainParameter:(CGFloat)parameter onEdge:(FBBezierCurve *)edge;
+
 @end

VectorBoolean/FBBezierContour.m

 
 #import "FBBezierContour.h"
 #import "FBBezierCurve.h"
-#import "FBContourEdge.h"
+#import "FBBezierCurve+Edge.h"
 #import "FBEdgeCrossing.h"
 #import "FBContourOverlap.h"
 #import "FBDebug.h"
 #import "FBGeometry.h"
 #import "FBBezierIntersection.h"
 #import "NSBezierPath+Utilities.h"
+#import "FBCurveLocation.h"
+#import "FBBezierIntersectRange.h"
 
 @interface FBBezierContour ()
 
-- (FBContourEdge *) startEdge;
 - (BOOL) contourAndSelfIntersectingContoursContainPoint:(NSPoint)point;
 - (void) addSelfIntersectingContoursToArray:(NSMutableArray *)contours originalContour:(FBBezierContour *)originalContour;
 
 @property (readonly) NSArray *selfIntersectingContours;
 
+- (void) startingEdge:(FBBezierCurve **)outEdge parameter:(CGFloat *)outParameter point:(NSPoint *)outPoint;
+- (BOOL) markCrossingsOnEdge:(FBBezierCurve *)edge startParameter:(CGFloat)startParameter stopParameter:(CGFloat)stopParameter otherContours:(NSArray *)otherContours isEntry:(BOOL)startIsEntry;
+
+@property (readonly) NSMutableArray *overlaps_;
+
 @end
 
 @implementation FBBezierContour
     self = [super init];
     if ( self != nil ) {
         _edges = [[NSMutableArray alloc] initWithCapacity:12];
-        _overlaps = [[NSMutableArray alloc] initWithCapacity:12];
     }
     
     return self;
     [super dealloc];
 }
 
+- (NSMutableArray *) overlaps_
+{
+    if ( _overlaps == nil )
+        _overlaps = [[NSMutableArray alloc] initWithCapacity:12];
+    return _overlaps;
+}
+
 - (void) addCurve:(FBBezierCurve *)curve
 {
     // Add the curve by wrapping it in an edge
     if ( curve == nil )
         return;
-    FBContourEdge *edge = [[[FBContourEdge alloc] initWithBezierCurve:curve contour:self] autorelease];
-    edge.index = [_edges count];
-    [_edges addObject:edge];
+    curve.contour = self;
+    curve.index = [_edges count];
+    [_edges addObject:curve];
     _bounds = NSZeroRect; // force the bounds to be recalculated
+    _boundingRect = NSZeroRect;
 	[_bezPathCache release];
 	_bezPathCache = nil;
 }
         return NSZeroRect;
     
     NSRect totalBounds = NSZeroRect;    
-    for (FBContourEdge *edge in _edges) {
-        NSRect bounds = edge.curve.bounds;
+    for (FBBezierCurve *edge in _edges) {
+        NSRect bounds = edge.bounds;
         if ( NSEqualRects(totalBounds, NSZeroRect) )
             totalBounds = bounds;
         else
     return _bounds;
 }
 
+- (NSRect) boundingRect
+{
+    // Cache the bounds to save time
+    if ( !NSEqualRects(_boundingRect, NSZeroRect) )
+        return _boundingRect;
+    
+    // If no edges, no bounds
+    if ( [_edges count] == 0 )
+        return NSZeroRect;
+    
+    NSRect totalBounds = NSZeroRect;
+    for (FBBezierCurve *edge in _edges) {
+        NSRect bounds = edge.boundingRect;
+        if ( NSEqualRects(totalBounds, NSZeroRect) )
+            totalBounds = bounds;
+        else
+            totalBounds = FBUnionRect(totalBounds, bounds);
+    }
+    
+    _boundingRect = totalBounds;
+    
+    return _boundingRect;
+}
+
 - (NSPoint) firstPoint
 {
     if ( [_edges count] == 0 )
         return NSZeroPoint;
 
-    FBContourEdge *edge = [_edges objectAtIndex:0];
-    return edge.curve.endPoint1;
+    FBBezierCurve *edge = [_edges objectAtIndex:0];
+    return edge.endPoint1;
 }
 
 - (BOOL) containsPoint:(NSPoint)testPoint
 {
+    if ( !NSPointInRect(testPoint, self.boundingRect) || !NSPointInRect(testPoint, self.bounds) )
+        return NO;
+    
 	// 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 = [self numberOfIntersectionsWithRay:testEdge];
+    NSUInteger intersectCount = [self numberOfIntersectionsWithRay:testCurve];
     return (intersectCount & 1) == 1;
 }
 
-- (NSUInteger) numberOfIntersectionsWithRay:(FBContourEdge *)testEdge
+- (NSUInteger) numberOfIntersectionsWithRay:(FBBezierCurve *)testEdge
 {
-    return [[self intersectionsWithRay:testEdge] count];
+    __block NSUInteger count = 0;
+    [self intersectionsWithRay:testEdge withBlock:^(FBBezierIntersection *intersection) {
+        count++;
+    }];
+    return count;
 }
 
-- (NSArray *) intersectionsWithRay:(FBContourEdge *)testEdge
+- (void) intersectionsWithRay:(FBBezierCurve *)testEdge withBlock:(void (^)(FBBezierIntersection *intersection))block
+
 {
-    FBBezierCurve *testCurve = testEdge.curve;
-    NSMutableArray *allIntersections = [NSMutableArray array];
+    __block FBBezierIntersection *firstIntersection = nil;
+    __block FBBezierIntersection *previousIntersection = nil;
     
     // Count how many times we intersect with this particular contour
-    for (FBContourEdge *edge in _edges) {
+    for (FBBezierCurve *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) {
+        FBBezierIntersectRange *intersectRange = nil;
+        [testEdge intersectionsWithBezierCurve:edge overlapRange:&intersectRange withBlock:^(FBBezierIntersection *intersection, BOOL *stop) {
             // Make sure this is a proper crossing
-            if ( ![testEdge crossesEdge:edge atIntersection:intersection] ) // don't count tangents
-                continue;
+            if ( ![testEdge crossesEdge:edge atIntersection:intersection] || edge.isPoint ) // don't count tangents
+                return;
             
             // 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;                
+            if ( intersection.isAtStartOfCurve2 && previousIntersection != nil ) {
+                FBBezierCurve *previousEdge = edge.previous;
+                if ( previousIntersection.isAtEndPointOfCurve2 && previousEdge == previousIntersection.curve2 )
+                    return;
+            } else if ( intersection.isAtEndPointOfCurve2 && firstIntersection != nil ) {
+                FBBezierCurve *nextEdge = edge.next;
+                if ( firstIntersection.isAtStartOfCurve2 && nextEdge == firstIntersection.curve2 )
+                    return;
             }
             
-            [allIntersections addObject:intersection];
-        }            
+            block(intersection);
+            if ( firstIntersection == nil )
+                firstIntersection = intersection;
+            previousIntersection = intersection;
+        }];
+        if ( intersectRange != nil && [testEdge crossesEdge:edge atIntersectRange:intersectRange] ) {
+            block([intersectRange middleIntersection]);
+        }
     }
-    return allIntersections;
 }
 
-- (FBContourEdge *) startEdge
+- (FBBezierCurve *) 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
     if ( [self.edges count] == 0 )
         return nil;
     
-    FBContourEdge *startEdge = [self.edges objectAtIndex:0];
-    FBContourEdge *stopValue = startEdge;
+    FBBezierCurve *startEdge = [self.edges objectAtIndex:0];
+    FBBezierCurve *stopValue = startEdge;
     while ( startEdge.isStartShared ) {
         startEdge = startEdge.next;
         if ( startEdge == stopValue )
     return startEdge;
 }
 
+- (NSPoint) testPointForContainment
+{
+    // Start with the startEdge, and if it's not shared (overlapping) then use its first point
+    FBBezierCurve *testEdge = self.startEdge;
+    if ( !testEdge.isStartShared )
+        return testEdge.endPoint1;
+    
+    // At this point we know that all the end points defining this contour are shared. We'll
+    //  need to somewhat arbitrarily pick a point on an edge that's not overlapping
+    FBBezierCurve *stopValue = testEdge;
+    CGFloat parameter = 0.5;
+    while ( [self doesOverlapContainParameter:parameter onEdge:testEdge] ) {
+        testEdge = testEdge.next;
+        if ( testEdge == stopValue )
+            break; // for safety. But if we're here, we could be hosed
+    }
+
+    return [testEdge pointAtParameter:parameter leftBezierCurve:nil rightBezierCurve:nil];
+}
+
+- (void) startingEdge:(FBBezierCurve **)outEdge parameter:(CGFloat *)outParameter point:(NSPoint *)outPoint
+{
+    // Start with the startEdge, and if it's not shared (overlapping) then use its first point
+    FBBezierCurve *testEdge = self.startEdge;
+    if ( !testEdge.isStartShared ) {
+        *outEdge = testEdge;
+        *outParameter = 0.0;
+        *outPoint = testEdge.endPoint1;
+        return;
+    }
+    
+    // At this point we know that all the end points defining this contour are shared. We'll
+    //  need to somewhat arbitrarily pick a point on an edge that's not overlapping
+    FBBezierCurve *stopValue = testEdge;
+    CGFloat parameter = 0.5;
+    while ( [self doesOverlapContainParameter:parameter onEdge:testEdge] ) {
+        testEdge = testEdge.next;
+        if ( testEdge == stopValue )
+            break; // for safety. But if we're here, we could be hosed
+    }
+
+    *outEdge = testEdge;
+    *outParameter = parameter;
+    *outPoint = [testEdge pointAtParameter:parameter leftBezierCurve:nil rightBezierCurve:nil];
+}
+
 - (void) markCrossingsAsEntryOrExitWithContour:(FBBezierContour *)otherContour markInside:(BOOL)markInside
 {
     // Go through and mark all the crossings with the given contour as "entry" or "exit". This 
     // 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 startEdge];
-    NSPoint startPoint = startEdge.curve.endPoint1;
-        
+    FBBezierCurve *startEdge = nil;
+    NSPoint startPoint = NSZeroPoint;
+    CGFloat startParameter = 0.0;
+    [self startingEdge:&startEdge parameter:&startParameter point:&startPoint];
+    
     // 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 contourAndSelfIntersectingContoursContainPoint:startPoint];
     BOOL isEntry = markInside ? !contains : contains;
     NSArray *otherContours = [otherContour.selfIntersectingContours arrayByAddingObject:otherContour];
     
+    static const CGFloat FBStopParameterNoLimit = 2.0; // needs to be > 1.0
+    static const CGFloat FBStartParameterNoLimit = 0.0;
+    
     // Walk all the edges in this contour and mark the crossings
-    FBContourEdge *edge = startEdge;
-    do {
-        // Mark all the crossings on this edge
-        for (FBEdgeCrossing *crossing in edge.crossings) {
-            // skip over other contours
-            if ( crossing.isSelfCrossing || ![otherContours containsObject:crossing.counterpart.edge.contour] )
-                continue;
-            crossing.entry = isEntry;
-            isEntry = !isEntry; // toggle.
-        }
-        
+    isEntry = [self markCrossingsOnEdge:startEdge startParameter:startParameter stopParameter:FBStopParameterNoLimit otherContours:otherContours isEntry:isEntry];
+    FBBezierCurve *edge = startEdge.next;
+    while ( edge != startEdge ) {
+        isEntry = [self markCrossingsOnEdge:edge startParameter:FBStartParameterNoLimit stopParameter:FBStopParameterNoLimit otherContours:otherContours isEntry:isEntry];
         edge = edge.next;
-    } while ( edge != startEdge );
+    }
+    [self markCrossingsOnEdge:startEdge startParameter:FBStartParameterNoLimit stopParameter:startParameter otherContours:otherContours isEntry:isEntry];
+}
+
+- (BOOL) markCrossingsOnEdge:(FBBezierCurve *)edge startParameter:(CGFloat)startParameter stopParameter:(CGFloat)stopParameter otherContours:(NSArray *)otherContours isEntry:(BOOL)startIsEntry
+{
+    __block BOOL isEntry = startIsEntry;
+    // Mark all the crossings on this edge
+    [edge crossingsWithBlock:^(FBEdgeCrossing *crossing, BOOL *stop) {
+        // skip over other contours
+        if ( crossing.isSelfCrossing || ![otherContours containsObject:crossing.counterpart.edge.contour] )
+            return;
+        if ( crossing.parameter < startParameter || crossing.parameter >= stopParameter )
+            return;
+        crossing.entry = isEntry;
+        isEntry = !isEntry; // toggle.
+    }];
+    return isEntry;
 }
 
 - (BOOL) contourAndSelfIntersectingContoursContainPoint:(NSPoint)point
 		NSBezierPath* path = [NSBezierPath bezierPath];
 		BOOL firstPoint = YES;        
 		
-		for ( FBContourEdge *edge in self.edges ) {
+		for ( FBBezierCurve *edge in self.edges ) {
 			if ( firstPoint ) {
-				[path moveToPoint:edge.curve.endPoint1];
+				[path moveToPoint:edge.endPoint1];
 				firstPoint = NO;
 			}
 			
-			if ( edge.curve.isStraightLine )
-				[path lineToPoint:edge.curve.endPoint2];
+			if ( edge.isStraightLine )
+				[path lineToPoint:edge.endPoint2];
 			else
-				[path curveToPoint:edge.curve.endPoint2 controlPoint1:edge.curve.controlPoint1 controlPoint2:edge.curve.controlPoint2];
+				[path curveToPoint:edge.endPoint2 controlPoint1:edge.controlPoint1 controlPoint2:edge.controlPoint2];
 		}
 		
 		[path closePath];
 	if ( [_edges count] == 0 )
         return;
     
-    FBContourEdge *first = [_edges objectAtIndex:0];
-    FBContourEdge *last = [_edges lastObject];
+    FBBezierCurve *first = [_edges objectAtIndex:0];
+    FBBezierCurve *last = [_edges lastObject];
     
-    if ( !FBArePointsClose(first.curve.endPoint1, last.curve.endPoint2) )
-        [self addCurve:[FBBezierCurve bezierCurveWithLineStartPoint:last.curve.endPoint2 endPoint:first.curve.endPoint1]];
+    if ( !FBArePointsClose(first.endPoint1, last.endPoint2) )
+        [self addCurve:[FBBezierCurve bezierCurveWithLineStartPoint:last.endPoint2 endPoint:first.endPoint1]];
 }
 
 
 {
 	FBBezierContour *revContour = [[[self class] alloc] init];
 	
-	for ( FBContourEdge *edge in _edges )
-		[revContour addReverseCurve:edge.curve];
+	for ( FBBezierCurve *edge in _edges )
+		[revContour addReverseCurve:edge];
 	
 	return [revContour autorelease];
 }
 	BOOL firstPoint = YES;
 	CGFloat	a = 0.0;
 	
-	for ( FBContourEdge* edge in _edges ) {
+	for ( FBBezierCurve* edge in _edges ) {
 		if ( firstPoint ) {
-			lastPoint = edge.curve.endPoint1;
+			lastPoint = edge.endPoint1;
 			firstPoint = NO;
 		} else {
-			currentPoint = edge.curve.endPoint2;
+			currentPoint = edge.endPoint2;
 			a += ((lastPoint.x * currentPoint.y) - (currentPoint.x * lastPoint.y));
 			lastPoint = currentPoint;
 		}
     return [self reversedContour];
 }
 
+- (BOOL) crossesOwnContour:(FBBezierContour *)contour
+{
+    for (FBBezierCurve *edge in _edges) {
+        __block BOOL intersects = NO;
+        [edge crossingsWithBlock:^(FBEdgeCrossing *crossing, BOOL *stop) {
+            if ( !crossing.isSelfCrossing )
+                return; // Only want the self intersecting crossings
+            FBBezierCurve *intersectingEdge = crossing.counterpart.edge;
+            if ( intersectingEdge.contour == contour ) {
+                intersects = YES;
+                *stop = YES;
+            }
+        }];
+        if ( intersects )
+            return YES;
+    }
+    return NO;
+}
 
 - (NSArray *) intersectingContours
 {
     // Go and find all the unique contours that intersect this specific contour
     NSMutableArray *contours = [NSMutableArray arrayWithCapacity:3];
-    for (FBContourEdge *edge in _edges) {
-        NSArray *intersectingEdges = edge.intersectingEdges;
-        for (FBContourEdge *intersectingEdge in intersectingEdges) {
+    for (FBBezierCurve *edge in _edges) {
+        [edge intersectingEdgesWithBlock:^(FBBezierCurve *intersectingEdge) {
             if ( ![contours containsObject:intersectingEdge.contour] )
                 [contours addObject:intersectingEdge.contour];
-        }
+        }];
     }
     return contours;
 }
 
 - (void) addSelfIntersectingContoursToArray:(NSMutableArray *)contours originalContour:(FBBezierContour *)originalContour
 {
-    for (FBContourEdge *edge in _edges) {
-        NSArray *intersectingEdges = edge.selfIntersectingEdges;
-        for (FBContourEdge *intersectingEdge in intersectingEdges) {
+    for (FBBezierCurve *edge in _edges) {
+        [edge selfIntersectingEdgesWithBlock:^(FBBezierCurve *intersectingEdge) {
             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];
+    if ( [overlap isEmpty] )
+        return;
+    
+    [self.overlaps_ addObject:overlap];
 }
 
 - (void) removeAllOverlaps
 {
+    if ( _overlaps == nil )
+        return;
+    
     [_overlaps removeAllObjects];
 }
 
 - (BOOL) isEquivalent:(FBBezierContour *)other
 {
+    if ( _overlaps == nil )
+        return NO;
+    
     for (FBContourOverlap *overlap in _overlaps) {
         if ( [overlap isBetweenContour:self andContour:other] && [overlap isComplete] )
             return YES;
     return NO;
 }
 
+- (void) forEachEdgeOverlapDo:(void (^)(FBEdgeOverlap *overlap))block
+{
+    if ( _overlaps == nil )
+        return;
+
+    for (FBContourOverlap *overlap in _overlaps) {
+        [overlap runsWithBlock:^(FBEdgeOverlapRun *run, BOOL *stop) {
+            for (FBEdgeOverlap *edgeOverlap in run.overlaps)
+                block(edgeOverlap);
+        }];
+    }
+}
+
+- (BOOL) doesOverlapContainCrossing:(FBEdgeCrossing *)crossing
+{
+    if ( _overlaps == nil )
+        return NO;
+
+    for (FBContourOverlap *overlap in _overlaps) {
+        if ( [overlap doesContainCrossing:crossing] )
+            return YES;
+    }
+    return NO;
+}
+
+- (BOOL) doesOverlapContainParameter:(CGFloat)parameter onEdge:(FBBezierCurve *)edge
+{
+    if ( _overlaps == nil )
+        return NO;
+
+    for (FBContourOverlap *overlap in _overlaps) {
+        if ( [overlap doesContainParameter:parameter onEdge:edge] )
+            return YES;
+    }
+    return NO;    
+}
+
 - (id)copyWithZone:(NSZone *)zone
 {
     FBBezierContour *copy = [[FBBezierContour allocWithZone:zone] init];
-    for (FBContourEdge *edge in _edges)
-        [copy addCurve:edge.curve];
+    for (FBBezierCurve *edge in _edges)
+        [copy addCurve:edge];
     return copy;
 }
 
+- (FBCurveLocation *) closestLocationToPoint:(NSPoint)point
+{
+    FBBezierCurve *closestEdge = nil;
+    FBBezierCurveLocation location = {};
+    
+    for (FBBezierCurve *edge in _edges) {
+        FBBezierCurveLocation edgeLocation = [edge closestLocationToPoint:point];
+        if ( closestEdge == nil || edgeLocation.distance < location.distance ) {
+            closestEdge = edge;
+            location = edgeLocation;
+        }
+    }
+    
+    if ( closestEdge == nil )
+        return nil;
+    
+    FBCurveLocation *curveLocation = [FBCurveLocation curveLocationWithEdge:closestEdge parameter:location.parameter distance:location.distance];
+    curveLocation.contour = self;
+    return curveLocation;
+}
+
 - (NSString *) description
 {
     return [NSString stringWithFormat:@"<%@: bounds = (%f, %f)(%f, %f) edges = %@>", 
 	
 	NSBezierPath *path = [NSBezierPath bezierPath];
 	
-	for ( FBContourEdge* edge in _edges ) {
-		for ( FBEdgeCrossing* crossing in [edge crossings] ) {
+	for ( FBBezierCurve* edge in _edges ) {
+        [edge crossingsWithBlock:^(FBEdgeCrossing *crossing, BOOL *stop) {
 			switch ( itersectionType ) {
 				default:	// match any
 					break;
-				
+                    
 				case 1:		// looking for entries
 					if ( !crossing.isEntry )
-						continue;
+						return;
 					break;
 					
 				case 2:		// looking for exits
 					if ( crossing.isEntry )
-						continue;
+						return;
 					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]];
+    FBBezierCurve *startEdge = [self startEdge];
+    NSPoint startEdgeTangent = FBNormalizePoint(FBSubtractPoint(startEdge.controlPoint1, startEdge.endPoint1));
+    [path appendBezierPath:[NSBezierPath triangleAtPoint:startEdge.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]];

VectorBoolean/FBBezierCurve+Edge.h

+//
+//  FBBezierCurve+Edge.h
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 7/3/13.
+//  Copyright (c) 2013 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "FBBezierCurve.h"
+
+@class FBEdgeCrossing, FBBezierIntersection, FBBezierIntersectRange;
+
+@interface FBBezierCurve (Edge)
+
+@property (assign) FBBezierContour *contour;
+@property NSUInteger index;
+
+// An easy way to iterate all the edges. Wraps around.
+@property (readonly) FBBezierCurve *next;
+@property (readonly) FBBezierCurve *previous;
+@property (readonly) FBBezierCurve *nextNonpoint;
+@property (readonly) FBBezierCurve *previousNonpoint;
+
+@property (readonly) FBEdgeCrossing *firstCrossing;
+@property (readonly) FBEdgeCrossing *lastCrossing;
+
+@property (readonly) BOOL hasCrossings;
+
+@property (readonly) FBEdgeCrossing *firstNonselfCrossing;
+@property (readonly) FBEdgeCrossing *lastNonselfCrossing;
+
+@property (readonly) BOOL hasNonselfCrossings;
+
+- (void) crossingsWithBlock:(void (^)(FBEdgeCrossing *crossing, BOOL *stop))block;
+- (void) crossingsCopyWithBlock:(void (^)(FBEdgeCrossing *crossing, BOOL *stop))block;
+
+- (FBEdgeCrossing *) nextCrossing:(FBEdgeCrossing *)crossing;
+- (FBEdgeCrossing *) previousCrossing:(FBEdgeCrossing *)crossing;
+
+
+- (void) intersectingEdgesWithBlock:(void (^)(FBBezierCurve *intersectingEdge))block;
+- (void) selfIntersectingEdgesWithBlock:(void (^)(FBBezierCurve *intersectingEdge))block;
+
+// Store if there are any intersections at either end of this edge.
+@property (getter = isStartShared) BOOL startShared;
+
+- (void) addCrossing:(FBEdgeCrossing *)crossing;
+- (void) removeCrossing:(FBEdgeCrossing *)crossing;
+- (void) removeAllCrossings;
+
+- (BOOL) crossesEdge:(FBBezierCurve *)edge2 atIntersection:(FBBezierIntersection *)intersection;
+- (BOOL) crossesEdge:(FBBezierCurve *)edge2 atIntersectRange:(FBBezierIntersectRange *)intersectRange;
+
+@end

VectorBoolean/FBBezierCurve+Edge.m

+//
+//  FBBezierCurve+Edge.m
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 7/3/13.
+//  Copyright (c) 2013 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "FBBezierCurve+Edge.h"
+#import "FBEdgeCrossing.h"
+#import "FBBezierContour.h"
+#import "FBBezierIntersection.h"
+#import "FBBezierIntersectRange.h"
+#import "FBBezierCurve.h"
+#import "FBGeometry.h"
+#import "FBDebug.h"
+
+static void FBFindEdge1TangentCurves(FBBezierCurve *edge, FBBezierIntersection *intersection, FBBezierCurve** leftCurve, FBBezierCurve **rightCurve)
+{
+    if ( intersection.isAtStartOfCurve1 ) {
+        *leftCurve = edge.previousNonpoint;
+        *rightCurve = edge;
+    } else if ( intersection.isAtStopOfCurve1 ) {
+        *leftCurve = edge;
+        *rightCurve = edge.nextNonpoint;
+    } else {
+        *leftCurve = intersection.curve1LeftBezier;
+        *rightCurve = intersection.curve1RightBezier;
+    }
+}
+
+static void FBFindEdge2TangentCurves(FBBezierCurve *edge, FBBezierIntersection *intersection, FBBezierCurve** leftCurve, FBBezierCurve **rightCurve)
+{
+    if ( intersection.isAtStartOfCurve2 ) {
+        *leftCurve = edge.previousNonpoint;
+        *rightCurve = edge;
+    } else if ( intersection.isAtStopOfCurve2 ) {
+        *leftCurve = edge;
+        *rightCurve = edge.nextNonpoint;
+    } else {
+        *leftCurve = intersection.curve2LeftBezier;
+        *rightCurve = intersection.curve2RightBezier;
+    }
+}
+
+static void FBComputeEdgeTangents(FBBezierCurve* leftCurve, FBBezierCurve *rightCurve, CGFloat offset, NSPoint edgeTangents[2])
+{
+    edgeTangents[0] = [leftCurve tangentFromRightOffset:offset];
+    edgeTangents[1] = [rightCurve tangentFromLeftOffset:offset];
+}
+
+
+static void FBComputeEdge1RangeTangentCurves(FBBezierCurve *edge, FBBezierIntersectRange *intersectRange, FBBezierCurve** leftCurve, FBBezierCurve **rightCurve)
+{
+    // edge1Tangents are firstOverlap.range1.minimum going to previous and lastOverlap.range1.maximum going to next
+    if ( intersectRange.isAtStartOfCurve1 )
+        *leftCurve = edge.previousNonpoint;
+    else
+        *leftCurve = intersectRange.curve1LeftBezier;
+    if ( intersectRange.isAtStopOfCurve1 )
+        *rightCurve = edge.nextNonpoint;
+    else
+        *rightCurve = intersectRange.curve1RightBezier;
+}
+
+static void FBComputeEdge2RangeTangentCurves(FBBezierCurve *edge, FBBezierIntersectRange *intersectRange, FBBezierCurve** leftCurve, FBBezierCurve **rightCurve)
+{
+    // edge2Tangents are firstOverlap.range2.minimum going to previous and lastOverlap.range2.maximum going to next
+    if ( intersectRange.isAtStartOfCurve2 )
+        *leftCurve = edge.previousNonpoint;
+    else
+        *leftCurve = intersectRange.curve2LeftBezier;
+    if ( intersectRange.isAtStopOfCurve2 ) {
+        *rightCurve = edge.nextNonpoint;
+    } else
+        *rightCurve = intersectRange.curve2RightBezier;
+}
+
+@interface FBBezierCurve (EdgePrivate)
+
+- (void) sortCrossings;
+
+@property (readonly) NSMutableArray *crossings_;
+
+@end
+
+@implementation FBBezierCurve (Edge)
+
+- (NSUInteger) index
+{
+    return _index;
+}
+
+- (void) setIndex:(NSUInteger)index
+{
+    _index = index;
+}
+
+- (BOOL) isStartShared
+{
+    return _startShared;
+}
+
+- (void) setStartShared:(BOOL)startShared
+{
+    _startShared = startShared;
+}
+
+- (FBBezierContour *) contour
+{
+    return _contour;
+}
+
+- (void) setContour:(FBBezierContour *)contour
+{
+    _contour = contour; // no cycles
+}
+
+- (void) addCrossing:(FBEdgeCrossing *)crossing
+{
+    // Make sure the crossing can make it back to us, and keep all the crossings sorted
+    crossing.edge = self;
+    [self.crossings_ addObject:crossing];
+    [self sortCrossings];
+}
+
+- (void) removeCrossing:(FBEdgeCrossing *)crossing
+{
+    // Keep the crossings sorted
+    crossing.edge = nil;
+    [_crossings removeObject:crossing];
+    [self sortCrossings];
+}
+
+- (void) removeAllCrossings
+{
+    [_crossings removeAllObjects];
+}
+
+- (FBBezierCurve *)next
+{
+    if ( _contour == nil )
+        return self;
+    
+    if ( _index >= ([self.contour.edges count] - 1) )
+        return [self.contour.edges objectAtIndex:0];
+    
+    return [self.contour.edges objectAtIndex:_index + 1];
+}
+
+- (FBBezierCurve *)previous
+{
+    if ( _contour == nil )
+        return self;
+    
+    if ( _index == 0 )
+        return [self.contour.edges objectAtIndex:[self.contour.edges count] - 1];
+    
+    return [self.contour.edges objectAtIndex:_index - 1];
+}
+
+- (FBBezierCurve *) nextNonpoint
+{
+    FBBezierCurve *edge = self.next;
+    while ( edge.isPoint )
+        edge = edge.next;
+    return edge;
+}
+
+- (FBBezierCurve *) previousNonpoint
+{
+    FBBezierCurve *edge = self.previous;
+    while ( edge.isPoint )
+        edge = edge.previous;
+    return edge;
+}
+
+- (BOOL) hasCrossings
+{
+    return _crossings != nil && [_crossings count] > 0;
+}
+
+- (void) crossingsWithBlock:(void (^)(FBEdgeCrossing *crossing, BOOL *stop))block
+{
+    if ( _crossings == nil )
+        return;
+    
+    BOOL stop = NO;
+    for (FBEdgeCrossing *crossing in _crossings) {
+        block(crossing, &stop);
+        if ( stop )
+            break;
+    }
+}
+
+- (void) crossingsCopyWithBlock:(void (^)(FBEdgeCrossing *crossing, BOOL *stop))block
+{
+    if ( _crossings == nil )
+        return;
+    
+    BOOL stop = NO;
+    NSArray *crossingsCopy = [[_crossings copy] autorelease];
+    for (FBEdgeCrossing *crossing in crossingsCopy) {
+        block(crossing, &stop);
+        if ( stop )
+            break;
+    }
+}
+
+- (FBEdgeCrossing *) nextCrossing:(FBEdgeCrossing *)crossing
+{
+    if ( _crossings == nil || crossing.index >= ([_crossings count] - 1) )
+        return nil;
+    
+    return [_crossings objectAtIndex:crossing.index + 1];
+}
+
+- (FBEdgeCrossing *) previousCrossing:(FBEdgeCrossing *)crossing
+{
+    if ( _crossings == nil || crossing.index == 0 )
+        return nil;
+    
+    return [_crossings objectAtIndex:crossing.index - 1];
+}
+
+- (void) intersectingEdgesWithBlock:(void (^)(FBBezierCurve *intersectingEdge))block
+{
+    [self crossingsWithBlock:^(FBEdgeCrossing *crossing, BOOL *stop) {
+        if ( crossing.isSelfCrossing )
+            return; // Right now skip over self intersecting crossings
+        FBBezierCurve *intersectingEdge = crossing.counterpart.edge;
+        block(intersectingEdge);
+    }];
+}
+
+- (void) selfIntersectingEdgesWithBlock:(void (^)(FBBezierCurve *intersectingEdge))block
+{
+    [self crossingsWithBlock:^(FBEdgeCrossing *crossing, BOOL *stop) {
+        if ( !crossing.isSelfCrossing )
+            return; // Only want the self intersecting crossings
+        FBBezierCurve *intersectingEdge = crossing.counterpart.edge;
+        block(intersectingEdge);
+    }];
+}
+
+- (FBEdgeCrossing *) firstCrossing
+{
+    if ( _crossings == nil || [_crossings count] == 0 )
+        return nil;
+    return [_crossings objectAtIndex:0];
+}
+
+- (FBEdgeCrossing *) lastCrossing
+{
+    if ( _crossings == nil || [_crossings count] == 0 )
+        return nil;
+    return [_crossings objectAtIndex:[_crossings count] - 1];
+}
+
+- (FBEdgeCrossing *) firstNonselfCrossing
+{
+    FBEdgeCrossing *first = self.firstCrossing;
+    while ( first != nil && first.isSelfCrossing )
+        first = first.next;
+    return first;
+}
+
+- (FBEdgeCrossing *) lastNonselfCrossing
+{
+    FBEdgeCrossing *last = self.lastCrossing;
+    while ( last != nil && last.isSelfCrossing )
+        last = last.previous;
+    return last;
+}
+
+- (BOOL) hasNonselfCrossings
+{
+    BOOL hasNonself = NO;
+    for (FBEdgeCrossing *crossing in _crossings) {
+        if ( !crossing.isSelfCrossing ) {
+            hasNonself = YES;
+            break;
+        }
+    }
+    return hasNonself;
+}
+
+- (BOOL) crossesEdge:(FBBezierCurve *)edge2 atIntersection:(FBBezierIntersection *)intersection
+{
+    // If it's tangent, then it doesn't cross
+    if ( intersection.isTangent )
+        return NO;
+    // If the intersect happens in the middle of both curves, then it definitely crosses, so we can just return yes. Most
+    //  intersections will fall into this category.
+    if ( !intersection.isAtEndPointOfCurve )
+        return YES;
+    
+    // The intersection happens at the end of one of the edges, meaning we'll have to look at the next
+    //  edge in sequence to see if it crosses or not. We'll do that by computing the four tangents at the exact
+    //  point the intersection takes place. We'll compute the polar angle for each of the tangents. If the
+    //  angles of self split the angles of edge2 (i.e. they alternate when sorted), then the edges cross. If
+    //  any of the angles are equal or if the angles group up, then the edges don't cross.
+    
+    // Calculate the four tangents: The two tangents moving away from the intersection point on self, the two tangents
+    //  moving away from the intersection point on edge2.
+    NSPoint edge1Tangents[] = { NSZeroPoint, NSZeroPoint };
+    NSPoint edge2Tangents[] = { NSZeroPoint, NSZeroPoint };
+    CGFloat offset = 0.0;
+    
+    FBBezierCurve *edge1LeftCurve = nil;
+    FBBezierCurve *edge1RightCurve = nil;
+    FBFindEdge1TangentCurves(self, intersection, &edge1LeftCurve, &edge1RightCurve);
+    CGFloat edge1Length = MIN([edge1LeftCurve length], [edge1RightCurve length]);
+    
+    FBBezierCurve *edge2LeftCurve = nil;
+    FBBezierCurve *edge2RightCurve = nil;
+    FBFindEdge2TangentCurves(edge2, intersection, &edge2LeftCurve, &edge2RightCurve);
+    CGFloat edge2Length = MIN([edge2LeftCurve length], [edge2RightCurve length]);
+    
+    CGFloat maxOffset = MIN(edge1Length, edge2Length);
+    
+    do {
+        FBComputeEdgeTangents(edge1LeftCurve, edge1RightCurve, offset, edge1Tangents);
+        FBComputeEdgeTangents(edge2LeftCurve, edge2RightCurve, offset, edge2Tangents);
+        
+        offset += 1.0;
+    } while ( FBAreTangentsAmbigious(edge1Tangents, edge2Tangents) && offset < maxOffset );
+    
+    return FBTangentsCross(edge1Tangents, edge2Tangents);
+}
+
+- (BOOL) crossesEdge:(FBBezierCurve *)edge2 atIntersectRange:(FBBezierIntersectRange *)intersectRange
+{
+    // Calculate the four tangents: The two tangents moving away from the intersection point on self, the two tangents
+    //  moving away from the intersection point on edge2.
+    NSPoint edge1Tangents[] = { NSZeroPoint, NSZeroPoint };
+    NSPoint edge2Tangents[] = { NSZeroPoint, NSZeroPoint };
+    CGFloat offset = 0.0;
+    
+    FBBezierCurve *edge1LeftCurve = nil;
+    FBBezierCurve *edge1RightCurve = nil;
+    FBComputeEdge1RangeTangentCurves(self, intersectRange, &edge1LeftCurve, &edge1RightCurve);
+    CGFloat edge1Length = MIN([edge1LeftCurve length], [edge1RightCurve length]);
+    
+    FBBezierCurve *edge2LeftCurve = nil;
+    FBBezierCurve *edge2RightCurve = nil;
+    FBComputeEdge2RangeTangentCurves(edge2, intersectRange, &edge2LeftCurve, &edge2RightCurve);
+    CGFloat edge2Length = MIN([edge2LeftCurve length], [edge2RightCurve length]);
+    
+    CGFloat maxOffset = MIN(edge1Length, edge2Length);
+    
+    do {
+        FBComputeEdgeTangents(edge1LeftCurve, edge1RightCurve, offset, edge1Tangents);
+        FBComputeEdgeTangents(edge2LeftCurve, edge2RightCurve, offset, edge2Tangents);
+        
+        offset += 1.0;
+    } while ( FBAreTangentsAmbigious(edge1Tangents, edge2Tangents) && offset < maxOffset );
+    
+    return FBTangentsCross(edge1Tangents, edge2Tangents);
+}
+
+@end
+
+@implementation FBBezierCurve (EdgePrivate)
+
+- (NSMutableArray *) crossings_
+{
+    if ( _crossings != nil )
+        return _crossings;
+    _crossings = [[NSMutableArray alloc] initWithCapacity:4];
+    return _crossings;
+}
+
+- (void) sortCrossings
+{
+    if ( _crossings == nil )
+        return;
+    
+    // Sort by the "order" of the crossing, then assign indices so next and previous work correctly.
+    [_crossings sortUsingComparator:^NSComparisonResult(id obj1, id obj2) {
+        FBEdgeCrossing *crossing1 = obj1;
+        FBEdgeCrossing *crossing2 = obj2;
+        if ( crossing1.order < crossing2.order )
+            return NSOrderedAscending;
+        else if ( crossing1.order > crossing2.order )
+            return NSOrderedDescending;
+        return NSOrderedSame;
+    }];
+    NSUInteger index = 0;
+    for (FBEdgeCrossing *crossing in _crossings)
+        crossing.index = index++;
+}
+
+@end

VectorBoolean/FBBezierCurve.h

 #import <Cocoa/Cocoa.h>
 #import "FBGeometry.h"
 
-@class FBBezierIntersectRange;
+@class FBBezierIntersectRange, FBBezierIntersection, FBBezierContour;
+
+typedef void (^FBCurveIntersectionBlock)(FBBezierIntersection *intersection, BOOL *stop);
+
+typedef struct FBBezierCurveLocation {
+    CGFloat parameter;
+    CGFloat distance;
+} FBBezierCurveLocation;
+
+typedef struct FBBezierCurveData {
+    NSPoint endPoint1;
+    NSPoint controlPoint1;
+    NSPoint controlPoint2;
+    NSPoint endPoint2;
+	BOOL isStraightLine;		// GPC: flag when curve came from a straight line segment
+    CGFloat length; // cached value
+    NSRect bounds; // cached value
+    BOOL isPoint; // cached value
+    NSRect boundingRect; // cached value
+} FBBezierCurveData;
 
 // FBBezierCurve is one cubic 2D bezier curve. It represents one segment of a bezier path, and is where
 //  the intersection calculation happens
 @interface FBBezierCurve : NSObject {
-    NSPoint _endPoint1;
-    NSPoint _controlPoint1;
-    NSPoint _controlPoint2;
-    NSPoint _endPoint2;
-	BOOL _isStraightLine;		// GPC: flag when curve came from a straight line segment
+    FBBezierCurveData _data;
+    
+    NSMutableArray *_crossings; // sorted by parameter of the intersection
+    FBBezierContour *_contour;
+    NSUInteger _index;
+    BOOL _startShared;
 }
 
 + (NSArray *) bezierCurvesFromBezierPath:(NSBezierPath *)path;
 + (id) bezierCurveWithLineStartPoint:(NSPoint)startPoint endPoint:(NSPoint)endPoint;
 + (id) bezierCurveWithEndPoint1:(NSPoint)endPoint1 controlPoint1:(NSPoint)controlPoint1 controlPoint2:(NSPoint)controlPoint2 endPoint2:(NSPoint)endPoint2;
 
-- (id) initWithEndPoint1:(NSPoint)endPoint1 controlPoint1:(NSPoint)controlPoint1 controlPoint2:(NSPoint)controlPoint2 endPoint2:(NSPoint)endPoint2;
-- (id) initWithLineStartPoint:(NSPoint)startPoint endPoint:(NSPoint)endPoint;
+- (id) initWithEndPoint1:(NSPoint)endPoint1 controlPoint1:(NSPoint)controlPoint1 controlPoint2:(NSPoint)controlPoint2 endPoint2:(NSPoint)endPoint2 contour:(FBBezierContour *)contour;
+- (id) initWithLineStartPoint:(NSPoint)startPoint endPoint:(NSPoint)endPoint contour:(FBBezierContour *)contour;
 
-@property NSPoint endPoint1;
-@property NSPoint controlPoint1;
-@property NSPoint controlPoint2;
-@property NSPoint endPoint2;
-@property BOOL isStraightLine;
+@property (readonly) NSPoint endPoint1;
+@property (readonly) NSPoint controlPoint1;
+@property (readonly) NSPoint controlPoint2;
+@property (readonly) NSPoint endPoint2;
+@property (readonly) BOOL isStraightLine;
 @property (readonly) NSRect bounds;
+@property (readonly) NSRect boundingRect;
+@property (readonly, getter = isPoint) BOOL point;
 
-- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve;
-- (NSArray *) intersectionsWithBezierCurve:(FBBezierCurve *)curve overlapRange:(FBBezierIntersectRange **)intersectRange;
+- (BOOL) doesHaveIntersectionsWithBezierCurve:(FBBezierCurve *)curve;
+- (void) intersectionsWithBezierCurve:(FBBezierCurve *)curve overlapRange:(FBBezierIntersectRange **)intersectRange withBlock:(FBCurveIntersectionBlock)block;
 
 - (NSPoint) pointAtParameter:(CGFloat)parameter leftBezierCurve:(FBBezierCurve **)leftBezierCurve rightBezierCurve:(FBBezierCurve **)rightBezierCurve;
 - (FBBezierCurve *) subcurveWithRange:(FBRange)range;
-- (NSArray *) splitSubcurvesWithRange:(FBRange)range;
+- (void) splitSubcurvesWithRange:(FBRange)range left:(FBBezierCurve **)leftCurve middle:(FBBezierCurve **)middleCurve right:(FBBezierCurve **)rightCurve;
 
 - (CGFloat) lengthAtParameter:(CGFloat)parameter;
 - (CGFloat) length;
 
+- (NSPoint) pointFromRightOffset:(CGFloat)offset;
+- (NSPoint) pointFromLeftOffset:(CGFloat)offset;
+
+- (NSPoint) tangentFromRightOffset:(CGFloat)offset;
+- (NSPoint) tangentFromLeftOffset:(CGFloat)offset;
+
+- (FBBezierCurveLocation) closestLocationToPoint:(NSPoint)point;
+
 - (FBBezierCurve *) reversedCurve;	// GPC: added
 
 - (NSBezierPath *) bezierPath;
 
+- (FBBezierCurve *) clone;
+
 @end

VectorBoolean/FBBezierCurve.m

 #import "FBBezierIntersection.h"
 #import "FBBezierIntersectRange.h"
 
+#pragma mark FBNormalizedLine
+
 //////////////////////////////////////////////////////////////////////////////////
 // Normalized lines
 //
     return line;
 }
 
+static FBNormalizedLine FBNormalizedLineMakeWithCoefficients(CGFloat a, CGFloat b, CGFloat c)
+{
+    FBNormalizedLine line = { a, b, c };
+    return line;
+}
+
+static FBNormalizedLine FBNormalizedLineOffset(FBNormalizedLine line, CGFloat offset)
+{
+    line.c += offset;
+    return line;
+}
+
 static CGFloat FBNormalizedLineDistanceFromPoint(FBNormalizedLine line, NSPoint point)
 {
     return line.a * point.x + line.b * point.y + line.c;
 }
 
+static NSPoint FBNormalizedLineIntersection(FBNormalizedLine line1, FBNormalizedLine line2)
+{
+    CGFloat denominator = line1.a * line2.b - line2.a * line1.b;
+    return NSMakePoint((line1.b * line2.c - line2.b * line1.c) / denominator, (line1.a * line2.c - line2.a * line1.c) / denominator);
+}
+
+#pragma mark Helper functions
 
 //////////////////////////////////////////////////////////////////////////////////
 // Helper functions
 //
 
+
+static CGFloat FBParameterOfPointOnLine(NSPoint lineStart, NSPoint lineEnd, NSPoint point)
+{
+    // Note: its asumed you have already checked that point is colinear with the line (lineStart, lineEnd)
+    CGFloat lineLength = FBDistanceBetweenPoints(lineStart, lineEnd);
+    CGFloat lengthFromStart = FBDistanceBetweenPoints(point, lineStart);
+    CGFloat parameter = lengthFromStart / lineLength;
+    
+    // The only tricky thing here is the sign. Is the point _before_ lineStart, or after lineStart?
+    CGFloat lengthFromEnd = FBDistanceBetweenPoints(point, lineEnd);
+    if ( FBAreValuesClose(lineLength + lengthFromStart, lengthFromEnd) )
+        parameter = -parameter;
+    
+    return parameter;
+}
+
+static BOOL FBLinesIntersect(NSPoint line1Start, NSPoint line1End, NSPoint line2Start, NSPoint line2End, NSPoint *outIntersect)
+{
+    FBNormalizedLine line1 = FBNormalizedLineMake(line1Start, line1End);
+    FBNormalizedLine line2 = FBNormalizedLineMake(line2Start, line2End);
+    *outIntersect = FBNormalizedLineIntersection(line1, line2);
+    if ( isnan(outIntersect->x) || isnan(outIntersect->y) )
+        return NO;
+    outIntersect->y = -outIntersect->y;
+    return YES;    
+}
+
 // The three points are a counter-clockwise turn if the return value is greater than 0,
 //  clockwise if less than 0, or colinear if 0.
 static CGFloat CounterClockwiseTurn(NSPoint point1, NSPoint point2, NSPoint point3)
     // degree is the order of the bezier path, which will be cubic (3) most of the time.
     
     // With this algorithm we start out with the points in the bezier path. 
-    NSPoint points[4] = {}; // we assume we'll never get more than a cubic bezier
+    NSPoint points[6] = {}; // we assume we'll never get more than a cubic bezier
     for (NSUInteger i = 0; i <= degree; i++)
         points[i] = bezierPoints[i];
     
     return points[0];
 }
 
-static NSArray *FBComputeCubicFirstDerivativeRoots(CGFloat a, CGFloat b, CGFloat c, CGFloat d)
+static void FBComputeCubicFirstDerivativeRoots(CGFloat a, CGFloat b, CGFloat c, CGFloat d, CGFloat *outRoots, NSUInteger *outRootsCount)
 {
     // See http://processingjs.nihongoresources.com/bezierinfo/#bounds for where the formulas come from
     CGFloat denominator = -a + 3.0 * b - 3.0 * c + d;
         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];
+        outRoots[0] = t1;
+        outRoots[1] = t2;
+        *outRootsCount = 2;
+        return;
     }
     
     // If denominator == 0, fall back to 
     CGFloat t = (a - b) / (2.0 * (a - 2.0 * b + c));
-    return [NSArray arrayWithObject:[NSNumber numberWithFloat:t]];
+    outRoots[0] = t;
+    *outRootsCount = 1;
 }
 
 // Legendre-Gauss abscissae (xi values, defined at i=n as the roots of the nth order Legendre polynomial Pn(x))
 
 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;
+    CGFloat t1 = -3.0 * p1 + 9.0 * p2 - 9.0 * p3 + 3.0 * p4;
+    CGFloat 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)
+static CGFloat FBGaussQuadratureFOfTForCubic(CGFloat t, NSPoint p1, NSPoint p2, NSPoint p3, NSPoint 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);
+    return sqrt(baseX * baseX + baseY * baseY);
 }
 
-static CGFloat FBGaussQuadratureComputeCurveLengthForCubic(CGFloat z, NSUInteger steps, CGPoint p1, CGPoint p2, CGPoint p3, CGPoint p4)
+static CGFloat FBGaussQuadratureComputeCurveLengthForCubic(CGFloat z, NSUInteger steps, NSPoint p1, NSPoint p2, NSPoint p3, NSPoint p4)
 {
     CGFloat z2 = z / 2.0;
     CGFloat sum = 0.0;
     return z2 * sum;
 }
 
+static NSInteger FBSign(CGFloat value)
+{
+    return value < 0.0 ? -1.0 : 1.0;
+}
+
+static NSUInteger FBCountBezierCrossings(NSPoint *bezierPoints, NSUInteger degree)
+{
+    NSUInteger count = 0;
+    NSInteger sign = FBSign(bezierPoints[0].y);
+    NSInteger previousSign = sign;
+    for (NSInteger i = 1; i <= degree; i++) {
+        sign = FBSign(bezierPoints[i].y);
+        if ( sign != previousSign )
+            count++;
+        previousSign = sign;
+    }
+    return count;
+}
+
+static const NSUInteger FBFindBezierRootsMaximumDepth = 64;
+
+static BOOL FBIsControlPolygonFlatEnough(NSPoint *bezierPoints, NSUInteger degree, NSPoint *intersectionPoint)
+{
+    CGFloat FBFindBezierRootsErrorThreshold = ldexpf(1, -(int)(FBFindBezierRootsMaximumDepth - 1));
+    
+    FBNormalizedLine line = FBNormalizedLineMake(bezierPoints[0], bezierPoints[degree]);
+    
+    // Find the bounds around the line
+    CGFloat belowDistance = 0;
+    CGFloat aboveDistance = 0;
+    for (NSUInteger i = 1; i < degree; i++) {
+        CGFloat distance = FBNormalizedLineDistanceFromPoint(line, bezierPoints[i]);
+        if ( distance > aboveDistance )
+            aboveDistance = distance;
+        if ( distance < belowDistance )
+            belowDistance = distance;
+    }
+    
+    FBNormalizedLine zeroLine = FBNormalizedLineMakeWithCoefficients(0, 1, 0);
+    FBNormalizedLine aboveLine = FBNormalizedLineOffset(line, -aboveDistance);
+    NSPoint intersect1 = FBNormalizedLineIntersection(zeroLine, aboveLine);
+    
+    FBNormalizedLine belowLine = FBNormalizedLineOffset(line, -belowDistance);
+    NSPoint intersect2 = FBNormalizedLineIntersection(zeroLine, belowLine);
+    
+    CGFloat error = MAX(intersect1.x, intersect2.x) - MIN(intersect1.x, intersect2.x);
+    if ( error < FBFindBezierRootsErrorThreshold ) {
+        *intersectionPoint = FBNormalizedLineIntersection(zeroLine, line);
+        return YES;
+    }
+    
+    return NO;
+}
+
+static void FBFindBezierRootsWithDepth(NSPoint *bezierPoints, NSUInteger degree, NSUInteger depth, void (^block)(CGFloat root))
+{
+    NSUInteger crossingCount = FBCountBezierCrossings(bezierPoints, degree);
+    if ( crossingCount == 0 )
+        return;
+    else if ( crossingCount == 1 ) {
+        if ( depth >= FBFindBezierRootsMaximumDepth ) {
+            CGFloat root = (bezierPoints[0].x + bezierPoints[degree].x) / 2.0;
+            block(root);
+            return;
+        }
+        NSPoint intersectionPoint = NSZeroPoint;
+        if ( FBIsControlPolygonFlatEnough(bezierPoints, degree, &intersectionPoint) ) {
+            block(intersectionPoint.x);
+            return;
+        }
+    }
+    
+    // Subdivide and try again
+    NSPoint leftCurve[6] = {}; // assume 5th degree
+    NSPoint rightCurve[6] = {};
+    BezierWithPoints(degree, bezierPoints, 0.5, leftCurve, rightCurve);
+    FBFindBezierRootsWithDepth(leftCurve, degree, depth + 1, block);
+    FBFindBezierRootsWithDepth(rightCurve, degree, depth + 1, block);
+}
+
+static void FBFindBezierRoots(NSPoint *bezierPoints, NSUInteger degree, void (^block)(CGFloat root))
+{
+    FBFindBezierRootsWithDepth(bezierPoints, degree, 0, block);
+}
+
+#pragma mark Convex Hull
+
+//////////////////////////////////////////////////////////////////////////////////
+// Convex Hull functions
+
+static inline BOOL FBConvexHullDoPointsTurnWrongDirection(NSPoint point1, NSPoint point2, NSPoint point3)
+{
+    CGFloat area = CounterClockwiseTurn(point1, point2, point3);
+    return FBAreValuesClose(area, 0.0) || area < 0.0;
+}
+
+static void FBConvexHullBuildFromPoints(NSPoint points[4], NSPoint *results, NSUInteger *outLength)
+{
+    // Compute the convex hull for this bezier curve. The convex hull is made up of the end and control points.
+    //  The hard part is determine the order they go in, and if any are inside or colinear with the convex hull.
+    
+    // Uses the Monotone chain algorithm:
+    //  http://en.wikibooks.org/wiki/Algorithm_Implementation/Geometry/Convex_hull/Monotone_chain
+    
+    // Start with all the end and control points in any order.
+    NSUInteger numberOfPoints = 4;
+    
+    // Sort points ascending x, if equal compare y
+    //  Bubble sort, which should be ok with a max of 4 elements, and the fact that our one current use case
+    //  already has them in ascending X order (i.e. should be just comparisons to verify)
+    NSUInteger sortLength = numberOfPoints;
+    do {
+        NSUInteger newSortLength = 0;
+        for (NSUInteger i = 1; i < sortLength; i++) {
+            if ( points[i - 1].x > points[i].x || (FBAreValuesClose(points[i - 1].x, points[i].x) && points[i - 1].y > points[i].y) ) {
+                NSPoint tempPoint = points[i];
+                points[i] = points[i - 1];
+                points[i - 1] = tempPoint;
+                newSortLength = i;
+            }
+        }
+        sortLength = newSortLength;
+    } while ( sortLength > 0 );
+    
+    
+    // Create the results
+    NSUInteger filledInIndex = 0;
+    
+    // Build lower hull
+    for (NSUInteger i = 0; i < numberOfPoints; i++) {
+        while ( filledInIndex >= 2 && FBConvexHullDoPointsTurnWrongDirection(results[filledInIndex - 2], results[filledInIndex - 1], points[i]) )
+            --filledInIndex;
+        results[filledInIndex] = points[i];
+        ++filledInIndex;
+    }
+    
+    // Build upper hull
+    for (NSInteger i = numberOfPoints - 2, thresholdIndex = filledInIndex + 1; i >= 0; i--) {
+        while ( filledInIndex >= thresholdIndex && FBConvexHullDoPointsTurnWrongDirection(results[filledInIndex - 2], results[filledInIndex - 1], points[i]) )
+            --filledInIndex;
+        results[filledInIndex] = points[i];
+        ++filledInIndex;
+    }
+    
+    *outLength = filledInIndex - 1;
+}
+
+#pragma mark FBBezierCurve Private Interface
+
+@interface FBBezierCurve ()
+
++ (id) bezierCurveWithBezierCurveData:(FBBezierCurveData)data;
+- (id) initWithBezierCurveData:(FBBezierCurveData)data;
+
+- (CGFloat) refineParameter:(CGFloat)parameter forPoint:(NSPoint)point;
+
+@property (readonly) FBBezierCurveData data;
+
+@end
+
+#pragma mark FBBezierCurveData
+
+static const CGFloat FBBezierCurveDataInvalidLength = -1.0;
+static const BOOL FBBezierCurveDataInvalidIsPoint = -1;
+
+static FBBezierCurveData FBBezierCurveDataMake(NSPoint endPoint1, NSPoint controlPoint1, NSPoint controlPoint2, NSPoint endPoint2, BOOL isStraightLine)
+{
+    FBBezierCurveData data = {endPoint1, controlPoint1, controlPoint2, endPoint2, isStraightLine, FBBezierCurveDataInvalidLength, NSZeroRect, FBBezierCurveDataInvalidIsPoint, NSZeroRect };
+    return data;
+}
+
+static CGFloat FBBezierCurveDataGetLengthAtParameter(FBBezierCurveData* me, CGFloat parameter)
+{
+    // Use the cached value if at all possible
+    if ( parameter == 1.0 && me->length != FBBezierCurveDataInvalidLength )
+        return me->length;
+    
+    // If it's a line, use that equation instead
+    CGFloat length = FBBezierCurveDataInvalidLength;
+    if ( me->isStraightLine )
+        length = FBDistanceBetweenPoints(me->endPoint1, me->endPoint2) * parameter;
+    else
+        length = FBGaussQuadratureComputeCurveLengthForCubic(parameter, 12, me->endPoint1, me->controlPoint1, me->controlPoint2, me->endPoint2);
+    
+    // If possible, update our cache
+    if ( parameter == 1.0 )
+        me->length = length;
+    
+    return length;
+}
+
+static CGFloat FBBezierCurveDataGetLength(FBBezierCurveData* me)
+{
+    return FBBezierCurveDataGetLengthAtParameter(me, 1.0);
+}
+
+static NSPoint FBBezierCurveDataPointAtParameter(FBBezierCurveData me, CGFloat parameter, FBBezierCurveData *leftBezierCurve, FBBezierCurveData *rightBezierCurve)
+{
+    // This method is a simple wrapper around the BezierWithPoints() helper function. It computes the 2D point at the given parameter,
+    //  and (optionally) the resulting curves that splitting at the parameter would create.
+    
+    NSPoint points[4] = { me.endPoint1, me.controlPoint1, me.controlPoint2, me.endPoint2 };
+    NSPoint leftCurve[4] = {};
+    NSPoint rightCurve[4] = {};
+    
+    NSPoint point = BezierWithPoints(3, points, parameter, leftCurve, rightCurve);
+    
+    if ( leftBezierCurve != nil ) {
+        *leftBezierCurve = FBBezierCurveDataMake(leftCurve[0], leftCurve[1], leftCurve[2], leftCurve[3], me.isStraightLine);
+	}
+    if ( rightBezierCurve != nil ) {
+        *rightBezierCurve = FBBezierCurveDataMake(rightCurve[0], rightCurve[1], rightCurve[2], rightCurve[3], me.isStraightLine);
+	}
+    return point;
+}
+
+static FBBezierCurveData FBBezierCurveDataSubcurveWithRange(FBBezierCurveData me, 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.
+    FBBezierCurveData upperCurve = {};
+    FBBezierCurveDataPointAtParameter(me, range.minimum, nil, &upperCurve);
+    if ( range.minimum == 1.0 )
+        return upperCurve; // 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);
+    
+    FBBezierCurveData lowerCurve = {};
+    FBBezierCurveDataPointAtParameter(upperCurve, adjustedMaximum, &lowerCurve, nil);
+    return lowerCurve;
+}
+
+static FBNormalizedLine FBBezierCurveDataRegularFatLineBounds(FBBezierCurveData me, FBRange *range)
+{
+    // Create the fat line based on the end points
+    FBNormalizedLine line = FBNormalizedLineMake(me.endPoint1, me.endPoint2);
+    
+    // Compute the bounds of the fat line. The fat line bounds should entirely encompass the
+    //  bezier curve. Since we know the convex hull entirely compasses the curve, just take
+    //  all four points that define this cubic bezier curve. Compute the signed distances of
+    //  each of the end and control points from the fat line, and that will give us the bounds.
+    
+    // In this case, we know that the end points are on the line, thus their distances will be 0.
+    //  So we can skip computing those and just use 0.
+    CGFloat controlPoint1Distance = FBNormalizedLineDistanceFromPoint(line, me.controlPoint1);
+    CGFloat controlPoint2Distance = FBNormalizedLineDistanceFromPoint(line, me.controlPoint2);
+    CGFloat min = MIN(controlPoint1Distance, MIN(controlPoint2Distance, 0.0));
+    CGFloat max = MAX(controlPoint1Distance, MAX(controlPoint2Distance, 0.0));
+    
+    *range = FBRangeMake(min, max);
+    
+    return line;
+}
+
+static FBNormalizedLine FBBezierCurveDataPerpendicularFatLineBounds(FBBezierCurveData me, FBRange *range)
+{
+    // Create a fat line that's perpendicular to the line created by the two end points.
+    NSPoint normal = FBLineNormal(me.endPoint1, me.endPoint2);
+    NSPoint startPoint = FBLineMidpoint(me.endPoint1, me.endPoint2);
+    NSPoint endPoint = FBAddPoint(startPoint, normal);
+    FBNormalizedLine line = FBNormalizedLineMake(startPoint, endPoint);
+    
+    // Compute the bounds of the fat line. The fat line bounds should entirely encompass the
+    //  bezier curve. Since we know the convex hull entirely compasses the curve, just take
+    //  all four points that define this cubic bezier curve. Compute the signed distances of
+    //  each of the end and control points from the fat line, and that will give us the bounds.
+    CGFloat controlPoint1Distance = FBNormalizedLineDistanceFromPoint(line, me.controlPoint1);
+    CGFloat controlPoint2Distance = FBNormalizedLineDistanceFromPoint(line, me.controlPoint2);
+    CGFloat point1Distance = FBNormalizedLineDistanceFromPoint(line, me.endPoint1);
+    CGFloat point2Distance = FBNormalizedLineDistanceFromPoint(line, me.endPoint2);
+    
+    CGFloat min = MIN(controlPoint1Distance, MIN(controlPoint2Distance, MIN(point1Distance, point2Distance)));
+    CGFloat max = MAX(controlPoint1Distance, MAX(controlPoint2Distance, MAX(point1Distance, point2Distance)));
+    
+    *range = FBRangeMake(min, max);
+    
+    return line;
+}
+
+static FBRange FBBezierCurveDataClipWithFatLine(FBBezierCurveData me, FBNormalizedLine fatLine, FBRange bounds)
+{
+    // This method computes the range of self that could possibly intersect with the fat line passed in (and thus with the curve enclosed by the fat line).
+    //  To do that, we first compute the signed distance of all our points (end and control) from the fat line, and map those onto a bezier curve at
+    //  evenly spaced intervals from [0..1]. The parts of the distance bezier that fall inside of the fat line bounds, correspond to the parts of ourself
+    //  that could potentially intersect with the other curve. Ideally, we'd calculate where the distance bezier intersected the horizontal lines representing
+    //  the fat line bounds. However, computing those intersections is hard and costly. So instead we'll compute the convex hull, and intersect those lines
+    //  with the fat line bounds. The intersection with the lowest x coordinate will be the minimum, and the intersection with the highest x coordinate will
+    //  be the maximum.
+    
+    // The convex hull (for cubic beziers) is the four points that define the curve. A useful property of the convex hull is that the entire curve lies
+    //  inside of it.
+    
+    // First calculate bezier curve points distance from the fat line that's clipping us
+    NSPoint distanceBezierPoints[] = {
+        NSMakePoint(0, FBNormalizedLineDistanceFromPoint(fatLine, me.endPoint1)),
+        NSMakePoint(1.0/3.0, FBNormalizedLineDistanceFromPoint(fatLine, me.controlPoint1)),
+        NSMakePoint(2.0/3.0, FBNormalizedLineDistanceFromPoint(fatLine, me.controlPoint2)),
+        NSMakePoint(1.0, FBNormalizedLineDistanceFromPoint(fatLine, me.endPoint2))
+    };
+    
+    NSUInteger convexHullLength = 0;
+    NSPoint convexHull[8] = {};
+    FBConvexHullBuildFromPoints(distanceBezierPoints, convexHull, &convexHullLength);
+    
+    // Find intersections of convex hull with the fat line bounds
+    FBRange range = FBRangeMake(1.0, 0.0);
+    for (NSUInteger i = 0; i < convexHullLength; i++) {
+        // Pull out the current line on the convex hull
+        NSUInteger indexOfNext = i < (convexHullLength - 1) ? i + 1 : 0;
+        NSPoint startPoint = convexHull[i];
+        NSPoint endPoint = convexHull[indexOfNext];
+        NSPoint intersectionPoint = NSZeroPoint;
+        
+        // See if the segment of the convex hull intersects with the minimum fat line bounds
+        if ( LineIntersectsHorizontalLine(startPoint, endPoint, bounds.minimum, &intersectionPoint) ) {
+            if ( intersectionPoint.x < range.minimum )
+                range.minimum = intersectionPoint.x;
+            if ( intersectionPoint.x > range.maximum )
+                range.maximum = intersectionPoint.x;
+        }
+        
+        // See if this segment of the convex hull intersects with the maximum fat line bounds
+        if ( LineIntersectsHorizontalLine(startPoint, endPoint, bounds.maximum, &intersectionPoint) ) {
+            if ( intersectionPoint.x < range.minimum )
+                range.minimum = intersectionPoint.x;
+            if ( intersectionPoint.x > range.maximum )
+                range.maximum = intersectionPoint.x;
+        }
+        
+        // We want to be able to refine t even if the convex hull lies completely inside the bounds. This
+        //  also allows us to be able to use range of [1..0] as a sentinel value meaning the convex hull
+        //  lies entirely outside of bounds, and the curves don't intersect.
+        if ( startPoint.y < bounds.maximum && startPoint.y > bounds.minimum ) {
+            if ( startPoint.x < range.minimum )
+                range.minimum = startPoint.x;
+            if ( startPoint.x > range.maximum )
+                range.maximum = startPoint.x;
+        }
+    }
+    
+    // Check for bad values
+    if ( range.minimum == INFINITY || range.minimum == NAN || range.maximum == INFINITY || range.maximum == NAN )
+        range = FBRangeMake(0, 1); // equivalent to: something went wrong, so I don't know
+    
+    return range;
+}
+
+static FBBezierCurveData FBBezierCurveDataBezierClipWithBezierCurve(FBBezierCurveData me, FBBezierCurveData curve, FBBezierCurveData originalCurve, FBRange *originalRange, BOOL *intersects)
+{
+    // This method does the clipping of self. It removes the parts of self that we can determine don't intersect
+    //  with curve. It'll return the clipped version of self, update originalRange which corresponds to the range
+    //  on the original curve that the return value represents. Finally, it'll set the intersects out parameter
+    //  to yes or no depending on if the curves intersect or not.
+    
+    // Clipping works as follows:
+    //  Draw a line through the two endpoints of the other curve, which we'll call the fat line. Measure the
+    //  signed distance between the control points on the other curve and the fat line. The distance from the line
+    //  will give us the fat line bounds. Any part of our curve that lies further away from the fat line than the
+    //  fat line bounds we know can't intersect with the other curve, and thus can be removed.
+    
+    // We actually use two different fat lines. The first one uses the end points of the other curve, and the second
+    //  one is perpendicular to the first. Most of the time, the first fat line will clip off more, but sometimes the
+    //  second proves to be a better fat line in that it clips off more. We use both in order to converge more quickly.
+    
+    // Compute the regular fat line using the end points, then compute the range that could still possibly intersect
+    //  with the other curve
+    FBRange fatLineBounds = {};
+    FBNormalizedLine fatLine = FBBezierCurveDataRegularFatLineBounds(curve, &fatLineBounds);
+    FBRange regularClippedRange = FBBezierCurveDataClipWithFatLine(me, fatLine, fatLineBounds);
+    // A range of [1, 0] is a special sentinel value meaning "they don't intersect". If they don't, bail early to save time
+    if ( regularClippedRange.minimum == 1.0 && regularClippedRange.maximum == 0.0 ) {
+        *intersects = NO;
+        return me;
+    }
+    
+    // Just in case the regular fat line isn't good enough, try the perpendicular one
+    FBRange perpendicularLineBounds = {};
+    FBNormalizedLine perpendicularLine = FBBezierCurveDataPerpendicularFatLineBounds(curve, &perpendicularLineBounds);
+    FBRange perpendicularClippedRange = FBBezierCurveDataClipWithFatLine(me, perpendicularLine, perpendicularLineBounds);
+    if ( perpendicularClippedRange.minimum == 1.0 && perpendicularClippedRange.maximum == 0.0 ) {
+        *intersects = NO;
+        return me;
+    }
+    
+    // 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;
+    *intersects = YES;
+    
+    // Actually divide the curve, but be sure to use the original curve. This helps with errors building up.
+    return FBBezierCurveDataSubcurveWithRange(originalCurve, *originalRange);
+}
+
+static BOOL FBBezierCurveDataIsPoint(FBBezierCurveData *me)
+{
+    // If the two end points are close together, then we're a point. Ignore the control
+    //  points.
+    static const CGFloat FBClosenessThreshold = 1e-5;
+    
+    if ( me->isPoint != FBBezierCurveDataInvalidIsPoint )
+        return me->isPoint;
+    
+    me->isPoint = FBArePointsCloseWithOptions(me->endPoint1, me->endPoint2, FBClosenessThreshold)
+        && FBArePointsCloseWithOptions(me->endPoint1, me->controlPoint1, FBClosenessThreshold)
+        && FBArePointsCloseWithOptions(me->endPoint1, me->controlPoint2, FBClosenessThreshold);
+    
+    return me->isPoint;
+}
+
+static NSRect FBBezierCurveDataBoundingRect(FBBezierCurveData *me)
+{
+    // Use the cache if we have one
+    if ( !NSEqualRects(me->boundingRect, NSZeroRect) )
+        return me->boundingRect;
+
+    CGFloat left = MIN(me->endPoint1.x, MIN(me->controlPoint1.x, MIN(me->controlPoint2.x, me->endPoint2.x)));
+    CGFloat top = MIN(me->endPoint1.y, MIN(me->controlPoint1.y, MIN(me->controlPoint2.y, me->endPoint2.y)));
+    CGFloat right = MAX(me->endPoint1.x, MAX(me->controlPoint1.x, MAX(me->controlPoint2.x, me->endPoint2.x)));
+    CGFloat bottom = MAX(me->endPoint1.y, MAX(me->controlPoint1.y, MAX(me->controlPoint2.y, me->endPoint2.y)));
+    
+    me->boundingRect = NSMakeRect(left, top, right - left, bottom - top);
+    
+    return me->boundingRect;
+}
+
+static NSRect FBBezierCurveDataBounds(FBBezierCurveData* me)
+{
+    // Use the cache if we have one
+    if ( !NSEqualRects(me->bounds, NSZeroRect) )
+        return me->bounds;
+    
+    NSRect bounds = NSZeroRect;
+    
+    if ( me->isStraightLine ) {
+        NSPoint topLeft = me->endPoint1;
+        NSPoint bottomRight = topLeft;
+        FBExpandBoundsByPoint(&topLeft, &bottomRight, me->endPoint2);
+
+        bounds = NSMakeRect(topLeft.x, topLeft.y, bottomRight.x - topLeft.x, bottomRight.y - topLeft.y);
+    } else {
+        // Start with the end points
+        NSPoint topLeft = FBBezierCurveDataPointAtParameter(*me, 0, nil, nil);
+        NSPoint bottomRight = topLeft;
+        NSPoint lastPoint = FBBezierCurveDataPointAtParameter(*me, 1, nil, nil);
+        FBExpandBoundsByPoint(&topLeft, &bottomRight, lastPoint);
+        
+        // Find the roots, which should be the extremities
+        CGFloat xRoots[] = {0.0, 0.0};
+        NSUInteger xRootsCount = 0;
+        FBComputeCubicFirstDerivativeRoots(me->endPoint1.x, me->controlPoint1.x, me->controlPoint2.x, me->endPoint2.x, xRoots, &xRootsCount);
+        for (NSUInteger i = 0; i < xRootsCount; i++) {
+            CGFloat t = xRoots[i];
+            if ( t < 0 || t > 1 )
+                continue;
+            
+            NSPoint location = FBBezierCurveDataPointAtParameter(*me, t, nil, nil);
+            FBExpandBoundsByPoint(&topLeft, &bottomRight, location);
+        }
+        
+        CGFloat yRoots[] = {0.0, 0.0};
+        NSUInteger yRootsCount = 0;
+        FBComputeCubicFirstDerivativeRoots(me->endPoint1.y, me->controlPoint1.y, me->controlPoint2.y, me->endPoint2.y, yRoots, &yRootsCount);
+        for (NSUInteger i = 0; i < yRootsCount; i++) {
+            CGFloat t = yRoots[i];
+            if ( t < 0 || t > 1 )
+                continue;
+            
+            NSPoint location = FBBezierCurveDataPointAtParameter(*me, t, nil, nil);
+            FBExpandBoundsByPoint(&topLeft, &bottomRight, location);
+        }
+        
+        bounds = NSMakeRect(topLeft.x, topLeft.y, bottomRight.x - topLeft.x, bottomRight.y - topLeft.y);
+    }
+    
+    // Cache the value
+    me->bounds = bounds;
+    
+    return me->bounds;
+}
+
+static void FBBezierCurveDataRefineIntersectionsOverIterations(NSUInteger iterations, FBRange *usRange, FBRange *themRange, FBBezierCurveData originalUs, FBBezierCurveData originalThem, FBBezierCurveData us, FBBezierCurveData them, FBBezierCurveData nonpointUs, FBBezierCurveData nonpointThem)
+{
+    for (NSUInteger i = 0; i < iterations; i++) {
+        BOOL intersects = NO;
+        us = FBBezierCurveDataBezierClipWithBezierCurve(us, them, originalUs, usRange, &intersects);
+        if ( !intersects )
+            us = FBBezierCurveDataBezierClipWithBezierCurve(nonpointUs, nonpointThem, originalUs, usRange, &intersects);
+        them = FBBezierCurveDataBezierClipWithBezierCurve(them, us, originalThem, themRange, &intersects);
+        if ( !intersects )
+            them = FBBezierCurveDataBezierClipWithBezierCurve(nonpointThem, nonpointUs, originalThem, themRange, &intersects);
+        if ( !FBBezierCurveDataIsPoint(&them) )
+            nonpointThem = them;
+        if ( !FBBezierCurveDataIsPoint(&us) )
+            nonpointUs = us;
+    }
+}
+
+
+static FBBezierCurveData FBBezierCurveDataClipLineOriginalCurve(FBBezierCurveData me, FBBezierCurveData originalCurve, FBBezierCurveData curve, FBRange *originalRange, FBBezierCurveData otherCurve, BOOL *intersects)
+{
+    CGFloat themOnUs1 = FBParameterOfPointOnLine(curve.endPoint1, curve.endPoint2, otherCurve.endPoint1);
+    CGFloat themOnUs2 = FBParameterOfPointOnLine(curve.endPoint1, curve.endPoint2, otherCurve.endPoint2);
+    FBRange clippedRange = FBRangeMake(MAX(0, MIN(themOnUs1, themOnUs2)), MIN(1, MAX(themOnUs1, themOnUs2)));
+    if ( clippedRange.minimum > clippedRange.maximum ) {
+        *intersects = NO;
+        return curve; // No intersection
+    }
+    
+    // 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;
+    *intersects = YES;
+    
+    // Actually divide the curve, but be sure to use the original curve. This helps with errors building up.
+    return FBBezierCurveDataSubcurveWithRange(originalCurve, *originalRange);
+}
+
+static BOOL FBBezierCurveDataCheckLinesForOverlap(FBBezierCurveData me, FBRange *usRange, FBRange *themRange, FBBezierCurveData originalUs, FBBezierCurveData originalThem, FBBezierCurveData *us, FBBezierCurveData *them)
+{
+    // First see if its possible for them to overlap at all
+    if ( !FBLineBoundsMightOverlap(FBBezierCurveDataBounds(us), FBBezierCurveDataBounds(them)) )
+        return NO;
+    
+    // Are all 4 points in a single line?
+    CGFloat errorThreshold = 1e-7;    
+    BOOL isColinear = FBAreValuesCloseWithOptions(CounterClockwiseTurn((*us).endPoint1, (*us).endPoint2, (*them).endPoint1), 0.0, errorThreshold)
+                    && FBAreValuesCloseWithOptions(CounterClockwiseTurn((*us).endPoint1, (*us).endPoint2, (*them).endPoint2), 0.0, errorThreshold);
+    if ( !isColinear )
+        return NO;
+    
+    BOOL intersects = NO;
+    *us = FBBezierCurveDataClipLineOriginalCurve(me, originalUs, *us, usRange, *them, &intersects);
+    if ( !intersects )
+        return NO;
+
+    *them = FBBezierCurveDataClipLineOriginalCurve(me, originalThem, *them, themRange, *us, &intersects);
+    
+    return intersects;
+}
+
+static void FBBezierCurveDataConvertSelfAndPoint(FBBezierCurveData me, NSPoint point, NSPoint *bezierPoints)
+{
+    NSPoint selfPoints[4] = { me.endPoint1, me.controlPoint1, me.controlPoint2, me.endPoint2 };
+    
+    // c[i] in the paper
+    NSPoint distanceFromPoint[4] = {};
+    for (NSUInteger i = 0; i < 4; i++)
+        distanceFromPoint[i] = FBSubtractPoint(selfPoints[i], point);
+        
+        // d[i] in the paper
+        NSPoint weightedDelta[3] = {};
+        for (NSUInteger i = 0; i < 3; i++)
+            weightedDelta[i] = FBScalePoint(FBSubtractPoint(selfPoints[i + 1], selfPoints[i]), 3);
+