1. Andy Finnell
  2. VectorBoolean

Commits

Andy Finnell  committed c26c7be

testing harness for boolean operations

  • Participants
  • Parent commits 95eccbe
  • Branches default

Comments (0)

Files changed (20)

File LICENSE.txt

View file
+Copyright (c) 2011 Andrew Finnell
+
+Permission is hereby granted, free of charge, to any person
+obtaining a copy of this software and associated documentation
+files (the “Software”), to deal in the Software without
+restriction, including without limitation the rights to use,
+copy, modify, merge, publish, distribute, sublicense, and/or sell
+copies of the Software, and to permit persons to whom the
+Software is furnished to do so, subject to the following
+conditions:
+
+The above copyright notice and this permission notice shall be
+included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+OTHER DEALINGS IN THE SOFTWARE.

File VectorBoolean.xcodeproj/project.pbxproj

View file
 	objects = {
 
 /* Begin PBXBuildFile section */
+		A11131E513960B9D00C9395C /* NSBezierPath+Boolean.m in Sources */ = {isa = PBXBuildFile; fileRef = A11131E413960B9D00C9395C /* NSBezierPath+Boolean.m */; };
 		A1C48B381395FA380043E2C7 /* Cocoa.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = A1C48B371395FA380043E2C7 /* Cocoa.framework */; };
 		A1C48B421395FA390043E2C7 /* InfoPlist.strings in Resources */ = {isa = PBXBuildFile; fileRef = A1C48B401395FA390043E2C7 /* InfoPlist.strings */; };
 		A1C48B451395FA390043E2C7 /* main.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B441395FA390043E2C7 /* main.m */; };
 		A1C48B4B1395FA390043E2C7 /* MyDocument.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B4A1395FA390043E2C7 /* MyDocument.m */; };
 		A1C48B4E1395FA390043E2C7 /* MyDocument.xib in Resources */ = {isa = PBXBuildFile; fileRef = A1C48B4C1395FA390043E2C7 /* MyDocument.xib */; };
 		A1C48B511395FA390043E2C7 /* MainMenu.xib in Resources */ = {isa = PBXBuildFile; fileRef = A1C48B4F1395FA390043E2C7 /* MainMenu.xib */; };
+		A1C48B5F1395FAE20043E2C7 /* Geometry.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B581395FAE10043E2C7 /* Geometry.m */; };
+		A1C48B601395FAE20043E2C7 /* NSBezierPath+FitCurve.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B5A1395FAE10043E2C7 /* NSBezierPath+FitCurve.m */; };
+		A1C48B611395FAE20043E2C7 /* NSBezierPath+Simplify.m in Sources */ = {isa = PBXBuildFile; fileRef = A1C48B5C1395FAE10043E2C7 /* NSBezierPath+Simplify.m */; };
+		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 */; };
 /* End PBXBuildFile section */
 
 /* Begin PBXFileReference section */
+		A11131E313960B9D00C9395C /* NSBezierPath+Boolean.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "NSBezierPath+Boolean.h"; sourceTree = "<group>"; };
+		A11131E413960B9D00C9395C /* NSBezierPath+Boolean.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "NSBezierPath+Boolean.m"; sourceTree = "<group>"; };
 		A1C48B331395FA380043E2C7 /* VectorBoolean.app */ = {isa = PBXFileReference; explicitFileType = wrapper.application; includeInIndex = 0; path = VectorBoolean.app; sourceTree = BUILT_PRODUCTS_DIR; };
 		A1C48B371395FA380043E2C7 /* Cocoa.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = Cocoa.framework; path = System/Library/Frameworks/Cocoa.framework; sourceTree = SDKROOT; };
 		A1C48B3A1395FA390043E2C7 /* AppKit.framework */ = {isa = PBXFileReference; lastKnownFileType = wrapper.framework; name = AppKit.framework; path = System/Library/Frameworks/AppKit.framework; sourceTree = SDKROOT; };
 		A1C48B4A1395FA390043E2C7 /* MyDocument.m */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.c.objc; path = MyDocument.m; sourceTree = "<group>"; };
 		A1C48B4D1395FA390043E2C7 /* en */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = en; path = en.lproj/MyDocument.xib; sourceTree = "<group>"; };
 		A1C48B501395FA390043E2C7 /* en */ = {isa = PBXFileReference; lastKnownFileType = file.xib; name = en; path = en.lproj/MainMenu.xib; sourceTree = "<group>"; };
+		A1C48B571395FAE00043E2C7 /* Geometry.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = Geometry.h; sourceTree = "<group>"; };
+		A1C48B581395FAE10043E2C7 /* Geometry.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = Geometry.m; sourceTree = "<group>"; };
+		A1C48B591395FAE10043E2C7 /* NSBezierPath+FitCurve.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "NSBezierPath+FitCurve.h"; sourceTree = "<group>"; };
+		A1C48B5A1395FAE10043E2C7 /* NSBezierPath+FitCurve.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "NSBezierPath+FitCurve.m"; sourceTree = "<group>"; };
+		A1C48B5B1395FAE10043E2C7 /* NSBezierPath+Simplify.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "NSBezierPath+Simplify.h"; sourceTree = "<group>"; };
+		A1C48B5C1395FAE10043E2C7 /* NSBezierPath+Simplify.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "NSBezierPath+Simplify.m"; sourceTree = "<group>"; };
+		A1C48B5D1395FAE10043E2C7 /* NSBezierPath+Utilities.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "NSBezierPath+Utilities.h"; sourceTree = "<group>"; };
+		A1C48B5E1395FAE20043E2C7 /* NSBezierPath+Utilities.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = "NSBezierPath+Utilities.m"; sourceTree = "<group>"; };
+		A1C48B63139602480043E2C7 /* CanvasView.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = CanvasView.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>"; };
 /* End PBXFileReference section */
 
 /* Begin PBXFrameworksBuildPhase section */
 			children = (
 				A1C48B491395FA390043E2C7 /* MyDocument.h */,
 				A1C48B4A1395FA390043E2C7 /* MyDocument.m */,
+				A1C48B63139602480043E2C7 /* CanvasView.h */,
+				A1C48B64139602480043E2C7 /* CanvasView.m */,
+				A1C48B66139602800043E2C7 /* Canvas.h */,
+				A1C48B67139602810043E2C7 /* Canvas.m */,
+				A1C48B571395FAE00043E2C7 /* Geometry.h */,
+				A1C48B581395FAE10043E2C7 /* Geometry.m */,
+				A11131E313960B9D00C9395C /* NSBezierPath+Boolean.h */,
+				A11131E413960B9D00C9395C /* NSBezierPath+Boolean.m */,
+				A1C48B591395FAE10043E2C7 /* NSBezierPath+FitCurve.h */,
+				A1C48B5A1395FAE10043E2C7 /* NSBezierPath+FitCurve.m */,
+				A1C48B5B1395FAE10043E2C7 /* NSBezierPath+Simplify.h */,
+				A1C48B5C1395FAE10043E2C7 /* NSBezierPath+Simplify.m */,
+				A1C48B5D1395FAE10043E2C7 /* NSBezierPath+Utilities.h */,
+				A1C48B5E1395FAE20043E2C7 /* NSBezierPath+Utilities.m */,
 				A1C48B4C1395FA390043E2C7 /* MyDocument.xib */,
 				A1C48B4F1395FA390043E2C7 /* MainMenu.xib */,
 				A1C48B3E1395FA390043E2C7 /* Supporting Files */,
 			files = (
 				A1C48B451395FA390043E2C7 /* main.m in Sources */,
 				A1C48B4B1395FA390043E2C7 /* MyDocument.m in Sources */,
+				A1C48B5F1395FAE20043E2C7 /* Geometry.m in Sources */,
+				A1C48B601395FAE20043E2C7 /* NSBezierPath+FitCurve.m in Sources */,
+				A1C48B611395FAE20043E2C7 /* NSBezierPath+Simplify.m in Sources */,
+				A1C48B621395FAE20043E2C7 /* NSBezierPath+Utilities.m in Sources */,
+				A1C48B65139602480043E2C7 /* CanvasView.m in Sources */,
+				A1C48B68139602820043E2C7 /* Canvas.m in Sources */,
+				A11131E513960B9D00C9395C /* NSBezierPath+Boolean.m in Sources */,
 			);
 			runOnlyForDeploymentPostprocessing = 0;
 		};
 				A1C48B561395FA390043E2C7 /* Release */,
 			);
 			defaultConfigurationIsVisible = 0;
+			defaultConfigurationName = Release;
 		};
 /* End XCConfigurationList section */
 	};

File VectorBoolean/Canvas.h

View file
+//
+//  Canvas.h
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 5/31/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Foundation/Foundation.h>
+
+
+@interface Canvas : NSObject {
+    NSMutableArray *_paths;    
+}
+
+- (void) addPath:(NSBezierPath *)path withColor:(NSColor *)color;
+- (void) clear;
+
+- (NSUInteger) numberOfPaths;
+- (NSBezierPath *) pathAtIndex:(NSUInteger)index;
+
+- (void) drawRect:(NSRect)dirtyRect;
+
+@end

File VectorBoolean/Canvas.m

View file
+//
+//  Canvas.m
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 5/31/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "Canvas.h"
+
+
+@implementation Canvas
+
+- (id)init
+{
+    self = [super init];
+    if (self) {
+        _paths = [[NSMutableArray alloc] initWithCapacity:3];
+    }
+    
+    return self;
+}
+
+- (void)dealloc
+{
+    [_paths release];
+
+    [super dealloc];
+}
+
+- (void) addPath:(NSBezierPath *)path withColor:(NSColor *)color
+{
+    NSDictionary *object = [NSDictionary dictionaryWithObjectsAndKeys:path, @"path", color, @"color", nil];
+    [_paths addObject:object];
+}
+
+- (NSUInteger) numberOfPaths
+{
+    return [_paths count];
+}
+
+- (NSBezierPath *) pathAtIndex:(NSUInteger)index
+{
+    NSDictionary *object = [_paths objectAtIndex:index];
+    return [object objectForKey:@"path"];
+}
+
+- (void) clear
+{
+    [_paths removeAllObjects];
+}
+
+- (void) drawRect:(NSRect)dirtyRect
+{
+    // Draw on a background
+    [[NSColor whiteColor] set];
+    [NSBezierPath fillRect:dirtyRect];
+    
+    // Draw on the objects
+    for (NSDictionary *object in _paths) {
+        NSColor *color = [object objectForKey:@"color"];
+        NSBezierPath *path = [object objectForKey:@"path"];
+        [color set];
+        [path fill];
+    }    
+}
+
+@end

File VectorBoolean/CanvasView.h

View file
+//
+//  CanvasView.h
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 5/31/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Cocoa/Cocoa.h>
+
+@class Canvas;
+
+@interface CanvasView : NSView {
+    Canvas *_canvas;    
+}
+
+@property (readonly) Canvas *canvas;
+
+@end

File VectorBoolean/CanvasView.m

View file
+//
+//  CanvasView.m
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 5/31/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "CanvasView.h"
+#import "Canvas.h"
+
+
+@implementation CanvasView
+
+@synthesize canvas=_canvas;
+
+- (id)initWithFrame:(NSRect)frame
+{
+    self = [super initWithFrame:frame];
+    if (self) {
+        _canvas = [[Canvas alloc] init];
+    }
+    
+    return self;
+}
+
+- (void)dealloc
+{
+    [_canvas release];
+
+    [super dealloc];
+}
+
+- (void)drawRect:(NSRect)dirtyRect
+{
+    [_canvas drawRect:dirtyRect];
+}
+
+@end

File VectorBoolean/Geometry.h

View file
+//
+//  Geometry.h
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/28/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Cocoa/Cocoa.h>
+
+
+CGFloat FBDistanceBetweenPoints(NSPoint point1, NSPoint point2);
+CGFloat FBDistancePointToLine(NSPoint point, NSPoint lineStartPoint, NSPoint lineEndPoint);
+
+NSPoint FBAddPoint(NSPoint point1, NSPoint point2);
+NSPoint FBScalePoint(NSPoint point, CGFloat scale);
+NSPoint FBUnitScalePoint(NSPoint point, CGFloat scale);
+NSPoint FBSubtractPoint(NSPoint point1, NSPoint point2);
+CGFloat FBDotMultiplyPoint(NSPoint point1, NSPoint point2);
+CGFloat FBPointLength(NSPoint point);
+CGFloat FBPointSquaredLength(NSPoint point);
+NSPoint FBNormalizePoint(NSPoint point);
+NSPoint FBNegatePoint(NSPoint point);

File VectorBoolean/Geometry.m

View file
+//
+//  Geometry.m
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/28/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "Geometry.h"
+
+
+CGFloat FBDistanceBetweenPoints(NSPoint point1, NSPoint point2)
+{
+    CGFloat xDelta = point2.x - point1.x;
+    CGFloat yDelta = point2.y - point1.y;
+    return sqrtf(xDelta * xDelta + yDelta * yDelta);
+}
+
+CGFloat FBDistancePointToLine(NSPoint point, NSPoint lineStartPoint, NSPoint lineEndPoint)
+{
+    CGFloat lineLength = FBDistanceBetweenPoints(lineStartPoint, lineEndPoint);
+    if ( lineLength == 0 )
+        return 0;
+    CGFloat u = ((point.x - lineStartPoint.x) * (lineEndPoint.x - lineStartPoint.x) + (point.y - lineStartPoint.y) * (lineEndPoint.y - lineStartPoint.y)) / (lineLength * lineLength);
+    NSPoint intersectionPoint = NSMakePoint(lineStartPoint.x + u * (lineEndPoint.x - lineStartPoint.x), lineStartPoint.y + u * (lineEndPoint.y - lineStartPoint.y));
+    return FBDistanceBetweenPoints(point, intersectionPoint);
+}
+
+NSPoint FBAddPoint(NSPoint point1, NSPoint point2)
+{
+    return NSMakePoint(point1.x + point2.x, point1.y + point2.y);
+}
+
+NSPoint FBUnitScalePoint(NSPoint point, CGFloat scale)
+{
+    NSPoint result = point;
+    CGFloat length = FBPointLength(point);
+    if ( length != 0.0 ) {
+        result.x *= scale/length;
+        result.y *= scale/length;
+    }
+    return result;
+}
+
+NSPoint FBScalePoint(NSPoint point, CGFloat scale)
+{
+    return NSMakePoint(point.x * scale, point.y * scale);
+}
+
+CGFloat FBDotMultiplyPoint(NSPoint point1, NSPoint point2)
+{
+    return point1.x * point2.x + point1.y * point2.y;
+}
+
+NSPoint FBSubtractPoint(NSPoint point1, NSPoint point2)
+{
+    return NSMakePoint(point1.x - point2.x, point1.y - point2.y);
+}
+
+CGFloat FBPointLength(NSPoint point)
+{
+    return sqrtf((point.x * point.x) + (point.y * point.y));
+}
+
+CGFloat FBPointSquaredLength(NSPoint point)
+{
+    return (point.x * point.x) + (point.y * point.y);
+}
+
+NSPoint FBNormalizePoint(NSPoint point)
+{
+    NSPoint result = point;
+    CGFloat length = FBPointLength(point);
+    if ( length != 0.0 ) {
+        result.x /= length;
+        result.y /= length;
+    }
+    return result;
+}
+
+NSPoint FBNegatePoint(NSPoint point)
+{
+    return NSMakePoint(-point.x, -point.y);
+}

File VectorBoolean/MyDocument.h

View file
 
 #import <Cocoa/Cocoa.h>
 
+@class CanvasView;
+
 @interface MyDocument : NSDocument {
-@private
+    IBOutlet CanvasView *_view;
 }
 
+- (IBAction) onReset:(id)sender;
+- (IBAction) onUnion:(id)sender;
+- (IBAction) onIntersect:(id)sender;
+- (IBAction) onDifference:(id)sender; // Punch
+- (IBAction) onJoin:(id)sender; // XOR
+
 @end

File VectorBoolean/MyDocument.m

View file
 //
 
 #import "MyDocument.h"
+#import "CanvasView.h"
+#import "Canvas.h"
+#import "NSBezierPath+Boolean.h"
 
 @implementation MyDocument
 
 {
     [super windowControllerDidLoadNib:aController];
     // Add any code here that needs to be executed once the windowController has loaded the document's window.
+    
+    [self onReset:nil];
 }
 
 - (NSData *)dataOfType:(NSString *)typeName error:(NSError **)outError {
     return YES;
 }
 
+- (IBAction) onReset:(id)sender
+{
+    [_view.canvas clear];
+    
+    NSBezierPath *rectangle = [NSBezierPath bezierPath];
+    [rectangle moveToPoint:NSMakePoint(50, 50)];
+    [rectangle lineToPoint:NSMakePoint(350, 50)];
+    [rectangle lineToPoint:NSMakePoint(350, 250)];
+    [rectangle lineToPoint:NSMakePoint(50, 250)];
+    [rectangle lineToPoint:NSMakePoint(50, 50)];
+    [_view.canvas addPath:rectangle withColor:[NSColor blueColor]];
+    
+    NSBezierPath *circle = [NSBezierPath bezierPath];
+    static const CGFloat FBMagicNumber = 0.55228475;
+    CGFloat controlPointLength = 125 * FBMagicNumber;
+    [circle moveToPoint:NSMakePoint(230, 240)];
+    [circle curveToPoint:NSMakePoint(355, 365) controlPoint1:NSMakePoint(230, 240 + controlPointLength) controlPoint2:NSMakePoint(355 - controlPointLength, 365)];
+    [circle curveToPoint:NSMakePoint(480, 240) controlPoint1:NSMakePoint(355 + controlPointLength, 365) controlPoint2:NSMakePoint(480, 240 + controlPointLength)];
+    [circle curveToPoint:NSMakePoint(355, 115) controlPoint1:NSMakePoint(480, 240 - controlPointLength) controlPoint2:NSMakePoint(355 + controlPointLength, 115)];
+    [circle curveToPoint:NSMakePoint(230, 240) controlPoint1:NSMakePoint(355 - controlPointLength, 115) controlPoint2:NSMakePoint(230, 240 - controlPointLength)];
+    [_view.canvas addPath:circle withColor:[NSColor redColor]];
+
+    [_view setNeedsDisplay:YES];
+}
+
+- (IBAction) onUnion:(id)sender
+{
+    [self onReset:sender];
+    
+    NSBezierPath *result = [[_view.canvas pathAtIndex:0] fb_union:[_view.canvas pathAtIndex:1]];
+    [_view.canvas clear];
+    [_view.canvas addPath:result withColor:[NSColor blueColor]];
+}
+
+- (IBAction) onIntersect:(id)sender
+{
+    [self onReset:sender];
+    
+    NSBezierPath *result = [[_view.canvas pathAtIndex:0] fb_intersect:[_view.canvas pathAtIndex:1]];
+    [_view.canvas clear];
+    [_view.canvas addPath:result withColor:[NSColor blueColor]];
+}
+
+- (IBAction) onDifference:(id)sender // Punch
+{
+    [self onReset:sender];
+    
+    NSBezierPath *result = [[_view.canvas pathAtIndex:0] fb_difference:[_view.canvas pathAtIndex:1]];
+    [_view.canvas clear];
+    [_view.canvas addPath:result withColor:[NSColor blueColor]];
+}
+
+- (IBAction) onJoin:(id)sender // XOR
+{
+    [self onReset:sender];
+    
+    NSBezierPath *result = [[_view.canvas pathAtIndex:0] fb_xor:[_view.canvas pathAtIndex:1]];
+    [_view.canvas clear];
+    [_view.canvas addPath:result withColor:[NSColor blueColor]];
+}
+
 @end

File VectorBoolean/NSBezierPath+Boolean.h

View file
+//
+//  NSBezierPath+Boolean.h
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 5/31/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Cocoa/Cocoa.h>
+
+
+@interface NSBezierPath (Boolean)
+
+- (NSBezierPath *) fb_union:(NSBezierPath *)path;
+- (NSBezierPath *) fb_intersect:(NSBezierPath *)path;
+- (NSBezierPath *) fb_difference:(NSBezierPath *)path;
+- (NSBezierPath *) fb_xor:(NSBezierPath *)path;
+
+@end

File VectorBoolean/NSBezierPath+Boolean.m

View file
+//
+//  NSBezierPath+Boolean.m
+//  VectorBoolean
+//
+//  Created by Andrew Finnell on 5/31/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "NSBezierPath+Boolean.h"
+
+
+@implementation NSBezierPath (Boolean)
+
+- (NSBezierPath *) fb_union:(NSBezierPath *)path
+{
+    return self;
+}
+
+- (NSBezierPath *) fb_intersect:(NSBezierPath *)path
+{
+    return self;
+}
+
+- (NSBezierPath *) fb_difference:(NSBezierPath *)path
+{
+    return self;
+}
+
+- (NSBezierPath *) fb_xor:(NSBezierPath *)path
+{
+    return self;
+}
+
+@end

File VectorBoolean/NSBezierPath+FitCurve.h

View file
+//
+//  NSBezierPath+FitCurve.h
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/28/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Cocoa/Cocoa.h>
+
+
+@interface NSBezierPath (FitCurve)
+
+- (NSBezierPath *) fb_fitCurve:(CGFloat)errorThreshold;
+
+@end

File VectorBoolean/NSBezierPath+FitCurve.m

View file
+//
+//  NSBezierPath+FitCurve.m
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/28/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "NSBezierPath+FitCurve.h"
+#import "NSBezierPath+Utilities.h"
+#import "Geometry.h"
+#import "math.h"
+
+// Algorithm implemented here is the one described in "An Algorithm for Automatically Fitting Digitized Curves"
+//  by Philip J. Schneider contained in the book Graphics Gems
+
+static const NSUInteger FitCurveMaximumReparameterizes = 4;
+
+static CGFloat Determinant(CGFloat matrix1[2], CGFloat matrix2[2])
+{
+    return matrix1[0] * matrix2[1] - matrix1[1] * matrix2[0];
+}
+
+// The following are 3rd degree Bertstein polynomials. They all have
+//  the same formula:
+//
+//  B[i](input) = (3! / ((3-i)! * i!)) * input^i * (1 - input) ^ (3 - i)
+//
+//  however the functions below have been optimized for their value of i.
+static CGFloat Bernstein0(CGFloat input)
+{
+    return powf(1.0 - input, 3);
+}
+
+static CGFloat Bernstein1(CGFloat input)
+{
+    return 3 * input * powf(1.0 - input, 2);
+}
+
+static CGFloat Bernstein2(CGFloat input)
+{
+    return 3 * powf(input, 2) * (1.0 - input);
+}
+
+static CGFloat Bernstein3(CGFloat input)
+{
+    return powf(input, 3);
+}
+
+static NSPoint BezierWithPoints(NSUInteger degree, NSPoint *bezierPoints, CGFloat parameter)
+{
+    // Calculate a point on the bezier curve passed in, specifically the point at parameter.
+    //  We could just plug parameter into the Q(t) formula shown in the fb_fitBezierInRange: comments.
+    //  However, that method isn't numerically stable, meaning it amplifies any errors, which is bad
+    //  seeing we're using floating point numbers with limited precision. Instead we'll use
+    //  De Casteljau's algorithm.
+    //
+    // See: http://www.cs.mtu.edu/~shene/COURSES/cs3621/NOTES/spline/Bezier/de-casteljau.html
+    //  for an explaination of De Casteljau's algorithm.
+    
+    // With this algorithm we start out with the points in the bezier path.    
+    NSPoint points[4] = {};
+    for (NSUInteger i = 0; i <= degree; i++)
+        points[i] = bezierPoints[i];
+    
+    for (NSUInteger k = 1; k <= degree; k++) {
+        for (NSUInteger i = 0; i <= (degree - k); i++) {
+            points[i].x = (1.0 - parameter) * points[i].x + parameter * points[i + 1].x;
+            points[i].y = (1.0 - parameter) * points[i].y + parameter * points[i + 1].y;            
+        }
+    }
+    
+    return points[0]; // we'll end up with just one point, which is handy, 'cause that's what we want
+}
+
+static NSPoint Bezier(NSUInteger degree, NSBezierPath *bezier, CGFloat parameter)
+{
+    // With this algorithm we start out with the points in the bezier path. We assume the bezier
+    //  path is a move to and a curve to
+    NSBezierElement element1 = [bezier fb_elementAtIndex:0];
+    NSBezierElement element2 = [bezier fb_elementAtIndex:1];
+    NSPoint bezierPoints[4] = {element1.point, element2.controlPoints[0], element2.controlPoints[1], element2.point};
+    
+    return BezierWithPoints(degree, bezierPoints, parameter);
+}
+
+static CGFloat NewtonsMethod(NSBezierPath *bezier, NSPoint point, CGFloat parameter)
+{
+    // Use Newton's Method to refine our parameter. In general, that formula is:
+    //
+    //  parameter = parameter - f(parameter) / f'(parameter)
+    //
+    // In our case:
+    //
+    //  f(parameter) = (Q(parameter) - point) * Q'(parameter) = 0
+    //
+    // Where Q'(parameter) is tangent to the curve at Q(parameter) and orthogonal to [Q(parameter) - P]
+    //
+    // Taking the derivative gives us:
+    //
+    //  f'(parameter) = (Q(parameter) - point) * Q''(parameter) + Q'(parameter) * Q'(parameter)
+    //
+    
+    // We assume the bezier path is a move to and a curve to
+    NSBezierElement element1 = [bezier fb_elementAtIndex:0];
+    NSBezierElement element2 = [bezier fb_elementAtIndex:1];
+    NSPoint bezierPoints[4] = {element1.point, element2.controlPoints[0], element2.controlPoints[1], element2.point};
+
+    // Compute Q(parameter)
+    NSPoint qAtParameter = BezierWithPoints(3, bezierPoints, parameter);
+    
+    // Compute Q'(parameter)
+    NSPoint qPrimePoints[3] = {};
+    for (NSUInteger i = 0; i < 3; i++) {
+        qPrimePoints[i].x = (bezierPoints[i + 1].x - bezierPoints[i].x) * 3.0;
+        qPrimePoints[i].y = (bezierPoints[i + 1].y - bezierPoints[i].y) * 3.0;
+    }
+    NSPoint qPrimeAtParameter = BezierWithPoints(2, qPrimePoints, parameter);
+    
+    // Compute Q''(parameter)
+    NSPoint qPrimePrimePoints[2] = {};
+    for (NSUInteger i = 0; i < 2; i++) {
+        qPrimePrimePoints[i].x = (qPrimePoints[i + 1].x - qPrimePoints[i].x) * 2.0;
+        qPrimePrimePoints[i].y = (qPrimePoints[i + 1].y - qPrimePoints[i].y) * 2.0;        
+    }
+    NSPoint qPrimePrimeAtParameter = BezierWithPoints(1, qPrimePrimePoints, parameter);
+    
+    // Compute f(parameter) and f'(parameter)
+    NSPoint qMinusPoint = FBSubtractPoint(qAtParameter, point);
+    CGFloat fAtParameter = FBDotMultiplyPoint(qMinusPoint, qPrimeAtParameter);
+    CGFloat fPrimeAtParameter = FBDotMultiplyPoint(qMinusPoint, qPrimePrimeAtParameter) + FBDotMultiplyPoint(qPrimeAtParameter, qPrimeAtParameter);
+    
+    // Newton's method!
+    return parameter - (fAtParameter / fPrimeAtParameter);
+}
+
+@interface NSBezierPath (FitCurvePrivate)
+
+- (NSBezierPath *) fb_fitCubicToRange:(NSRange)range leftTangent:(NSPoint)leftTangent rightTangent:(NSPoint)rightTangent errorThreshold:(CGFloat)errorThreshold;
+- (NSArray *) fb_refineParameters:(NSArray *)parameters forRange:(NSRange)range bezier:(NSBezierPath *)bezier;
+- (CGFloat) fb_findMaximumErrorForBezier:(NSBezierPath *)bezier inRange:(NSRange)range parameters:(NSArray *)parameters maximumIndex:(NSUInteger *)maximumIndex;
+- (NSBezierPath *) fb_fitBezierUsingNaiveMethodInRange:(NSRange)range leftTangent:(NSPoint)leftTangent rightTangent:(NSPoint)rightTangent;
+- (NSPoint) fb_computeLeftTangentAtIndex:(NSUInteger)index;
+- (NSPoint) fb_computeRightTangentAtIndex:(NSUInteger)index;
+- (NSPoint) fb_computeCenterTangentAtIndex:(NSUInteger)index;
+- (NSArray *) fb_estimateParametersUsingChordLengthMethodInRange:(NSRange)range;
+- (NSBezierPath *) fb_fitBezierInRange:(NSRange)range withParameters:(NSArray *)parameters leftTangent:(NSPoint)leftTangent rightTangent:(NSPoint)rightTangent;
+
+@end
+
+@implementation NSBezierPath (FitCurve)
+
+- (NSBezierPath *) fb_fitCurve:(CGFloat)errorThreshold
+{
+    // Safety first
+    if ( [self elementCount] < 2 )
+        return self;
+    
+    NSPoint leftTangentVector = [self fb_computeLeftTangentAtIndex:0];
+    NSPoint rightTangentVector = [self fb_computeRightTangentAtIndex:[self elementCount] - 1];
+    return [self fb_fitCubicToRange:NSMakeRange(0, [self elementCount]) leftTangent:leftTangentVector rightTangent:rightTangentVector errorThreshold:errorThreshold];
+}
+
+@end
+
+@implementation NSBezierPath (FitCurvePrivate)
+
+- (NSBezierPath *) fb_fitCubicToRange:(NSRange)range leftTangent:(NSPoint)leftTangent rightTangent:(NSPoint)rightTangent errorThreshold:(CGFloat)errorThreshold
+{
+    // Handle the special case where we only have two points
+    if ( range.length == 2 ) 
+        return [self fb_fitBezierUsingNaiveMethodInRange:range leftTangent:leftTangent rightTangent:rightTangent];
+
+    // First thing, just try to fit one bezier curve to all our points in range
+    NSArray *parameters = [self fb_estimateParametersUsingChordLengthMethodInRange:range];
+    NSBezierPath *bezier = [self fb_fitBezierInRange:range withParameters:parameters leftTangent:leftTangent rightTangent:rightTangent];
+    
+    // See how well our bezier fit our points. If it's within the allowed error, we're done
+    NSUInteger maximumIndex = NSNotFound;
+    CGFloat error = [self fb_findMaximumErrorForBezier:bezier inRange:range parameters:parameters maximumIndex:&maximumIndex];
+    if ( error < errorThreshold )
+        return bezier;
+    
+    // Huh. That wasn't good enough. Well, our estimated parameters probably sucked, so see if it makes sense to try
+    //  to refine them. If error is huge, it probably means that probably won't help, so in that case just skip it.
+    if ( error < (errorThreshold * errorThreshold) ) {
+        for (NSUInteger i = 0; i < FitCurveMaximumReparameterizes; i++) {
+            parameters = [self fb_refineParameters:parameters forRange:range bezier:bezier];
+            
+            // OK, try again with the new parameters
+            bezier = [self fb_fitBezierInRange:range withParameters:parameters leftTangent:leftTangent rightTangent:rightTangent];
+            error = [self fb_findMaximumErrorForBezier:bezier inRange:range parameters:parameters maximumIndex:&maximumIndex];
+            if ( error < errorThreshold )
+                return bezier; // sweet, it worked!
+        }
+    }
+    
+    // Alright, we couldn't fit a single bezier curve to all these points no matter how much we refined the parameters.
+    //  Instead, split the points into two parts based on where the biggest error is. Build two separate curves which
+    //  we'll combine into one single NSBezierPath.
+    NSPoint centerTangent = [self fb_computeCenterTangentAtIndex:maximumIndex];
+    NSBezierPath *leftBezier = [self fb_fitCubicToRange:NSMakeRange(range.location, maximumIndex - range.location + 1) leftTangent:leftTangent rightTangent:centerTangent errorThreshold:errorThreshold];
+    NSBezierPath *rightBezier = [self fb_fitCubicToRange:NSMakeRange(maximumIndex, (range.location + range.length) - maximumIndex) leftTangent:FBNegatePoint(centerTangent) rightTangent:rightTangent errorThreshold:errorThreshold];
+    [leftBezier fb_appendPath:rightBezier];
+    return leftBezier;
+}
+
+- (NSArray *) fb_refineParameters:(NSArray *)parameters forRange:(NSRange)range bezier:(NSBezierPath *)bezier
+{
+    // Use Newton's Method to refine our parameters.
+    NSMutableArray *refinedParameters = [NSMutableArray arrayWithCapacity:range.length];
+    for (NSUInteger i = 0; i < range.length; i++) {
+        [refinedParameters addObject:[NSNumber numberWithFloat:NewtonsMethod(bezier, [self fb_pointAtIndex:range.location + i], [[parameters objectAtIndex:i] floatValue])]];
+    }
+    return refinedParameters;
+}
+
+- (CGFloat) fb_findMaximumErrorForBezier:(NSBezierPath *)bezier inRange:(NSRange)range parameters:(NSArray *)parameters maximumIndex:(NSUInteger *)maximumIndex
+{
+    // Here we calculate the squared errors, defined as:
+    //
+    //  S = SUM( (point[i] - Q(parameters[i])) ^ 2 )
+    //
+    //  Where point[i] is the point on this NSBezierPath at i, parameters[i] is the float in the parameters
+    //  NSArray at index i. Q is the bezier curve represented by the variable bezier. This formula takes
+    //  the difference (distance) between a point in this NSBezierPath we're trying to fit, and the corresponding
+    //  point in the generated bezier curve, squares it, and adds all the differences up (i.e. squared errors).
+    //  This tells us how far off our curve is from our points we're trying to fit.    
+    CGFloat maximumError = 0.0;
+    for (NSUInteger i = 1; i < (range.length - 1); i++) {
+        NSPoint pointOnQ = Bezier(3, bezier, [[parameters objectAtIndex:i] floatValue]); // Calculate Q(parameters[i])
+        NSPoint point = [self fb_pointAtIndex:range.location + i];
+        CGFloat distance = FBPointSquaredLength(FBSubtractPoint(pointOnQ, point));
+        if ( distance >= maximumError ) {
+            maximumError = distance;
+            *maximumIndex = range.location + i;
+        }
+    }
+    return maximumError;
+}
+
+- (NSBezierPath *) fb_fitBezierUsingNaiveMethodInRange:(NSRange)range leftTangent:(NSPoint)leftTangent rightTangent:(NSPoint)rightTangent
+{
+    // This is a fallback method for when our normal bezier curve fitting method fails, either due to too few points
+    //  or other anomalies. As with the normal curve fitting, we have the two end points and the direction of the two control
+    //  points, meaning we only lack the distance of the control points from their end points. However, instead of getting
+    //  all fancy pants in calculating those distances we just throw up our hands and guess that it's a third of the distance between
+    //  the two end points. It's a heuristic, and not a good one.
+    
+    NSBezierPath *result = [NSBezierPath bezierPath];
+    [result fb_copyAttributesFrom:self];
+    
+    CGFloat thirdOfDistance = FBDistanceBetweenPoints([self fb_pointAtIndex:range.location + 1], [self fb_pointAtIndex:range.location]) / 3.0;
+    
+    [result moveToPoint:[self fb_pointAtIndex:range.location]];
+    [result curveToPoint:[self fb_pointAtIndex:range.location + 1] controlPoint1:FBAddPoint([self fb_pointAtIndex:range.location], FBUnitScalePoint(leftTangent, thirdOfDistance)) controlPoint2:FBAddPoint([self fb_pointAtIndex:range.location + 1], FBUnitScalePoint(rightTangent, thirdOfDistance))];
+    
+    return result;
+}
+
+- (NSBezierPath *) fb_fitBezierInRange:(NSRange)range withParameters:(NSArray *)parameters leftTangent:(NSPoint)leftTangent rightTangent:(NSPoint)rightTangent
+{
+    // We want to create a bezier curve to fit the path. A bezier curve is simply four points:
+    //  the two end points, and a control point for each end point. We already have the end points 
+    //  (i.e. [self pointAtIndex:range.location] and [self pointAtIndex:range.location+range.length-1])
+    //  and the direction of the control points away from the end points (leftTangent and rightTangent). 
+    //  The only thing lacking is the distance of the control points from their respective end points.
+    //  This function computes those distances, called leftAlpha and rightAlpha, and then constructs
+    //  the bezier curve from that.
+    //
+    // The basic formula used here for fitting a bezier is:
+    //
+    //  leftEndPoint = [self pointAtIndex:0]
+    //  rightEndPoint = [self pointAtIndex:[self elementCount]-1]
+    //  leftControlPoint = leftAlpha * leftTangent + leftEndPoint
+    //  rightControlPoint = rightAlpha * rightTangent + rightEndPoint
+
+    // By controlling the distance of the control points from their end points, we can affect the curve
+    //  of the bezier. We want to chose distances (leftAlpha and rightAlpha) such that it best fits the
+    //  points in self. Formally stated, we want to minimize the squared errors as represented by:
+    //
+    //  S = SUM( (point[i] - Q(parameters[i])) ^ 2 )
+    //
+    //  Where point[i] is the point on this NSBezierPath at i, parameters[i] is the float in the parameters
+    //  NSArray at index i. Q is the bezier curve we're generating in this function. This formula takes
+    //  the difference (distance) between a point in this NSBezierPath we're trying to fit, and the corresponding
+    //  point in the generated bezier curve, squares it, and adds all the differences up (i.e. squared errors).
+    //  This tells us how far off our curve is from our points we're trying to fit. We'd like to minimize this,
+    //  when calculating leftAlpha and rightAlpha.
+    //
+    //  Using the least squares approach we can write the equations we want to solve:
+    //
+    //  d(S) / d(leftAlpha) = 0
+    //  d(S) / d(rightAlpha) = 0
+    //
+    //  Here d() is the derivative, and S is the squared errors defined above. By then substituting in
+    //  S and then Q(t), which is defined as:
+    //
+    //  Q(t) = SUM(V[i] * Bernstein[i](t))
+    //
+    //  Where i ranges between [0..3], V is one of the points on the bezier curve. V[0] is the leftEndPoint,
+    //  V[1] the leftControlPoint, V[2] the rightControlPoint, and V[3] the rightEndPoint. Berstein[i] is
+    //  is a polynomial defined by the Bernstein0(), Bernstein1(), Bernstein2(), Bernstein3() functions
+    //  (see their comments for explaination).
+    //
+    // After much mathematical flagellation, we arrive at the following definitions
+    //
+    //  leftAlpha = det(X * C2) / det(C1 * C2)
+    //  rightAlpha = det(C1 * X) / det(C1 * C2)
+    //
+    // Where:
+    //
+    //  C1 = [SUM(A1[i] * A1[i]), SUM(A1[i] * A2[i])]
+    //  C2 = [SUM(A1[i] * A2[i]), SUM(A2[i] * A2[i])]
+    //  X = [SUM(partOfX * A1[i]), SUM(partOfX * A2[i])]
+    //      Where partOfX = (points[i] - (leftEndPoint * Bernstein0(parameters[i]) + leftEndPoint * Bernstein1(parameters[i]) + rightEndPoint * Bernstein2(parameters[i]) + rightEndPoint * Bernstein3(parameters[i])))
+    //  A1[i] = leftTangent * Bernstein1(parameters[i])
+    //  A2[i] = rightTangent * Bernstein2(parameters[i])
+    
+    // Create tables for the A values
+    NSPoint *a1 = (NSPoint *)calloc(range.length, sizeof(NSPoint));
+    NSPoint *a2 = (NSPoint *)calloc(range.length, sizeof(NSPoint));    
+    for (NSUInteger i = 0; i < range.length; i++) {
+        a1[i] = FBUnitScalePoint(leftTangent, Bernstein1([[parameters objectAtIndex:i] floatValue]));
+        a2[i] = FBUnitScalePoint(rightTangent, Bernstein2([[parameters objectAtIndex:i] floatValue]));
+    }
+    
+    // Create the C1, C2, and X matrices
+    CGFloat c1[2] = {};
+    CGFloat c2[2] = {};
+    CGFloat x[2] = {};
+    NSPoint partOfX = NSZeroPoint;
+    NSPoint leftEndPoint = [self fb_pointAtIndex:range.location];
+    NSPoint rightEndPoint = [self fb_pointAtIndex:range.location + range.length - 1];
+    for (NSUInteger i = 0; i < range.length; i++) {
+        c1[0] += FBDotMultiplyPoint(a1[i], a1[i]);
+        c1[1] += FBDotMultiplyPoint(a1[i], a2[i]);
+        c2[0] += FBDotMultiplyPoint(a1[i], a2[i]);
+        c2[1] += FBDotMultiplyPoint(a2[i], a2[i]);
+        
+        partOfX = FBSubtractPoint([self fb_pointAtIndex:range.location + i], 
+                                  FBAddPoint(FBScalePoint(leftEndPoint, Bernstein0([[parameters objectAtIndex:i] floatValue])),
+                                             FBAddPoint(FBScalePoint(leftEndPoint, Bernstein1([[parameters objectAtIndex:i] floatValue])),
+                                                        FBAddPoint(FBScalePoint(rightEndPoint, Bernstein2([[parameters objectAtIndex:i] floatValue])),
+                                                                   FBScalePoint(rightEndPoint, Bernstein3([[parameters objectAtIndex:i] floatValue]))))));
+        
+        x[0] += FBDotMultiplyPoint(partOfX, a1[i]);
+        x[1] += FBDotMultiplyPoint(partOfX, a2[i]);
+    }
+    
+    // We're done with the A values, so free that up
+    free(a1);
+    free(a2);
+
+    // Calculate left and right alpha
+    CGFloat c1AndC2 = Determinant(c1, c2);
+    CGFloat xAndC2 = Determinant(x, c2);
+    CGFloat c1AndX = Determinant(c1, x);
+    CGFloat leftAlpha = 0.0;
+    CGFloat rightAlpha = 0.0;
+    if ( c1AndC2 != 0 ) {
+        leftAlpha = xAndC2 / c1AndC2;
+        rightAlpha = c1AndX / c1AndC2;
+    }
+    
+    // If the alpha values are too small or negative, things aren't going to work out well. Fall back
+    //  to the simple heuristic
+    CGFloat verySmallValue = 1.0e-6 * FBDistanceBetweenPoints(leftEndPoint, rightEndPoint);
+    if ( leftAlpha < verySmallValue || rightAlpha < verySmallValue )
+        return [self fb_fitBezierUsingNaiveMethodInRange:range leftTangent:leftTangent rightTangent:rightTangent];
+    
+    // We already have the end points, so we just need the control points. Use alpha values
+    //  to calculate those
+    NSPoint leftControlPoint = FBAddPoint(FBUnitScalePoint(leftTangent, leftAlpha), leftEndPoint);
+    NSPoint rightControlPoint = FBAddPoint(FBUnitScalePoint(rightTangent, rightAlpha), rightEndPoint);
+    
+    // Create the bezier path based on the end and control points we calculated
+    NSBezierPath *path = [NSBezierPath bezierPath];
+    [path fb_copyAttributesFrom:self];
+    [path moveToPoint:leftEndPoint];
+    [path curveToPoint:rightEndPoint controlPoint1:leftControlPoint controlPoint2:rightControlPoint];
+    return path;
+}
+
+- (NSArray *) fb_estimateParametersUsingChordLengthMethodInRange:(NSRange)range
+{
+    // We assume that our bezier curve is represented by the function Q(t), where t has the range of [0..1].
+    //  The output of Q(t) is (x, y) coordinates that (hopefully) fit closely to our input
+    //  points (i.e the points in this bezier path). In this method we're trying to estimate the 
+    //  parameter of the function Q (i.e. t) for each of our input points. For the end points, this is easy:
+    //  Q(0) should give us [self fb_pointAtIndex:range.location] and Q(1) should give us
+    //  [self fb_pointAtIndex:range.location + range.length - 1]. For the points in between we'll use the
+    //  chord length method.
+    //
+    // The chord length method assumes a straight line between the points is a reasonable estimate for the curve
+    //  between the points. Thus we can estimate t for a given point Foo to be distance in between all the points
+    //  from the start point up to the point Foo, divided by the distance between all the points (in order to normalize
+    //  the distance between [0..1])
+    
+    NSMutableArray *distances = [NSMutableArray arrayWithCapacity:range.length];
+    [distances addObject:[NSNumber numberWithFloat:0.0]]; // First one is always 0 (see above)
+    CGFloat totalDistance = 0.0;
+    for (NSUInteger i = 1; i < range.length; i++) {
+        // Calculate the total distance along the curve up to this point
+        totalDistance += FBDistanceBetweenPoints([self fb_pointAtIndex:range.location + i], [self fb_pointAtIndex:range.location + i - 1]);
+        [distances addObject:[NSNumber numberWithFloat:totalDistance]];
+    }
+    
+    // Now go through and normalize the distances to in the range [0..1]
+    NSMutableArray *parameters = [NSMutableArray arrayWithCapacity:range.length];
+    for (NSNumber *distance in distances)
+        [parameters addObject:[NSNumber numberWithFloat:[distance floatValue] / totalDistance]];
+
+    return parameters;
+}
+
+- (NSPoint) fb_computeLeftTangentAtIndex:(NSUInteger)index
+{
+    // Compute the tangent unit vector by computing the vector between the left two points,
+    //  then normalizing it so its unit vector.
+    return FBNormalizePoint( FBSubtractPoint([self fb_pointAtIndex:index + 1], [self fb_pointAtIndex:index]) );
+}
+
+- (NSPoint) fb_computeRightTangentAtIndex:(NSUInteger)index
+{
+    // Compute the tangent unit vector by computing the vector between the right two points,
+    //  then normalizing it so its unit vector.
+    return FBNormalizePoint( FBSubtractPoint([self fb_pointAtIndex:index - 1], [self fb_pointAtIndex:index]) );
+}
+
+- (NSPoint) fb_computeCenterTangentAtIndex:(NSUInteger)index
+{
+    // Compute the tangent unit vector with index as the center. We'll calculate the vectors on both sides
+    //  of index and then average them together.
+    NSPoint vector1 = FBSubtractPoint([self fb_pointAtIndex:index - 1], [self fb_pointAtIndex:index]);
+    NSPoint vector2 = FBSubtractPoint([self fb_pointAtIndex:index], [self fb_pointAtIndex:index + 1]);
+    return FBNormalizePoint(NSMakePoint((vector1.x + vector2.x) / 2.0, (vector1.y + vector2.y) / 2.0));
+}
+@end

File VectorBoolean/NSBezierPath+Simplify.h

View file
+//
+//  NSBezierPath+Simplify.h
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/27/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Foundation/Foundation.h>
+
+
+@interface NSBezierPath (Simplify)
+
+- (NSBezierPath *) fb_simplify:(CGFloat)threshold;
+
+@end

File VectorBoolean/NSBezierPath+Simplify.m

View file
+//
+//  NSBezierPath+Simplify.m
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/27/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "NSBezierPath+Simplify.h"
+#import "NSBezierPath+Utilities.h"
+#import "Geometry.h"
+
+// Implements the Ramer-Douglas-Peucker algorithm
+
+@implementation NSBezierPath (Simplify)
+
+- (NSBezierPath *) fb_simplify:(CGFloat)threshold
+{
+    if ( [self elementCount] <= 2 )
+        return self;
+    
+    CGFloat maximumDistance = 0.0;
+    NSUInteger maximumIndex = 0;
+    
+    // Find the point the furtherest away
+    for (NSUInteger i = 1; i < ([self elementCount] - 1); i++) {
+        CGFloat distance = FBDistancePointToLine([self fb_pointAtIndex:i], [self fb_pointAtIndex:0], [self fb_pointAtIndex:[self elementCount] - 1]);
+        if ( distance > maximumDistance ) {
+            maximumDistance = distance;
+            maximumIndex = i;
+        }
+    }
+    
+    if ( maximumDistance >= threshold ) {
+        // The distance is too great to simplify, so recurse
+        NSBezierPath *results1 = [[self fb_subpathWithRange:NSMakeRange(0, maximumIndex + 1)] fb_simplify:threshold];
+        NSBezierPath *results2 = [[self fb_subpathWithRange:NSMakeRange(maximumIndex, [self elementCount] - maximumIndex)] fb_simplify:threshold];
+    
+        [results1 fb_appendPath:[results2 fb_subpathWithRange:NSMakeRange(1, [results2 elementCount] - 1)]];
+        return results1;
+    } 
+        
+    // The greatest distance from our end points isn't that much, so we can simplify
+    NSBezierPath *path = [NSBezierPath bezierPath];
+    [path fb_copyAttributesFrom:self];
+    [path moveToPoint:[self fb_pointAtIndex:0]];
+    [path lineToPoint:[self fb_pointAtIndex:[self elementCount] - 1]];
+    return path;
+}
+
+@end

File VectorBoolean/NSBezierPath+Utilities.h

View file
+//
+//  NSBezierPath+Utilities.h
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/28/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import <Cocoa/Cocoa.h>
+
+typedef struct NSBezierElement {
+    NSBezierPathElement kind;
+    NSPoint point;
+    NSPoint controlPoints[2];
+} NSBezierElement;
+
+@interface NSBezierPath (FBUtilities)
+
+- (NSPoint) fb_pointAtIndex:(NSUInteger)index;
+- (NSBezierElement) fb_elementAtIndex:(NSUInteger)index;
+
+- (NSBezierPath *) fb_subpathWithRange:(NSRange)range;
+
+- (void) fb_copyAttributesFrom:(NSBezierPath *)path;
+- (void) fb_appendPath:(NSBezierPath *)path;
+- (void) fb_appendElement:(NSBezierElement)element;
+
+@end

File VectorBoolean/NSBezierPath+Utilities.m

View file
+//
+//  NSBezierPath+Utilities.m
+//  VectorBrush
+//
+//  Created by Andrew Finnell on 5/28/11.
+//  Copyright 2011 Fortunate Bear, LLC. All rights reserved.
+//
+
+#import "NSBezierPath+Utilities.h"
+
+
+@implementation NSBezierPath (FBUtilities)
+
+- (NSPoint) fb_pointAtIndex:(NSUInteger)index
+{
+    return [self fb_elementAtIndex:index].point;
+}
+
+- (NSBezierElement) fb_elementAtIndex:(NSUInteger)index
+{
+    NSBezierElement element = {};
+    NSPoint points[3] = {};
+    element.kind = [self elementAtIndex:index associatedPoints:points];
+    switch (element.kind) {
+        case NSMoveToBezierPathElement:
+        case NSLineToBezierPathElement:
+        case NSClosePathBezierPathElement:
+            element.point = points[0];
+            break;
+            
+        case NSCurveToBezierPathElement:
+            element.controlPoints[0] = points[0];
+            element.controlPoints[1] = points[1];
+            element.point = points[2];
+            break;
+    }
+    return element;
+}
+
+- (NSBezierPath *) fb_subpathWithRange:(NSRange)range
+{
+    NSBezierPath *path = [NSBezierPath bezierPath];
+    [path fb_copyAttributesFrom:self];
+    for (NSUInteger i = 0; i < range.length; i++) {
+        NSBezierElement element = [self fb_elementAtIndex:range.location + i];
+        if ( i == 0 )
+            [path moveToPoint:element.point];
+        else
+            [path fb_appendElement:element];
+    }
+    return path;
+}
+
+- (void) fb_copyAttributesFrom:(NSBezierPath *)path
+{
+    [self setLineWidth:[path lineWidth]];
+    [self setLineCapStyle:[path lineCapStyle]];
+    [self setLineJoinStyle:[path lineJoinStyle]];
+    [self setWindingRule:[path windingRule]];
+    [self setMiterLimit:[path miterLimit]];
+    [self setFlatness:[path flatness]];
+}
+
+- (void) fb_appendPath:(NSBezierPath *)path
+{
+    NSBezierElement previousElement = [self fb_elementAtIndex:[self elementCount] - 1];
+    for (NSUInteger i = 0; i < [path elementCount]; i++) {
+        NSBezierElement element = [path fb_elementAtIndex:i];
+        
+        // If the first element is a move to where we left off, skip it
+        if ( element.kind == NSMoveToBezierPathElement ) {
+            if ( NSEqualPoints(element.point, previousElement.point) )
+                continue;
+            else
+                element.kind = NSLineToBezierPathElement; // change it to a line to
+        }
+        
+        [self fb_appendElement:element];
+        previousElement = element;
+    }
+}
+
+- (void) fb_appendElement:(NSBezierElement)element
+{
+    switch (element.kind) {
+        case NSMoveToBezierPathElement:
+            [self moveToPoint:element.point];
+            break;
+        case NSLineToBezierPathElement:
+            [self lineToPoint:element.point];
+            break;
+        case NSCurveToBezierPathElement:
+            [self curveToPoint:element.point controlPoint1:element.controlPoints[0] controlPoint2:element.controlPoints[1]];
+            break;
+        case NSClosePathBezierPathElement:
+            [self closePath];
+            break;
+    }
+}
+
+@end

File VectorBoolean/en.lproj/MainMenu.xib

View file
 <archive type="com.apple.InterfaceBuilder3.Cocoa.XIB" version="7.10">
 	<data>
 		<int key="IBDocument.SystemTarget">1060</int>
-		<string key="IBDocument.SystemVersion">10A313</string>
-		<string key="IBDocument.InterfaceBuilderVersion">718</string>
-		<string key="IBDocument.AppKitVersion">1013</string>
-		<string key="IBDocument.HIToolboxVersion">415.00</string>
+		<string key="IBDocument.SystemVersion">10J567</string>
+		<string key="IBDocument.InterfaceBuilderVersion">1306</string>
+		<string key="IBDocument.AppKitVersion">1038.35</string>
+		<string key="IBDocument.HIToolboxVersion">462.00</string>
 		<object class="NSMutableDictionary" key="IBDocument.PluginVersions">
 			<string key="NS.key.0">com.apple.InterfaceBuilder.CocoaPlugin</string>
-			<string key="NS.object.0">718</string>
+			<string key="NS.object.0">1306</string>
 		</object>
-		<object class="NSMutableArray" key="IBDocument.EditedObjectIDs">
+		<object class="NSArray" key="IBDocument.IntegratedClassDependencies">
 			<bool key="EncodedWithXMLCoder">YES</bool>
-			<integer value="29"/>
+			<string>NSMenu</string>
+			<string>NSMenuItem</string>
+			<string>NSCustomObject</string>
 		</object>
 		<object class="NSArray" key="IBDocument.PluginDependencies">
 			<bool key="EncodedWithXMLCoder">YES</bool>
 			<object class="NSArray" key="dict.sortedKeys" id="0">
 				<bool key="EncodedWithXMLCoder">YES</bool>
 			</object>
-			<object class="NSMutableArray" key="dict.values">
-				<bool key="EncodedWithXMLCoder">YES</bool>
-			</object>
+			<reference key="dict.values" ref="0"/>
 		</object>
 		<object class="NSMutableArray" key="IBDocument.RootObjects" id="1048">
 			<bool key="EncodedWithXMLCoder">YES</bool>
 							<string key="NSTitle">Edit</string>
 							<object class="NSMutableArray" key="NSMenuItems">
 								<bool key="EncodedWithXMLCoder">YES</bool>
-								<object class="NSMenuItem" id="1058277027">
+								<object class="NSMenuItem" id="389894064">
 									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Undo</string>
-									<string key="NSKeyEquiv">z</string>
-									<int key="NSKeyEquivModMask">1048576</int>
+									<string key="NSTitle">Reset</string>
+									<string key="NSKeyEquiv"/>
 									<int key="NSMnemonicLoc">2147483647</int>
 									<reference key="NSOnImage" ref="1033313550"/>
 									<reference key="NSMixedImage" ref="310636482"/>
 								</object>
-								<object class="NSMenuItem" id="790794224">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Redo</string>
-									<string key="NSKeyEquiv">Z</string>
-									<int key="NSKeyEquivModMask">1179648</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-								</object>
-								<object class="NSMenuItem" id="1040322652">
+								<object class="NSMenuItem" id="922849572">
 									<reference key="NSMenu" ref="789758025"/>
 									<bool key="NSIsDisabled">YES</bool>
 									<bool key="NSIsSeparator">YES</bool>
 									<string key="NSTitle"/>
 									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
 									<int key="NSMnemonicLoc">2147483647</int>
 									<reference key="NSOnImage" ref="1033313550"/>
 									<reference key="NSMixedImage" ref="310636482"/>
 								</object>
-								<object class="NSMenuItem" id="296257095">
+								<object class="NSMenuItem" id="552064043">
 									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Cut</string>
-									<string key="NSKeyEquiv">x</string>
-									<int key="NSKeyEquivModMask">1048576</int>
+									<string key="NSTitle">Union</string>
+									<string key="NSKeyEquiv"/>
 									<int key="NSMnemonicLoc">2147483647</int>
 									<reference key="NSOnImage" ref="1033313550"/>
 									<reference key="NSMixedImage" ref="310636482"/>
 								</object>
-								<object class="NSMenuItem" id="860595796">
+								<object class="NSMenuItem" id="696057768">
 									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Copy</string>
-									<string key="NSKeyEquiv">c</string>
-									<int key="NSKeyEquivModMask">1048576</int>
+									<string key="NSTitle">Intersect</string>
+									<string key="NSKeyEquiv"/>
 									<int key="NSMnemonicLoc">2147483647</int>
 									<reference key="NSOnImage" ref="1033313550"/>
 									<reference key="NSMixedImage" ref="310636482"/>
 								</object>
-								<object class="NSMenuItem" id="29853731">
+								<object class="NSMenuItem" id="417065018">
 									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Paste</string>
-									<string key="NSKeyEquiv">v</string>
-									<int key="NSKeyEquivModMask">1048576</int>
+									<string key="NSTitle">Difference</string>
+									<string key="NSKeyEquiv"/>
 									<int key="NSMnemonicLoc">2147483647</int>
 									<reference key="NSOnImage" ref="1033313550"/>
 									<reference key="NSMixedImage" ref="310636482"/>
 								</object>
-								<object class="NSMenuItem" id="763435172">
+								<object class="NSMenuItem" id="1031749860">
 									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Paste and Match Style</string>
-									<string key="NSKeyEquiv">V</string>
-									<int key="NSKeyEquivModMask">1572864</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-								</object>
-								<object class="NSMenuItem" id="437104165">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Delete</string>
+									<string key="NSTitle">Join</string>
 									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-								</object>
-								<object class="NSMenuItem" id="583158037">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Select All</string>
-									<string key="NSKeyEquiv">a</string>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-								</object>
-								<object class="NSMenuItem" id="212016141">
-									<reference key="NSMenu" ref="789758025"/>
-									<bool key="NSIsDisabled">YES</bool>
-									<bool key="NSIsSeparator">YES</bool>
-									<string key="NSTitle"/>
-									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-								</object>
-								<object class="NSMenuItem" id="892235320">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Find</string>
-									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-									<string key="NSAction">submenuAction:</string>
-									<object class="NSMenu" key="NSSubmenu" id="963351320">
-										<string key="NSTitle">Find</string>
-										<object class="NSMutableArray" key="NSMenuItems">
-											<bool key="EncodedWithXMLCoder">YES</bool>
-											<object class="NSMenuItem" id="447796847">
-												<reference key="NSMenu" ref="963351320"/>
-												<string key="NSTitle">Find…</string>
-												<string key="NSKeyEquiv">f</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">1</int>
-											</object>
-											<object class="NSMenuItem" id="326711663">
-												<reference key="NSMenu" ref="963351320"/>
-												<string key="NSTitle">Find Next</string>
-												<string key="NSKeyEquiv">g</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">2</int>
-											</object>
-											<object class="NSMenuItem" id="270902937">
-												<reference key="NSMenu" ref="963351320"/>
-												<string key="NSTitle">Find Previous</string>
-												<string key="NSKeyEquiv">G</string>
-												<int key="NSKeyEquivModMask">1179648</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">3</int>
-											</object>
-											<object class="NSMenuItem" id="159080638">
-												<reference key="NSMenu" ref="963351320"/>
-												<string key="NSTitle">Use Selection for Find</string>
-												<string key="NSKeyEquiv">e</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">7</int>
-											</object>
-											<object class="NSMenuItem" id="88285865">
-												<reference key="NSMenu" ref="963351320"/>
-												<string key="NSTitle">Jump to Selection</string>
-												<string key="NSKeyEquiv">j</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-										</object>
-									</object>
-								</object>
-								<object class="NSMenuItem" id="972420730">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Spelling and Grammar</string>
-									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-									<string key="NSAction">submenuAction:</string>
-									<object class="NSMenu" key="NSSubmenu" id="769623530">
-										<string key="NSTitle">Spelling and Grammar</string>
-										<object class="NSMutableArray" key="NSMenuItems">
-											<bool key="EncodedWithXMLCoder">YES</bool>
-											<object class="NSMenuItem" id="679648819">
-												<reference key="NSMenu" ref="769623530"/>
-												<string key="NSTitle">Show Spelling and Grammar</string>
-												<string key="NSKeyEquiv">:</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="96193923">
-												<reference key="NSMenu" ref="769623530"/>
-												<string key="NSTitle">Check Document Now</string>
-												<string key="NSKeyEquiv">;</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="292991471">
-												<reference key="NSMenu" ref="769623530"/>
-												<bool key="NSIsDisabled">YES</bool>
-												<bool key="NSIsSeparator">YES</bool>
-												<string key="NSTitle"/>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="948374510">
-												<reference key="NSMenu" ref="769623530"/>
-												<string key="NSTitle">Check Spelling While Typing</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="967646866">
-												<reference key="NSMenu" ref="769623530"/>
-												<string key="NSTitle">Check Grammar With Spelling</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="817901857">
-												<reference key="NSMenu" ref="769623530"/>
-												<string key="NSTitle">Correct Spelling Automatically</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-										</object>
-									</object>
-								</object>
-								<object class="NSMenuItem" id="507821607">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Substitutions</string>
-									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-									<string key="NSAction">submenuAction:</string>
-									<object class="NSMenu" key="NSSubmenu" id="698887838">
-										<string key="NSTitle">Substitutions</string>
-										<object class="NSMutableArray" key="NSMenuItems">
-											<bool key="EncodedWithXMLCoder">YES</bool>
-											<object class="NSMenuItem" id="63225254">
-												<reference key="NSMenu" ref="698887838"/>
-												<string key="NSTitle">Show Substitutions</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="430156352">
-												<reference key="NSMenu" ref="698887838"/>
-												<bool key="NSIsDisabled">YES</bool>
-												<bool key="NSIsSeparator">YES</bool>
-												<string key="NSTitle"/>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="605118523">
-												<reference key="NSMenu" ref="698887838"/>
-												<string key="NSTitle">Smart Copy/Paste</string>
-												<string key="NSKeyEquiv">f</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">1</int>
-											</object>
-											<object class="NSMenuItem" id="197661976">
-												<reference key="NSMenu" ref="698887838"/>
-												<string key="NSTitle">Smart Quotes</string>
-												<string key="NSKeyEquiv">g</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">2</int>
-											</object>
-											<object class="NSMenuItem" id="618524225">
-												<reference key="NSMenu" ref="698887838"/>
-												<string key="NSTitle">Smart Dashes</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="708854459">
-												<reference key="NSMenu" ref="698887838"/>
-												<string key="NSTitle">Smart Links</string>
-												<string key="NSKeyEquiv">G</string>
-												<int key="NSKeyEquivModMask">1179648</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">3</int>
-											</object>
-											<object class="NSMenuItem" id="511468581">
-												<reference key="NSMenu" ref="698887838"/>
-												<string key="NSTitle">Text Replacement</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-										</object>
-									</object>
-								</object>
-								<object class="NSMenuItem" id="981774355">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Transformations</string>
-									<string key="NSKeyEquiv"/>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-									<string key="NSAction">submenuAction:</string>
-									<object class="NSMenu" key="NSSubmenu" id="769264466">
-										<string key="NSTitle">Transformations</string>
-										<object class="NSMutableArray" key="NSMenuItems">
-											<bool key="EncodedWithXMLCoder">YES</bool>
-											<object class="NSMenuItem" id="372238911">
-												<reference key="NSMenu" ref="769264466"/>
-												<string key="NSTitle">Make Upper Case</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="740446531">
-												<reference key="NSMenu" ref="769264466"/>
-												<string key="NSTitle">Make Lower Case</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="1063332286">
-												<reference key="NSMenu" ref="769264466"/>
-												<string key="NSTitle">Capitalize</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-										</object>
-									</object>
-								</object>
-								<object class="NSMenuItem" id="676164635">
-									<reference key="NSMenu" ref="789758025"/>
-									<string key="NSTitle">Speech</string>
-									<string key="NSKeyEquiv"/>
-									<int key="NSKeyEquivModMask">1048576</int>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-									<string key="NSAction">submenuAction:</string>
-									<object class="NSMenu" key="NSSubmenu" id="785027613">
-										<string key="NSTitle">Speech</string>
-										<object class="NSMutableArray" key="NSMenuItems">
-											<bool key="EncodedWithXMLCoder">YES</bool>
-											<object class="NSMenuItem" id="731782645">
-												<reference key="NSMenu" ref="785027613"/>
-												<string key="NSTitle">Start Speaking</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="680220178">
-												<reference key="NSMenu" ref="785027613"/>
-												<string key="NSTitle">Stop Speaking</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-										</object>
-									</object>
-								</object>
-							</object>
-						</object>
-					</object>
-					<object class="NSMenuItem" id="470804886">
-						<reference key="NSMenu" ref="649796088"/>
-						<string key="NSTitle">Format</string>
-						<string key="NSKeyEquiv"/>
-						<int key="NSMnemonicLoc">2147483647</int>
-						<reference key="NSOnImage" ref="1033313550"/>
-						<reference key="NSMixedImage" ref="310636482"/>
-						<string key="NSAction">submenuAction:</string>
-						<object class="NSMenu" key="NSSubmenu" id="892078337">
-							<string key="NSTitle">Format</string>
-							<object class="NSMutableArray" key="NSMenuItems">
-								<bool key="EncodedWithXMLCoder">YES</bool>
-								<object class="NSMenuItem" id="417081885">
-									<reference key="NSMenu" ref="892078337"/>
-									<string key="NSTitle">Font</string>
-									<string key="NSKeyEquiv"/>
-									<int key="NSMnemonicLoc">2147483647</int>
-									<reference key="NSOnImage" ref="1033313550"/>
-									<reference key="NSMixedImage" ref="310636482"/>
-									<string key="NSAction">submenuAction:</string>
-									<object class="NSMenu" key="NSSubmenu" id="1063883570">
-										<string key="NSTitle">Font</string>
-										<object class="NSMutableArray" key="NSMenuItems">
-											<bool key="EncodedWithXMLCoder">YES</bool>
-											<object class="NSMenuItem" id="174638318">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Show Fonts</string>
-												<string key="NSKeyEquiv">t</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="481459203">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Bold</string>
-												<string key="NSKeyEquiv">b</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">2</int>
-											</object>
-											<object class="NSMenuItem" id="275470842">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Italic</string>
-												<string key="NSKeyEquiv">i</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">1</int>
-											</object>
-											<object class="NSMenuItem" id="319949941">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Underline</string>
-												<string key="NSKeyEquiv">u</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="692549729">
-												<reference key="NSMenu" ref="1063883570"/>
-												<bool key="NSIsDisabled">YES</bool>
-												<bool key="NSIsSeparator">YES</bool>
-												<string key="NSTitle"/>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="410574898">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Bigger</string>
-												<string key="NSKeyEquiv">+</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">3</int>
-											</object>
-											<object class="NSMenuItem" id="234445462">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Smaller</string>
-												<string key="NSKeyEquiv">-</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<int key="NSTag">4</int>
-											</object>
-											<object class="NSMenuItem" id="364585565">
-												<reference key="NSMenu" ref="1063883570"/>
-												<bool key="NSIsDisabled">YES</bool>
-												<bool key="NSIsSeparator">YES</bool>
-												<string key="NSTitle"/>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="53157584">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Kern</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<string key="NSAction">submenuAction:</string>
-												<object class="NSMenu" key="NSSubmenu" id="249492784">
-													<string key="NSTitle">Kern</string>
-													<object class="NSMutableArray" key="NSMenuItems">
-														<bool key="EncodedWithXMLCoder">YES</bool>
-														<object class="NSMenuItem" id="621871957">
-															<reference key="NSMenu" ref="249492784"/>
-															<string key="NSTitle">Use Default</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="287782986">
-															<reference key="NSMenu" ref="249492784"/>
-															<string key="NSTitle">Use None</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="1054746601">
-															<reference key="NSMenu" ref="249492784"/>
-															<string key="NSTitle">Tighten</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="927944004">
-															<reference key="NSMenu" ref="249492784"/>
-															<string key="NSTitle">Loosen</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-													</object>
-												</object>
-											</object>
-											<object class="NSMenuItem" id="29382803">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Ligature</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<string key="NSAction">submenuAction:</string>
-												<object class="NSMenu" key="NSSubmenu" id="481842979">
-													<string key="NSTitle">Ligature</string>
-													<object class="NSMutableArray" key="NSMenuItems">
-														<bool key="EncodedWithXMLCoder">YES</bool>
-														<object class="NSMenuItem" id="1023090053">
-															<reference key="NSMenu" ref="481842979"/>
-															<string key="NSTitle">Use Default</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="592961422">
-															<reference key="NSMenu" ref="481842979"/>
-															<string key="NSTitle">Use None</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="1070261725">
-															<reference key="NSMenu" ref="481842979"/>
-															<string key="NSTitle">Use All</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-													</object>
-												</object>
-											</object>
-											<object class="NSMenuItem" id="1035117790">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Baseline</string>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-												<string key="NSAction">submenuAction:</string>
-												<object class="NSMenu" key="NSSubmenu" id="228490898">
-													<string key="NSTitle">Baseline</string>
-													<object class="NSMutableArray" key="NSMenuItems">
-														<bool key="EncodedWithXMLCoder">YES</bool>
-														<object class="NSMenuItem" id="897580362">
-															<reference key="NSMenu" ref="228490898"/>
-															<string key="NSTitle">Use Default</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="78871505">
-															<reference key="NSMenu" ref="228490898"/>
-															<string key="NSTitle">Superscript</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="17354335">
-															<reference key="NSMenu" ref="228490898"/>
-															<string key="NSTitle">Subscript</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="670533225">
-															<reference key="NSMenu" ref="228490898"/>
-															<string key="NSTitle">Raise</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-														<object class="NSMenuItem" id="654494087">
-															<reference key="NSMenu" ref="228490898"/>
-															<string key="NSTitle">Lower</string>
-															<string key="NSKeyEquiv"/>
-															<int key="NSMnemonicLoc">2147483647</int>
-															<reference key="NSOnImage" ref="1033313550"/>
-															<reference key="NSMixedImage" ref="310636482"/>
-														</object>
-													</object>
-												</object>
-											</object>
-											<object class="NSMenuItem" id="707650671">
-												<reference key="NSMenu" ref="1063883570"/>
-												<bool key="NSIsDisabled">YES</bool>
-												<bool key="NSIsSeparator">YES</bool>
-												<string key="NSTitle"/>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="871758183">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Show Colors</string>
-												<string key="NSKeyEquiv">C</string>
-												<int key="NSKeyEquivModMask">1048576</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="750501226">
-												<reference key="NSMenu" ref="1063883570"/>
-												<bool key="NSIsDisabled">YES</bool>
-												<bool key="NSIsSeparator">YES</bool>
-												<string key="NSTitle"/>
-												<string key="NSKeyEquiv"/>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="721121421">
-												<reference key="NSMenu" ref="1063883570"/>
-												<string key="NSTitle">Copy Style</string>
-												<string key="NSKeyEquiv">c</string>
-												<int key="NSKeyEquivModMask">1572864</int>
-												<int key="NSMnemonicLoc">2147483647</int>
-												<reference key="NSOnImage" ref="1033313550"/>
-												<reference key="NSMixedImage" ref="310636482"/>
-											</object>
-											<object class="NSMenuItem" id="331522238">