+//////////////////////////////////////////////////////////////////////////
+// Helper methods for angles
static const CGFloat FB2PI = 2.0 * M_PI;
+// Normalize the angle between 0 and 2pi
static CGFloat NormalizeAngle(CGFloat value)
+// Compute the polar angle from the cartesian point
static CGFloat PolarAngle(NSPoint point)
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 {
return angle >= 0.0 && angle < range.maximum;
+//////////////////////////////////////////////////////////////////////////
+// The main point of this class is to perform boolean operations. The algorithm
+// used here is a modified and expanded version of the algorithm presented
+// in "Efficient clipping of arbitrary polygons" by Günther Greiner and Kai Hormann.
+// http://www.inf.usi.ch/hormann/papers/Greiner.1998.ECO.pdf
+// That algorithm assumes polygons, not curves, and only considers one contour intersecting
+// one other contour. My algorithm uses bezier curves (not polygons) and handles
+// multiple contours intersecting other contours.
@interface FBBezierGraph ()
- (void) removeDuplicateCrossings;
+ // 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;
_contours = [[NSMutableArray alloc] initWithCapacity:2];
+ // Go through and mark each contour if its a hole or filled region
for (contour in _contours)
contour.inside = [self contourInsides:contour];
+////////////////////////////////////////////////////////////////////////
+// The three main boolean operations (union, intersect, difference) follow
+// much the same algorithm. First, the places where the two graphs cross
+// (not just intersect) are marked on the graph with FBEdgeCrossing objects.
+// Next, we decide which sections of the two graphs should appear in the final
+// result. (There are only two kind of sections: those inside of the other graph,
+// and those outside.) We do this by walking all the crossings we created
+// and marking them as entering a section that should appear in the final result,
+// or as exiting the final result. We then walk all the crossings again, and
+// actually output the final result of the graphs that intersect.
+// The last part of each boolean operation deals with what do with contours
+// in each graph that don't intersect any other contours.
+// The exclusive or boolean op is implemented in terms of union, intersect,
+// and difference. More specifically it subtracts the intersection of both
+// graphs from the union of both graphs.
- (FBBezierGraph *) unionWithBezierGraph:(FBBezierGraph *)graph
+ // First insert FBEdgeCrossings into both graphs where the graphs
[self insertCrossingsWithBezierGraph:graph];
+ // 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];
+ // 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];
+ // 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];
- // There are no crossings, which means one contains the other, or they're completely disjoint
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];
if ( clipContainsSubject )
[finalNonintersectingContours removeObject:ourContour];
for (FBBezierContour *theirContour in theirNonintersectinContours) {
+ // If we contain this contour, it's redundant and we can just remove it
BOOL subjectContainsClip = [self containsContour:theirContour];
if ( subjectContainsClip )
[finalNonintersectingContours removeObject:theirContour];
for (FBBezierContour *contour in finalNonintersectingContours)
[result addContour:contour];
- // Clean up crossings so the graphs can be reused
+ // Clean up crossings so the graphs can be reused, e.g. XOR will reuse graphs.
- (FBBezierGraph *) intersectWithBezierGraph:(FBBezierGraph *)graph
+ // First insert FBEdgeCrossings into both graphs where the graphs cross.
[self insertCrossingsWithBezierGraph:graph];
+ // 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];
+ // 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];
+ // Since we're doing an intersect, assume that most of these non-crossing contours shouldn't be in
NSMutableArray *finalNonintersectingContours = [NSMutableArray arrayWithCapacity:[ourNonintersectingContours count] + [theirNonintersectinContours count]];
- // There are no crossings, which means one contains the other, or they're completely disjoint
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.
BOOL clipContainsSubject = [graph containsContour:ourContour];
if ( clipContainsSubject )
[finalNonintersectingContours addObject:ourContour];
for (FBBezierContour *theirContour in theirNonintersectinContours) {
+ // If we contain theirContour, then the two graphs intersect (logical AND) at theirContour,
+ // so add it to the final result.
BOOL subjectContainsClip = [self containsContour:theirContour];
if ( subjectContainsClip )
[finalNonintersectingContours addObject:theirContour];
for (FBBezierContour *contour in finalNonintersectingContours)
[result addContour:contour];
- // Clean up crossings so the graphs can be reused
+ // Clean up crossings so the graphs can be reused, e.g. XOR will reuse graphs.
- (FBBezierGraph *) differenceWithBezierGraph:(FBBezierGraph *)graph
+ // First insert FBEdgeCrossings into both graphs where the graphs cross.
[self insertCrossingsWithBezierGraph:graph];
+ // 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];
+ // 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];
+ // 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]];
- // There are no crossings, which means one contains the other, or they're completely disjoint
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.
BOOL clipContainsSubject = [graph containsContour:ourContour];
if ( !clipContainsSubject )
[finalNonintersectingContours addObject:ourContour];
for (FBBezierContour *theirContour in theirNonintersectinContours) {
+ // If our graph contains theirContour, then add theirContour as a hole.
BOOL subjectContainsClip = [self containsContour:theirContour];
if ( subjectContainsClip )
[finalNonintersectingContours addObject:theirContour]; // add it as a hole
- (void) markCrossingsAsEntryOrExitWithBezierGraph:(FBBezierGraph *)otherGraph markInside:(BOOL)markInside
+ // Walk each contour in ourself and mark the crossings with each intersecting contour as entering
+ // or exiting the final contour.
for (FBBezierContour *contour in self.contours) {
NSArray *intersectingContours = contour.intersectingContours;
for (FBBezierContour *otherContour in intersectingContours) {
+ // If the other contour is a hole, that's a special case where we flip marking inside/outside.
+ // For example, if we're doing a union, we'd normally mark the outside of contours. But
+ // if we're unioning with a hole, we want to cut into that hole so we mark the inside instead
if ( otherContour.inside == FBContourInsideHole )
[contour markCrossingsAsEntryOrExitWithContour:otherContour markInside:!markInside];
- (FBBezierGraph *) xorWithBezierGraph:(FBBezierGraph *)graph
+ // XOR is done by combing union (OR), intersect (AND) and difference. Specifically
+ // we compute the union of the two graphs, the intersect of them, then subtract
+ // the intersect from the union.
+ // Note that we reuse the resulting graphs, which is why it is important that operations
+ // clean up any crossings when their done, otherwise they could interfere with subsequent
FBBezierGraph *allParts = [self unionWithBezierGraph:graph];
FBBezierGraph *intersectingParts = [self intersectWithBezierGraph:graph];
return [allParts differenceWithBezierGraph:intersectingParts];
- (NSBezierPath *) bezierPath
+ // Convert this graph into a bezier path. This is straightforward, each contour
+ // starting with a move to and each subsequent edge being translated by doing
+ // Be sure to mark the winding rule as even odd, or interior contours (holes)
+ // won't get filled/left alone properly.
NSBezierPath *path = [NSBezierPath bezierPath];
[path setWindingRule:NSEvenOddWindingRule];
+ // Round off all end and control points to integral values
for (FBBezierContour *contour in _contours)
- (void) insertCrossingsWithBezierGraph:(FBBezierGraph *)other
- // Find all intersections and, if they cross the other graph, create crossings for them
+ // 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) {
+ // Find all intersections between these two edges (curves)
NSArray *intersections = [ourEdge.curve intersectionsWithBezierCurve:theirEdge.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 ) {
ourEdge.startShared = YES;
ourEdge.previous.stopShared = YES;
if ( ![self doesEdge:ourEdge crossEdge:theirEdge atIntersection:intersection] )
+ // Add crossings to both graphs for this intersection, and point them at each other
FBEdgeCrossing *ourCrossing = [FBEdgeCrossing crossingWithIntersection:intersection];
FBEdgeCrossing *theirCrossing = [FBEdgeCrossing crossingWithIntersection:intersection];
ourCrossing.counterpart = theirCrossing;
theirCrossing.counterpart = ourCrossing;
[ourEdge addCrossing:ourCrossing];
[theirEdge addCrossing:theirCrossing];
+ // Remove duplicate crossings that can happen at end points of edges
[self removeDuplicateCrossings];
[other removeDuplicateCrossings];
- (void) removeDuplicateCrossings
- // Find any duplicate crossings. These will happen at the endpoints of edges
+ // Find any duplicate crossings. These will happen at the endpoints of edges.
for (FBBezierContour *ourContour in self.contours) {
for (FBContourEdge *ourEdge in ourContour.edges) {
NSArray *crossings = [[ourEdge.crossings copy] autorelease];
for (FBEdgeCrossing *crossing in crossings) {
if ( crossing.isAtStart && crossing.edge.previous.lastCrossing.isAtEnd ) {
+ // Found a duplicate. Remove this crossing and its counterpart
FBEdgeCrossing *counterpart = crossing.counterpart;
[crossing removeFromEdge];
[counterpart removeFromEdge];
if ( crossing.isAtEnd && crossing.edge.next.firstCrossing.isAtStart ) {
+ // Found a duplicate. Remove this crossing and its counterpart
FBEdgeCrossing *counterpart = crossing.edge.next.firstCrossing.counterpart;
[crossing.edge.next.firstCrossing removeFromEdge];
[counterpart removeFromEdge];
- (BOOL) doesEdge:(FBContourEdge *)edge1 crossEdge:(FBContourEdge *)edge2 atIntersection:(FBBezierIntersection *)intersection
- // Handle the main case first
+ // If it's tangent, then it doesn't cross
+ if ( intersection.isTangent )
+ // 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 )
- if ( intersection.isTangent )
// 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
+ // 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 edge1 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
+ // Calculate the four tangents: The two tangents moving away from the intersection point on edge1, the two tangents
+ // moving away from the intersection point on edge2.
NSPoint edge1Tangents[] = { NSZeroPoint, NSZeroPoint };
NSPoint edge2Tangents[] = { NSZeroPoint, NSZeroPoint };
if ( intersection.isAtStartOfCurve1 ) {
edge2Tangents[1] = FBSubtractPoint(intersection.curve2RightBezier.controlPoint1, intersection.curve2RightBezier.endPoint1);
- // Calculate angles between the tangents
+ // Calculate angles for the tangents
CGFloat edge1Angles[] = { PolarAngle(edge1Tangents[0]), PolarAngle(edge1Tangents[1]) };
CGFloat edge2Angles[] = { PolarAngle(edge2Tangents[0]), PolarAngle(edge2Tangents[1]) };
- // Count how many times edge2 angles are between edge1 angles
+ // Count how many times edge2 angles appear between the edge1 angles
FBAngleRange range1 = FBAngleRangeMake(edge1Angles[0], edge1Angles[1]);
NSUInteger rangeCount1 = 0;
if ( FBAngleRangeContainsAngle(range1, edge2Angles[0]) )
if ( FBAngleRangeContainsAngle(range1, edge2Angles[1]) )
+ // Count how many times edge1 angles appear between the edge2 angles
FBAngleRange range2 = FBAngleRangeMake(edge1Angles[1], edge1Angles[0]);
NSUInteger rangeCount2 = 0;
if ( FBAngleRangeContainsAngle(range2, edge2Angles[0]) )
if ( FBAngleRangeContainsAngle(range2, edge2Angles[1]) )
+ // If each pair of angles split the other two, then the edges cross.
return rangeCount1 == 1 && rangeCount2 == 1;
+ // Compute the bounds of the graph by unioning together the bounds of the individual contours
if ( !NSEqualRects(_bounds, NSZeroRect) )
if ( [_contours count] == 0 )
- (FBContourInside) contourInsides:(FBBezierContour *)testContour
+ // Determine if this contour, which should reside in this graph, is a filled region or
+ // a hole. Determine this by casting a ray from one edges of the contour to the outside of
+ // the entire graph. Count how many times the ray intersects a contour in the graph. If it's
+ // an odd number, the test contour resides inside of filled region, meaning it must be a hole.
+ // Otherwise it's "outside" of the graph and creates a filled region.
+ // 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];
for (FBContourEdge *edge in contour.edges) {
NSArray *intersections = [testCurve intersectionsWithBezierCurve:edge.curve];
for (FBBezierIntersection *intersection in intersections) {
- if ( intersection.isTangent )
+ if ( intersection.isTangent ) // don't count tangents
return (intersectCount % 2) == 1 ? FBContourInsideHole : FBContourInsideFilled;
- (BOOL) containsContour:(FBBezierContour *)testContour
+ // Determine if the test contour is inside a filled region of self or not. We do this by
+ // see which, if any, of our contours contains the test contour. If one does, we contain
+ // it only if the contour is filled (a hole would mean the test contour outside of us).
FBBezierContour *container = [self containerForContour:testContour];
return container != nil && container.inside == FBContourInsideFilled;
- (FBBezierContour *) containerForContour:(FBBezierContour *)testContour
+ // Determine the container, if any, for the test contour. We do this by casting a ray from one end of the graph to the other,
+ // and recording the intersections before and after the test contour. If the ray intersects with a contour an odd number of
+ // times on one side, we know it contains the test contour. After determine which contours contain the test contour, we simply
+ // pick the closest one to test contour.
+ // Things get a bit more complicated though. If contour shares and edge the test contour, then it can be impossible to determine
+ // whom contains whom. Or if we hit the test contour at a location where edges joint together (i.e. end points).
+ // For this reason, we sit in a loop passing both horizontal and vertical rays through the graph until we can eliminate the number
+ // of potentially enclosing contours down to 1 or 0. Most times the first ray will find the correct answer, but in some degenerate
+ // cases it will take a few iterations.
static const CGFloat FBRayOverlap = 10.0;
+ // In the beginning all our contours are possible containers for the test contour.
NSMutableArray *containers = [[_contours mutableCopy] autorelease];
+ // Each time through the loop we split the test contour into any increasing amount of pieces
+ // (halves, thirds, quarters, etc) and send a ray along the boundaries. In order to increase
+ // our changes of eliminate all but 1 of the contours, we do both horizontal and vertical rays.
NSUInteger count = MAX(ceilf(NSWidth(testContour.bounds)), ceilf(NSHeight(testContour.bounds)));
for (NSUInteger fraction = 2; fraction <= count; fraction++) {
+ // Send the horizontal rays through the test contour and (possibly) through parts of the graph
CGFloat verticalSpacing = NSHeight(testContour.bounds) / (CGFloat)fraction;
for (CGFloat y = NSMinY(testContour.bounds) + verticalSpacing; y < NSMaxY(testContour.bounds); y += verticalSpacing) {
+ // Construct a line that will reach outside both ends of both the test contour and graph
FBBezierCurve *ray = [FBBezierCurve bezierCurveWithLineStartPoint:NSMakePoint(MIN(NSMinX(self.bounds), NSMinX(testContour.bounds)) - FBRayOverlap, y) endPoint:NSMakePoint(MAX(NSMaxX(self.bounds), NSMaxX(testContour.bounds)) + FBRayOverlap, y)];
+ // Eliminate any contours that aren't containers. It's possible for this method to fail, so check the return
+ BOOL eliminated = [self eliminateContainers:containers thatDontContainContour:testContour usingRay:ray];
+ // Send the vertical rays through the test contour and (possibly) through parts of the graph
+ CGFloat horizontalSpacing = NSWidth(testContour.bounds) / (CGFloat)fraction;
+ for (CGFloat x = NSMinX(testContour.bounds) + horizontalSpacing; x < NSMaxX(testContour.bounds); x += horizontalSpacing) {
+ // Construct a line that will reach outside both ends of both the test contour and graph
+ FBBezierCurve *ray = [FBBezierCurve bezierCurveWithLineStartPoint:NSMakePoint(x, MIN(NSMinY(self.bounds), NSMinY(testContour.bounds)) - FBRayOverlap) endPoint:NSMakePoint(x, MAX(NSMaxY(self.bounds), NSMaxY(testContour.bounds)) + FBRayOverlap)];
+ // Eliminate any contours that aren't containers. It's possible for this method to fail, so check the return
BOOL eliminated = [self eliminateContainers:containers thatDontContainContour:testContour usingRay:ray];
- CGFloat horizontalSpacing = NSWidth(testContour.bounds) / (CGFloat)fraction;
- for (CGFloat x = NSMinX(testContour.bounds) + horizontalSpacing; x < NSMaxX(testContour.bounds); x += horizontalSpacing) {
- FBBezierCurve *ray = [FBBezierCurve bezierCurveWithLineStartPoint:NSMakePoint(x, MIN(NSMinY(self.bounds), NSMinY(testContour.bounds)) - FBRayOverlap) endPoint:NSMakePoint(x, MAX(NSMaxY(self.bounds), NSMaxY(testContour.bounds)) + FBRayOverlap)];
- BOOL eliminated = [self eliminateContainers:containers thatDontContainContour:testContour usingRay:ray];
+ // If we've eliminated all the contours, then nothing contains the test contour, and we're done
if ( [containers count] == 0 )
+ // We were able to eliminate someone, and we're down to one, so we're done. If the eliminateContainers: method
+ // failed, we can't make any assumptions about the contains, so just let it go again.
if ( didEliminate && [containers count] == 1 )
return [containers objectAtIndex:0];
+ // This is a curious case, because by now we've sent rays that went through every integral cordinate of the test contour.
+ // Despite that eliminateContainers: failed each time, meaning one container has a shared edge for each ray test. It is likely
+ // that contour is equal (the same) as the test contour. Return nil, because if it is equal, it doesn't contain.
- (BOOL) findBoundsOfContour:(FBBezierContour *)testContour onRay:(FBBezierCurve *)ray minimum:(NSPoint *)testMinimum maximum:(NSPoint *)testMaximum
+ // Find the bounds of test contour that lie on ray. Simply intersect the ray with test contour. For a horizontal ray, the minimum is the point
+ // with the lowest x value, the maximum with the highest x value. For a vertical ray, use the high and low y values.
BOOL horizontalRay = ray.endPoint1.y == ray.endPoint2.y; // ray has to be a vertical or horizontal line
- // First determine the exterior bounds of testContour on the given ray
+ // First find all the intersections with the ray
NSMutableArray *rayIntersections = [NSMutableArray arrayWithCapacity:9];
for (FBContourEdge *edge in testContour.edges)
[rayIntersections addObjectsFromArray:[ray intersectionsWithBezierCurve:edge.curve]];
if ( [rayIntersections count] == 0 )
return NO; // shouldn't happen
+ // Next go through and find the lowest and highest
FBBezierIntersection *firstRayIntersection = [rayIntersections objectAtIndex:0];
*testMinimum = firstRayIntersection.location;
*testMaximum = *testMinimum;
- (BOOL) findCrossingsOnContainers:(NSArray *)containers onRay:(FBBezierCurve *)ray beforeMinimum:(NSPoint)testMinimum afterMaximum:(NSPoint)testMaximum crossingsBefore:(NSMutableArray *)crossingsBeforeMinimum crossingsAfter:(NSMutableArray *)crossingsAfterMaximum
+ // Find intersections where the ray intersects the possible containers, before the minimum point, or after the maximum point. Store these
+ // as FBEdgeCrossings in the out parameters.
BOOL horizontalRay = ray.endPoint1.y == ray.endPoint2.y; // ray has to be a vertical or horizontal line
+ // Walk through each possible container, one at a time and see where it intersects
NSMutableArray *ambiguousCrossings = [NSMutableArray arrayWithCapacity:10];
for (FBBezierContour *container in containers) {
for (FBContourEdge *containerEdge in container.edges) {
+ // See where the ray intersects this particular edge
NSArray *intersections = [ray intersectionsWithBezierCurve:containerEdge.curve];
for (FBBezierIntersection *intersection in intersections) {
if ( intersection.isTangent )
+ continue; // tangents don't count
+ // If the ray intersects one of the contours at a joint (end point), then we won't be able
+ // to make any accurate conclusions, so bail now, and say we failed.
if ( intersection.isAtEndPointOfCurve2 )
- // only examine those intersections outside of or on testContour
+ // If the point likes inside the min and max bounds specified, just skip over it. We only want to remember
+ // the intersections that fall on or outside of the min and max.
if ( horizontalRay && intersection.location.x < testMaximum.x && intersection.location.x > testMinimum.x )
else if ( !horizontalRay && intersection.location.y < testMaximum.y && intersection.location.y > testMinimum.y )
+ // Creat a crossing for it so we know what edge it is associated with. Don't insert it into a graph or anything though.
FBEdgeCrossing *crossing = [FBEdgeCrossing crossingWithIntersection:intersection];
crossing.edge = containerEdge;
- // Special case if the bounds are just a point, and this crossing is on that point
+ // Special case if the bounds are just a point, and this crossing is on that point. In that case
+ // it could fall on either side, and we'll need to do some special processing on it later. For now,
+ // remember it, and move on to the next intersection.
if ( NSEqualPoints(testMaximum, testMinimum) && NSEqualPoints(testMaximum, intersection.location) ) {
[ambiguousCrossings addObject:crossing];
+ // This crossing falls outse the bounds, so add it to the appropriate array
if ( horizontalRay && intersection.location.x <= testMinimum.x )
[crossingsBeforeMinimum addObject:crossing];
else if ( !horizontalRay && intersection.location.y <= testMinimum.y )
+ // Handle any intersects that are ambigious. i.e. the min and max are one point, and the intersection is on that point.
for (FBEdgeCrossing *ambiguousCrossing in ambiguousCrossings) {
+ // See how many times the given contour crosses on each side. Add the ambigious crossing to the side that has less,
+ // in hopes of balancing it out.
NSUInteger numberOfTimesContourAppearsBefore = [self numberOfTimesContour:ambiguousCrossing.edge.contour appearsInCrossings:crossingsBeforeMinimum];
NSUInteger numberOfTimesContourAppearsAfter = [self numberOfTimesContour:ambiguousCrossing.edge.contour appearsInCrossings:crossingsAfterMaximum];
if ( numberOfTimesContourAppearsBefore < numberOfTimesContourAppearsAfter )
- (NSUInteger) numberOfTimesContour:(FBBezierContour *)contour appearsInCrossings:(NSArray *)crossings
+ // Count how many times a contour appears in a crossings array
for (FBEdgeCrossing *crossing in crossings) {
if ( crossing.edge.contour == contour )
- (NSArray *) minimumCrossings:(NSArray *)crossings onRay:(FBBezierCurve *)ray
+ // Find the crossings with the minimum x or y values. If it's a horizontal ray
+ // pick the minimum x values, if vertical, minimum y values. It's possible
+ // to return more than one crossing if they share the minimum value.
if ( [crossings count] == 0 )
BOOL horizontalRay = ray.endPoint1.y == ray.endPoint2.y; // ray has to be a vertical or horizontal line
+ // Start with the first crossing as the minimum value to compare all others with
NSMutableArray *minimums = [NSMutableArray arrayWithCapacity:[crossings count]];
FBEdgeCrossing *firstCrossing = [crossings objectAtIndex:0];
NSPoint minimum = firstCrossing.location;
for (FBEdgeCrossing *crossing in crossings) {
+ // If the current value is less than the minimum, replace it. If it is equal
+ // to the minimum value, add it to the array.
if ( crossing.location.x < minimum.x ) {
minimum = crossing.location;
- (NSArray *) maximumCrossings:(NSArray *)crossings onRay:(FBBezierCurve *)ray
+ // Find the crossings with the maximum x or y values. If it's a horizontal ray
+ // pick the maximum x values, if vertical, maximum y values. It's possible
+ // to return more than one crossing if they share the maximum value.
if ( [crossings count] == 0 )
BOOL horizontalRay = ray.endPoint1.y == ray.endPoint2.y; // ray has to be a vertical or horizontal line
+ // Start with the first crossing as the maximum value to compare all others with
NSMutableArray *maximums = [NSMutableArray arrayWithCapacity:[crossings count]];
FBEdgeCrossing *firstCrossing = [crossings objectAtIndex:0];
NSPoint maximum = firstCrossing.location;
for (FBEdgeCrossing *crossing in crossings) {
+ // If the current value is greater than the maximum, replace it. If it is equal
+ // to the maximum value, add it to the array.
if ( crossing.location.x > maximum.x ) {
maximum = crossing.location;
[maximums removeAllObjects];
- (BOOL) eliminateContainers:(NSMutableArray *)containers thatDontContainContour:(FBBezierContour *)testContour usingRay:(FBBezierCurve *)ray
+ // This method attempts to eliminate all or all but one of the containers that might contain test contour, using the ray specified.
// First determine the exterior bounds of testContour on the given ray
NSPoint testMinimum = NSZeroPoint;
NSPoint testMaximum = NSZeroPoint;
- // Remove containers that appear an even number of times on either side
+ // Remove containers that appear an even number of times on either side, because by the even/odd rule
+ // they can't contain test contour.
[self removeContoursThatDontContain:crossingsBeforeMinimum];
[self removeContoursThatDontContain:crossingsAfterMaximum];
- // Find the container(s) that are the closest
+ // Find the container(s) that are the closest to the test contour, while still being outside it
[crossingsBeforeMinimum setArray:[self maximumCrossings:crossingsBeforeMinimum onRay:ray]];
[crossingsAfterMaximum setArray:[self minimumCrossings:crossingsAfterMaximum onRay:ray]];
- (NSArray *) contoursFromCrossings:(NSArray *)crossings
+ // Determine all the unique contours in the array of crossings
NSMutableArray *contours = [NSMutableArray arrayWithCapacity:[crossings count]];
for (FBEdgeCrossing *crossing in crossings) {
if ( ![contours containsObject:crossing.edge.contour] )
- (void) removeContourCrossings:(NSMutableArray *)crossings1 thatDontAppearIn:(NSMutableArray *)crossings2
+ // If a contour appears in crossings1, but not crossings2, remove all the associated crossings from
NSMutableArray *containersToRemove = [NSMutableArray arrayWithCapacity:[crossings1 count]];
for (FBEdgeCrossing *crossingToTest in crossings1) {
FBBezierContour *containerToTest = crossingToTest.edge.contour;
+ // See if this contour exists in the other array
for (FBEdgeCrossing *crossing in crossings2) {
if ( crossing.edge.contour == containerToTest ) {
+ // If it doesn't exist in our counterpart, mark it for death
[containersToRemove addObject:containerToTest];
- (void) removeContoursThatDontContain:(NSMutableArray *)crossings
+ // Remove contours that cross the ray an even number of times. By the even/odd rule this means
+ // they can't contain the test contour.
NSMutableArray *containersToRemove = [NSMutableArray arrayWithCapacity:[crossings count]];
for (FBEdgeCrossing *crossingToTest in crossings) {
+ // For this contour, count how many times it appears in the crossings array
FBBezierContour *containerToTest = crossingToTest.edge.contour;
for (FBEdgeCrossing *crossing in crossings) {
if ( crossing.edge.contour == containerToTest )
+ // If it's not an odd number of times, it doesn't contain the test contour, so mark it for death
[containersToRemove addObject:containerToTest];
- (void) removeCrossings:(NSMutableArray *)crossings forContours:(NSArray *)containersToRemove
+ // A helper method that goes through and removes all the crossings that appear on the specified
+ // First walk through and identify which crossings to remove
NSMutableArray *crossingsToRemove = [NSMutableArray arrayWithCapacity:[crossings count]];
for (FBBezierContour *contour in containersToRemove) {
for (FBEdgeCrossing *crossing in crossings) {
[crossingsToRemove addObject:crossing];
+ // Now walk through and remove the crossings
for (FBEdgeCrossing *crossing in crossingsToRemove)
[crossings removeObject:crossing];
- (FBEdgeCrossing *) firstUnprocessedCrossing
+ // Find the first crossing in our graph that has yet to be processed by the bezierGraphFromIntersections
for (FBBezierContour *contour in _contours) {
for (FBContourEdge *edge in contour.edges) {
for (FBEdgeCrossing *crossing in edge.crossings) {
- (FBBezierGraph *) bezierGraphFromIntersections
+ // This method walks the current graph, starting at the crossings, and outputs the final contours
+ // of the parts of the graph that actually intersect. The general algorithm is: start an crossing
+ // we haven't seen before. If it's marked as entry, start outputing edges moving forward (i.e. using edge.next)
+ // until another crossing is hit. (If a crossing is marked as exit, start outputting edges move backwards, using
+ // edge.previous.) Once the next crossing is hit, switch to the crossing's counter part in the other graph,
+ // and process it in the same way. Continue this until we reach a crossing that's been processed.
FBBezierGraph *result = [FBBezierGraph bezierGraph];
+ // Find the first crossing to start one
FBEdgeCrossing *crossing = [self firstUnprocessedCrossing];
while ( crossing != nil ) {
- // This is the start of a contour
+ // This is the start of a contour, so create one
FBBezierContour *contour = [[[FBBezierContour alloc] init] autorelease];
[result addContour:contour];
- // keep going until run into processed crossing
+ // Keep going until we run into a crossing we've seen before.
while ( !crossing.isProcessed ) {
- crossing.processed = YES;
+ crossing.processed = YES; // ...and we've just seen this one
if ( crossing.isEntry ) {
// Keep going to next until meet a crossing
[contour addCurveFrom:crossing to:crossing.next];
if ( crossing.next == nil ) {
- // we hit the end of the edge without finding another crossing, so go find the next crossing
+ // We hit the end of the edge without finding another crossing, so go find the next crossing
FBContourEdge *edge = crossing.edge.next;
while ( [edge.crossings count] == 0 ) {
// output this edge whole
- // We have an edge that has at least one intersection
+ // We have an edge that has at least one crossing
crossing = edge.firstCrossing;
- [contour addCurveFrom:nil to:crossing];
+ [contour addCurveFrom:nil to:crossing]; // add the curve up to the crossing
- crossing = crossing.next;
+ crossing = crossing.next; // this edge has a crossing, so just move to it
// Keep going to previous until meet a crossing
[contour addReverseCurveFrom:crossing.previous to:crossing];
- // We have an edge that has at least one intersection
+ // We have an edge that has at least one edge
crossing = edge.lastCrossing;
- [contour addReverseCurveFrom:crossing to:nil];
+ [contour addReverseCurveFrom:crossing to:nil]; // add the curve up to the crossing
crossing = crossing.previous;
- // Switch over to counterpart
+ // Switch over to counterpart in the other graph
crossing.processed = YES;
crossing = crossing.counterpart;
- // See if there's another contour
+ // See if there's another contour that we need to handle
crossing = [self firstUnprocessedCrossing];
+ // Crossings only make sense for the intersection between two specific graphs. In order for this
+ // graph to be usable in the future, remove all the crossings
for (FBBezierContour *contour in _contours)
for (FBContourEdge *edge in contour.edges)
[edge removeAllCrossings];
- (void) addContour:(FBBezierContour *)contour
+ // Add a contour to ouselves, and force the bounds to be recalculated
[_contours addObject:contour];
- (NSArray *) nonintersectingContours
+ // Find all the contours that have no crossings on them.
NSMutableArray *contours = [NSMutableArray arrayWithCapacity:[_contours count]];
for (FBBezierContour *contour in self.contours) {
if ( [contour.intersectingContours count] == 0 )