1#import "RNSVGPathMeasure.h"
2#import "RNSVGBezierElement.h"
3
4/* Some Bezier logic from PerformanceBezier */
5/*
6
7 ## License
8
9 <a rel="license" href="http://creativecommons.org/licenses/by/3.0/us/"><img alt="Creative Commons License"
10 style="border-width:0" src="https://i.creativecommons.org/l/by/3.0/us/88x31.png" /></a><br />This work is licensed
11 under a <a rel="license" href="http://creativecommons.org/licenses/by/3.0/us/">Creative Commons Attribution 3.0 United
12 States License</a>.
13
14 For attribution, please include:
15
16 1. Mention original author "Adam Wulf for Loose Leaf app"
17 2. Link to https://getlooseleaf.com/opensource/
18 3. Link to https://github.com/adamwulf/PerformanceBezier
19
20 */
21static CGFloat idealFlatness = (CGFloat).01;
22
23/**
24 * returns the distance between two points
25 */
26static CGFloat distance(CGPoint p1, CGPoint p2)
27{
28  CGFloat dx = p2.x - p1.x;
29  CGFloat dy = p2.y - p1.y;
30  return hypot(dx, dy);
31}
32
33// Subdivide a Bézier (specific division)
34/*
35 * (c) 2004 Alastair J. Houghton
36 * All Rights Reserved.
37 *
38 * Redistribution and use in source and binary forms, with or without
39 * modification, are permitted provided that the following conditions are met:
40 *
41 *   1. Redistributions of source code must retain the above copyright
42 *      notice, this list of conditions and the following disclaimer.
43 *
44 *   2. Redistributions in binary form must reproduce the above copyright
45 *      notice, this list of conditions and the following disclaimer in the
46 *      documentation and/or other materials provided with the distribution.
47 *
48 *   3. The name of the author of this software may not be used to endorse
49 *      or promote products derived from the software without specific prior
50 *      written permission.
51 *
52 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER "AS IS" AND ANY EXPRESS
53 * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
54 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
55 * IN NO EVENT SHALL THE COPYRIGHT OWNER BE LIABLE FOR ANY DIRECT, INDIRECT,
56 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO
57 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA OR PROFITS;
58 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
59 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
60 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
61 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
62 *
63 */
64static void subdivideBezierAtT(const CGPoint bez[4], CGPoint bez1[4], CGPoint bez2[4], CGFloat t)
65{
66  CGPoint q;
67  CGFloat mt = 1 - t;
68
69  bez1[0].x = bez[0].x;
70  bez1[0].y = bez[0].y;
71  bez2[3].x = bez[3].x;
72  bez2[3].y = bez[3].y;
73
74  q.x = mt * bez[1].x + t * bez[2].x;
75  q.y = mt * bez[1].y + t * bez[2].y;
76  bez1[1].x = mt * bez[0].x + t * bez[1].x;
77  bez1[1].y = mt * bez[0].y + t * bez[1].y;
78  bez2[2].x = mt * bez[2].x + t * bez[3].x;
79  bez2[2].y = mt * bez[2].y + t * bez[3].y;
80
81  bez1[2].x = mt * bez1[1].x + t * q.x;
82  bez1[2].y = mt * bez1[1].y + t * q.y;
83  bez2[1].x = mt * q.x + t * bez2[2].x;
84  bez2[1].y = mt * q.y + t * bez2[2].y;
85
86  bez1[3].x = bez2[0].x = mt * bez1[2].x + t * bez2[1].x;
87  bez1[3].y = bez2[0].y = mt * bez1[2].y + t * bez2[1].y;
88}
89
90@implementation RNSVGPathMeasure
91
92- (void)addLine:(CGPoint *)last next:(const CGPoint *)next
93{
94  NSArray *line = @[ [NSValue valueWithCGPoint:*last], [NSValue valueWithCGPoint:*next] ];
95  _pathLength += distance(*last, *next);
96  [_lengths addObject:[NSNumber numberWithDouble:_pathLength]];
97  [_lines addObject:line];
98  *last = *next;
99}
100
101- (void)reset
102{
103  _lengths = nil;
104  _lines = nil;
105  _isClosed = NO;
106  _lineCount = 0;
107  _pathLength = 0;
108  _path = nil;
109}
110
111- (void)extractPathData:(CGPathRef)path
112{
113  if (path == _path) {
114    return;
115  }
116  _path = path;
117  CGPoint origin = CGPointMake(0.0, 0.0);
118  CGPoint last = CGPointMake(0.0, 0.0);
119  _lengths = [NSMutableArray array];
120  _lines = [NSMutableArray array];
121  _isClosed = NO;
122  _lineCount = 0;
123  _pathLength = 0;
124  NSArray *elements = [RNSVGBezierElement elementsFromCGPath:path];
125  for (RNSVGBezierElement *element in elements) {
126    switch (element.elementType) {
127      case kCGPathElementMoveToPoint:
128        origin = last = element.point;
129        break;
130
131      case kCGPathElementAddLineToPoint: {
132        CGPoint next = element.point;
133        [self addLine:&last next:&next];
134        _lineCount++;
135        break;
136      }
137      case kCGPathElementAddQuadCurveToPoint:
138      case kCGPathElementAddCurveToPoint: {
139        // handle both curve types gracefully
140        CGPoint curveTo = element.point;
141        CGPoint ctrl1 = element.controlPoint1;
142        CGPoint ctrl2 = element.elementType == kCGPathElementAddQuadCurveToPoint ? ctrl1 : element.controlPoint2;
143
144        // this is the bezier for our current element
145        CGPoint bezier[4] = {last, ctrl1, ctrl2, curveTo};
146        NSValue *arr = [NSValue valueWithBytes:&bezier objCType:@encode(CGPoint[4])];
147        NSMutableArray *curves = [NSMutableArray arrayWithObjects:arr, nil];
148
149        for (NSInteger curveIndex = 0; curveIndex >= 0; curveIndex--) {
150          CGPoint bez[4];
151          [curves[curveIndex] getValue:&bez];
152          [curves removeLastObject];
153
154          // calculate the error rate of the curve vs
155          // a line segment between the start and end points
156          CGPoint ctrl1 = bez[1];
157          CGPoint ctrl2 = bez[2];
158          CGPoint next = bez[3];
159          CGFloat polyLen = distance(last, ctrl1) + distance(ctrl1, ctrl2) + distance(ctrl2, next);
160          CGFloat chordLen = distance(last, next);
161          CGFloat error = polyLen - chordLen;
162
163          // if the error is less than our accepted level of error
164          // then add a line, else, split the curve in half
165          if (error <= idealFlatness) {
166            [self addLine:&last next:&next];
167            _lineCount++;
168          } else {
169            CGPoint bez1[4], bez2[4];
170            subdivideBezierAtT(bez, bez1, bez2, .5);
171            [curves addObject:[NSValue valueWithBytes:&bez2 objCType:@encode(CGPoint[4])]];
172            [curves addObject:[NSValue valueWithBytes:&bez1 objCType:@encode(CGPoint[4])]];
173            curveIndex += 2;
174          }
175        }
176        break;
177      }
178
179      case kCGPathElementCloseSubpath: {
180        CGPoint next = origin;
181        [self addLine:&last next:&next];
182        _lineCount++;
183        _isClosed = YES;
184        break;
185      }
186
187      default:
188        break;
189    }
190  }
191}
192
193- (void)getPosAndTan:(CGFloat *)angle midPoint:(CGFloat)midPoint x:(CGFloat *)x y:(CGFloat *)y
194{
195  // Investigation suggests binary search is faster at lineCount >= 16
196  // https://gist.github.com/msand/4c7993319425f9d7933be58ad9ada1a4
197  NSUInteger i = _lineCount < 16
198      ? [_lengths indexOfObjectPassingTest:^(NSNumber *length, NSUInteger index, BOOL *_Nonnull stop) {
199          BOOL contains = midPoint <= [length doubleValue];
200          return contains;
201        }]
202      : [_lengths indexOfObject:[NSNumber numberWithDouble:midPoint]
203                  inSortedRange:NSMakeRange(0, _lineCount)
204                        options:NSBinarySearchingInsertionIndex
205                usingComparator:^(NSNumber *obj1, NSNumber *obj2) {
206                  return [obj1 compare:obj2];
207                }];
208
209  CGFloat totalLength = (CGFloat)[_lengths[i] doubleValue];
210  CGFloat prevLength = i == 0 ? 0 : (CGFloat)[_lengths[i - 1] doubleValue];
211
212  CGFloat length = totalLength - prevLength;
213  CGFloat percent = (midPoint - prevLength) / length;
214
215  NSArray *points = [_lines objectAtIndex:i];
216  CGPoint p1 = [[points objectAtIndex:0] CGPointValue];
217  CGPoint p2 = [[points objectAtIndex:1] CGPointValue];
218
219  CGFloat ldx = p2.x - p1.x;
220  CGFloat ldy = p2.y - p1.y;
221  *angle = atan2(ldy, ldx);
222  *x = p1.x + ldx * percent;
223  *y = p1.y + ldy * percent;
224}
225
226@end
227