1 // Copyright 2013 Howling Moon Software. All rights reserved.
2 // See http://chipmunk2d.net/legal.php for more information.
3
4 #include <stdlib.h>
5 #include <stdio.h>
6 #include <string.h>
7 #include <math.h>
8
9 #include "chipmunk/chipmunk_private.h"
10 #include "chipmunk/cpPolyline.h"
11
12
Next(int i,int count)13 static inline int Next(int i, int count){return (i+1)%count;}
14
15 //MARK: Polylines
16
17 #define DEFAULT_POLYLINE_CAPACITY 16
18
19 static int
cpPolylineSizeForCapacity(int capacity)20 cpPolylineSizeForCapacity(int capacity)
21 {
22 return sizeof(cpPolyline) + capacity*sizeof(cpVect);
23 }
24
25 static cpPolyline *
cpPolylineMake(int capacity)26 cpPolylineMake(int capacity)
27 {
28 capacity = (capacity > DEFAULT_POLYLINE_CAPACITY ? capacity : DEFAULT_POLYLINE_CAPACITY);
29
30 cpPolyline *line = (cpPolyline *)cpcalloc(1, cpPolylineSizeForCapacity(capacity));
31 line->count = 0;
32 line->capacity = capacity;
33
34 return line;
35 }
36
37 static cpPolyline *
cpPolylineMake2(int capacity,cpVect a,cpVect b)38 cpPolylineMake2(int capacity, cpVect a, cpVect b)
39 {
40 cpPolyline *line = cpPolylineMake(capacity);
41 line->count = 2;
42 line->verts[0] = a;
43 line->verts[1] = b;
44
45 return line;
46 }
47
48 static cpPolyline *
cpPolylineShrink(cpPolyline * line)49 cpPolylineShrink(cpPolyline *line)
50 {
51 line->capacity = line->count;
52 return cprealloc(line, cpPolylineSizeForCapacity(line->count));
53 }
54
55 void
cpPolylineFree(cpPolyline * line)56 cpPolylineFree(cpPolyline *line)
57 {
58 cpfree(line);
59 }
60
61 // Grow the allocated memory for a polyline.
62 static cpPolyline *
cpPolylineGrow(cpPolyline * line,int count)63 cpPolylineGrow(cpPolyline *line, int count)
64 {
65 line->count += count;
66
67 int capacity = line->capacity;
68 while(line->count > capacity) capacity *= 2;
69
70 if(line->capacity < capacity){
71 line->capacity = capacity;
72 line = cprealloc(line, cpPolylineSizeForCapacity(capacity));
73 }
74
75 return line;
76 }
77
78 // Push v onto the end of line.
79 static cpPolyline *
cpPolylinePush(cpPolyline * line,cpVect v)80 cpPolylinePush(cpPolyline *line, cpVect v)
81 {
82 int count = line->count;
83 line = cpPolylineGrow(line, 1);
84 line->verts[count] = v;
85
86 return line;
87 }
88
89 // Push v onto the beginning of line.
90 static cpPolyline *
cpPolylineEnqueue(cpPolyline * line,cpVect v)91 cpPolylineEnqueue(cpPolyline *line, cpVect v)
92 {
93 // TODO could optimize this to grow in both directions.
94 // Probably doesn't matter though.
95 int count = line->count;
96 line = cpPolylineGrow(line, 1);
97 memmove(line->verts + 1, line->verts, count*sizeof(cpVect));
98 line->verts[0] = v;
99
100 return line;
101 }
102
103 // Returns true if the polyline starts and ends with the same vertex.
104 cpBool
cpPolylineIsClosed(cpPolyline * line)105 cpPolylineIsClosed(cpPolyline *line)
106 {
107 return (line->count > 1 && cpveql(line->verts[0], line->verts[line->count-1]));
108 }
109
110 // Check if a cpPolyline is longer than a certain length
111 // Takes a range which can wrap around if the polyline is looped.
112 static cpBool
cpPolylineIsShort(cpVect * points,int count,int start,int end,cpFloat min)113 cpPolylineIsShort(cpVect *points, int count, int start, int end, cpFloat min)
114 {
115 cpFloat length = 0.0f;
116 for(int i=start; i!=end; i=Next(i, count)){
117 length += cpvdist(points[i], points[Next(i, count)]);
118 if(length > min) return cpFalse;
119 }
120
121 return cpTrue;
122 }
123
124 //MARK: Polyline Simplification
125
126 static inline cpFloat
Sharpness(cpVect a,cpVect b,cpVect c)127 Sharpness(cpVect a, cpVect b, cpVect c)
128 {
129 // TODO could speed this up by caching the normals instead of calculating each twice.
130 return cpvdot(cpvnormalize(cpvsub(a, b)), cpvnormalize(cpvsub(c, b)));
131 }
132
133 // Join similar adjacent line segments together. Works well for hard edged shapes.
134 // 'tol' is the minimum anglular difference in radians of a vertex.
135 cpPolyline *
cpPolylineSimplifyVertexes(cpPolyline * line,cpFloat tol)136 cpPolylineSimplifyVertexes(cpPolyline *line, cpFloat tol)
137 {
138 cpPolyline *reduced = cpPolylineMake2(0, line->verts[0], line->verts[1]);
139
140 cpFloat minSharp = -cpfcos(tol);
141
142 for(int i=2; i<line->count; i++){
143 cpVect vert = line->verts[i];
144 cpFloat sharp = Sharpness(reduced->verts[reduced->count - 2], reduced->verts[reduced->count - 1], vert);
145
146 if(sharp <= minSharp){
147 reduced->verts[reduced->count - 1] = vert;
148 } else {
149 reduced = cpPolylinePush(reduced, vert);
150 }
151 }
152
153 if(
154 cpPolylineIsClosed(line) &&
155 Sharpness(reduced->verts[reduced->count - 2], reduced->verts[0], reduced->verts[1]) < minSharp
156 ){
157 reduced->verts[0] = reduced->verts[reduced->count - 2];
158 reduced->count--;
159 }
160
161 // TODO shrink
162 return reduced;
163 }
164
165 // Recursive function used by cpPolylineSimplifyCurves().
166 static cpPolyline *
DouglasPeucker(cpVect * verts,cpPolyline * reduced,int length,int start,int end,cpFloat min,cpFloat tol)167 DouglasPeucker(
168 cpVect *verts, cpPolyline *reduced,
169 int length, int start, int end,
170 cpFloat min, cpFloat tol
171 ){
172 // Early exit if the points are adjacent
173 if((end - start + length)%length < 2) return reduced;
174
175 cpVect a = verts[start];
176 cpVect b = verts[end];
177
178 // Check if the length is below the threshold
179 if(cpvnear(a, b, min) && cpPolylineIsShort(verts, length, start, end, min)) return reduced;
180
181 // Find the maximal vertex to split and recurse on
182 cpFloat max = 0.0;
183 int maxi = start;
184
185 cpVect n = cpvnormalize(cpvperp(cpvsub(b, a)));
186 cpFloat d = cpvdot(n, a);
187
188 for(int i=Next(start, length); i!=end; i=Next(i, length)){
189 cpFloat dist = fabs(cpvdot(n, verts[i]) - d);
190
191 if(dist > max){
192 max = dist;
193 maxi = i;
194 }
195 }
196
197 if(max > tol){
198 reduced = DouglasPeucker(verts, reduced, length, start, maxi, min, tol);
199 reduced = cpPolylinePush(reduced, verts[maxi]);
200 reduced = DouglasPeucker(verts, reduced, length, maxi, end, min, tol);
201 }
202
203 return reduced;
204 }
205
206 // Recursively reduce the vertex count on a polyline. Works best for smooth shapes.
207 // 'tol' is the maximum error for the reduction.
208 // The reduced polyline will never be farther than this distance from the original polyline.
209 cpPolyline *
cpPolylineSimplifyCurves(cpPolyline * line,cpFloat tol)210 cpPolylineSimplifyCurves(cpPolyline *line, cpFloat tol)
211 {
212 cpPolyline *reduced = cpPolylineMake(line->count);
213
214 cpFloat min = tol/2.0f;
215
216 if(cpPolylineIsClosed(line)){
217 int start, end;
218 cpLoopIndexes(line->verts, line->count - 1, &start, &end);
219
220 reduced = cpPolylinePush(reduced, line->verts[start]);
221 reduced = DouglasPeucker(line->verts, reduced, line->count - 1, start, end, min, tol);
222 reduced = cpPolylinePush(reduced, line->verts[end]);
223 reduced = DouglasPeucker(line->verts, reduced, line->count - 1, end, start, min, tol);
224 reduced = cpPolylinePush(reduced, line->verts[start]);
225 } else {
226 reduced = cpPolylinePush(reduced, line->verts[0]);
227 reduced = DouglasPeucker(line->verts, reduced, line->count, 0, line->count - 1, min, tol);
228 reduced = cpPolylinePush(reduced, line->verts[line->count - 1]);
229 }
230
231 return cpPolylineShrink(reduced);
232 }
233
234 //MARK: Polyline Sets
235
236 cpPolylineSet *
cpPolylineSetAlloc(void)237 cpPolylineSetAlloc(void)
238 {
239 return (cpPolylineSet *)cpcalloc(1, sizeof(cpPolylineSet));
240 }
241
242 cpPolylineSet *
cpPolylineSetInit(cpPolylineSet * set)243 cpPolylineSetInit(cpPolylineSet *set)
244 {
245 set->count = 0;
246 set->capacity = 8;
247 set->lines = cpcalloc(set->capacity, sizeof(cpPolyline));
248
249 return set;
250 }
251
252
253 cpPolylineSet *
cpPolylineSetNew(void)254 cpPolylineSetNew(void)
255 {
256 return cpPolylineSetInit(cpPolylineSetAlloc());
257 }
258
259 void
cpPolylineSetDestroy(cpPolylineSet * set,cpBool freePolylines)260 cpPolylineSetDestroy(cpPolylineSet *set, cpBool freePolylines)
261 {
262 if(freePolylines){
263 for(int i=0; i<set->count; i++){
264 cpPolylineFree(set->lines[i]);
265 }
266 }
267
268 cpfree(set->lines);
269 }
270
271
272 void
cpPolylineSetFree(cpPolylineSet * set,cpBool freePolylines)273 cpPolylineSetFree(cpPolylineSet *set, cpBool freePolylines)
274 {
275 if(set){
276 cpPolylineSetDestroy(set, freePolylines);
277 cpfree(set);
278 }
279 }
280
281 // Find the polyline that ends with v.
282 static int
cpPolylineSetFindEnds(cpPolylineSet * set,cpVect v)283 cpPolylineSetFindEnds(cpPolylineSet *set, cpVect v){
284 int count = set->count;
285 cpPolyline **lines = set->lines;
286
287 for(int i=0; i<count; i++){
288 cpPolyline *line = lines[i];
289 if(cpveql(line->verts[line->count - 1], v)) return i;
290 }
291
292 return -1;
293 }
294
295 // Find the polyline that starts with v.
296 static int
cpPolylineSetFindStarts(cpPolylineSet * set,cpVect v)297 cpPolylineSetFindStarts(cpPolylineSet *set, cpVect v){
298 int count = set->count;
299 cpPolyline **lines = set->lines;
300
301 for(int i=0; i<count; i++){
302 if(cpveql(lines[i]->verts[0], v)) return i;
303 }
304
305 return -1;
306 }
307
308 // Add a new polyline to a polyline set.
309 static void
cpPolylineSetPush(cpPolylineSet * set,cpPolyline * line)310 cpPolylineSetPush(cpPolylineSet *set, cpPolyline *line)
311 {
312 // grow set
313 set->count++;
314 if(set->count > set->capacity){
315 set->capacity *= 2;
316 set->lines = cprealloc(set->lines, set->capacity*sizeof(cpPolyline));
317 }
318
319 set->lines[set->count - 1] = line;
320 }
321
322 // Add a new polyline to a polyline set.
323 static void
cpPolylineSetAdd(cpPolylineSet * set,cpVect v0,cpVect v1)324 cpPolylineSetAdd(cpPolylineSet *set, cpVect v0, cpVect v1)
325 {
326 cpPolylineSetPush(set, cpPolylineMake2(DEFAULT_POLYLINE_CAPACITY, v0, v1));
327 }
328
329 // Join two cpPolylines in a polyline set together.
330 static void
cpPolylineSetJoin(cpPolylineSet * set,int before,int after)331 cpPolylineSetJoin(cpPolylineSet *set, int before, int after)
332 {
333 cpPolyline *lbefore = set->lines[before];
334 cpPolyline *lafter = set->lines[after];
335
336 // append
337 int count = lbefore->count;
338 lbefore = cpPolylineGrow(lbefore, lafter->count);
339 memmove(lbefore->verts + count, lafter->verts, lafter->count*sizeof(cpVect));
340 set->lines[before] = lbefore;
341
342 // delete lafter
343 set->count--;
344 cpPolylineFree(set->lines[after]);
345 set->lines[after] = set->lines[set->count];
346 }
347
348 // Add a segment to a polyline set.
349 // A segment will either start a new polyline, join two others, or add to or loop an existing polyline.
350 void
cpPolylineSetCollectSegment(cpVect v0,cpVect v1,cpPolylineSet * lines)351 cpPolylineSetCollectSegment(cpVect v0, cpVect v1, cpPolylineSet *lines)
352 {
353 int before = cpPolylineSetFindEnds(lines, v0);
354 int after = cpPolylineSetFindStarts(lines, v1);
355
356 if(before >= 0 && after >= 0){
357 if(before == after){
358 // loop by pushing v1 onto before
359 lines->lines[before] = cpPolylinePush(lines->lines[before], v1);
360 } else {
361 // join before and after
362 cpPolylineSetJoin(lines, before, after);
363 }
364 } else if(before >= 0){
365 // push v1 onto before
366 lines->lines[before] = cpPolylinePush(lines->lines[before], v1);
367 } else if(after >= 0){
368 // enqueue v0 onto after
369 lines->lines[after] = cpPolylineEnqueue(lines->lines[after], v0);
370 } else {
371 // create new line from v0 and v1
372 cpPolylineSetAdd(lines, v0, v1);
373 }
374 }
375
376 //MARK: Convex Hull Functions
377
378 cpPolyline *
cpPolylineToConvexHull(cpPolyline * line,cpFloat tol)379 cpPolylineToConvexHull(cpPolyline *line, cpFloat tol)
380 {
381 cpPolyline *hull = cpPolylineMake(line->count + 1);
382 hull->count = cpConvexHull(line->count, line->verts, hull->verts, NULL, tol);
383 hull = cpPolylinePush(hull, hull->verts[0]);
384
385 return cpPolylineShrink(hull);
386 }
387
388 //MARK: Approximate Concave Decompostition
389
390 struct Notch {
391 int i;
392 cpFloat d;
393 cpVect v;
394 cpVect n;
395 };
396
397 static cpFloat
FindSteiner(int count,cpVect * verts,struct Notch notch)398 FindSteiner(int count, cpVect *verts, struct Notch notch)
399 {
400 cpFloat min = INFINITY;
401 cpFloat feature = -1.0;
402
403 for(int i=1; i<count-1; i++){
404 int index = (notch.i + i)%count;
405
406 cpVect seg_a = verts[index];
407 cpVect seg_b = verts[Next(index, count)];
408
409 cpFloat thing_a = cpvcross(notch.n, cpvsub(seg_a, notch.v));
410 cpFloat thing_b = cpvcross(notch.n, cpvsub(seg_b, notch.v));
411 if(thing_a*thing_b <= 0.0){
412 cpFloat t = thing_a/(thing_a - thing_b);
413 cpFloat dist = cpvdot(notch.n, cpvsub(cpvlerp(seg_a, seg_b, t), notch.v));
414
415 if(dist >= 0.0 && dist <= min){
416 min = dist;
417 feature = index + t;
418 }
419 }
420 }
421
422 return feature;
423 }
424
425 //static cpFloat
426 //FindSteiner2(cpVect *verts, int count, struct Notch notch)
427 //{
428 // cpVect a = verts[(notch.i + count - 1)%count];
429 // cpVect b = verts[(notch.i + 1)%count];
430 // cpVect n = cpvnormalize(cpvadd(cpvnormalize(cpvsub(notch.v, a)), cpvnormalize(cpvsub(notch.v, b))));
431 //
432 // cpFloat min = INFINITY;
433 // cpFloat feature = -1.0;
434 //
435 // for(int i=1; i<count-1; i++){
436 // int index = (notch.i + i)%count;
437 //
438 // cpVect seg_a = verts[index];
439 // cpVect seg_b = verts[Next(index, count)];
440 //
441 // cpFloat thing_a = cpvcross(n, cpvsub(seg_a, notch.v));
442 // cpFloat thing_b = cpvcross(n, cpvsub(seg_b, notch.v));
443 // if(thing_a*thing_b <= 0.0){
444 // cpFloat t = thing_a/(thing_a - thing_b);
445 // cpFloat dist = cpvdot(n, cpvsub(cpvlerp(seg_a, seg_b, t), notch.v));
446 //
447 // if(dist >= 0.0 && dist <= min){
448 // min = dist;
449 // feature = index + t;
450 // }
451 // }
452 // }
453 //
454 // cpAssertSoft(feature >= 0.0, "No closest features detected. This is likely due to a self intersecting polygon.");
455 // return feature;
456 //}
457
458 //struct Range {cpFloat min, max;};
459 //static inline struct Range
460 //clip_range(cpVect delta_a, cpVect delta_b, cpVect clip)
461 //{
462 // cpFloat da = cpvcross(delta_a, clip);
463 // cpFloat db = cpvcross(delta_b, clip);
464 // cpFloat clamp = da/(da - db);
465 // if(da > db){
466 // return (struct Range){-INFINITY, clamp};
467 // } else if(da < db){
468 // return (struct Range){clamp, INFINITY};
469 // } else {
470 // return (struct Range){-INFINITY, INFINITY};
471 // }
472 //}
473 //
474 //static cpFloat
475 //FindSteiner3(cpVect *verts, int count, struct Notch notch)
476 //{
477 // cpFloat min = INFINITY;
478 // cpFloat feature = -1.0;
479 //
480 // cpVect support_a = verts[(notch.i - 1 + count)%count];
481 // cpVect support_b = verts[(notch.i + 1)%count];
482 //
483 // cpVect clip_a = cpvlerp(support_a, support_b, 0.1);
484 // cpVect clip_b = cpvlerp(support_b, support_b, 0.9);
485 //
486 // for(int i=1; i<count - 1; i++){
487 // int index = (notch.i + i)%count;
488 // cpVect seg_a = verts[index];
489 // cpVect seg_b = verts[Next(index, count)];
490 //
491 // cpVect delta_a = cpvsub(seg_a, notch.v);
492 // cpVect delta_b = cpvsub(seg_b, notch.v);
493 //
494 // // Ignore if the segment faces away from the point.
495 // if(cpvcross(delta_b, delta_a) > 0.0){
496 // struct Range range1 = clip_range(delta_a, delta_b, cpvsub(notch.v, clip_a));
497 // struct Range range2 = clip_range(delta_a, delta_b, cpvsub(clip_b, notch.v));
498 //
499 // cpFloat min_t = cpfmax(0.0, cpfmax(range1.min, range2.min));
500 // cpFloat max_t = cpfmin(1.0, cpfmin(range1.max, range2.max));
501 //
502 // // Ignore if the segment has been completely clipped away.
503 // if(min_t < max_t){
504 // cpVect seg_delta = cpvsub(seg_b, seg_a);
505 // cpFloat closest_t = cpfclamp(cpvdot(seg_delta, cpvsub(notch.v, seg_a))/cpvlengthsq(seg_delta), min_t, max_t);
506 // cpVect closest = cpvlerp(seg_a, seg_b, closest_t);
507 //
508 // cpFloat dist = cpvdistsq(notch.v, closest);
509 // if(dist < min){
510 // min = dist;
511 // feature = index + closest_t;
512 // }
513 // }
514 // }
515 // }
516 //
517 // cpAssertWarn(feature >= 0.0, "Internal Error: No closest features detected.");
518 // return feature;
519 //}
520
521 //static cpBool
522 //VertexUnobscured(int count, cpVect *verts, int index, int notch_i)
523 //{
524 // cpVect v = verts[notch_i];
525 // cpVect n = cpvnormalize(cpvsub(verts[index], v));
526 //
527 // for(int i=0; i<count; i++){
528 // if(i == index || i == Next(i, count) || i == notch_i || i == Next(notch_i, count)) continue;
529 //
530 // cpVect seg_a = verts[i];
531 // cpVect seg_b = verts[Next(i, count)];
532 //
533 // cpFloat thing_a = cpvcross(n, cpvsub(seg_a, v));
534 // cpFloat thing_b = cpvcross(n, cpvsub(seg_b, v));
535 // if(thing_a*thing_b <= 0.0) return cpTrue;
536 // }
537 //
538 // return cpFalse;
539 //}
540 //
541 //static cpFloat
542 //FindSteiner4(int count, cpVect *verts, struct Notch notch, cpFloat *convexity)
543 //{
544 // cpFloat min = INFINITY;
545 // cpFloat feature = -1.0;
546 //
547 // for(int i=Next(notch.b, count); i!=notch.a; i=Next(i, count)){
548 // cpVect v = verts[i];
549 // cpFloat weight = (1.0 + 0.1*convexity[i])/(1.0*cpvdist(notch.v, v));
550 //
551 // if(weight <= min && VertexUnobscured(count, verts, i, notch.i)){
552 // min = weight;
553 // feature = i;
554 // }
555 // }
556 //
557 // cpAssertSoft(feature >= 0.0, "No closest features detected. This is likely due to a self intersecting polygon.");
558 // return feature;
559 //}
560
561 static struct Notch
DeepestNotch(int count,cpVect * verts,int hullCount,cpVect * hullVerts,int first,cpFloat tol)562 DeepestNotch(int count, cpVect *verts, int hullCount, cpVect *hullVerts, int first, cpFloat tol)
563 {
564 struct Notch notch = {};
565 int j = Next(first, count);
566
567 for(int i=0; i<hullCount; i++){
568 cpVect a = hullVerts[i];
569 cpVect b = hullVerts[Next(i, hullCount)];
570
571 // TODO use a cross check instead?
572 cpVect n = cpvnormalize(cpvrperp(cpvsub(a, b)));
573 cpFloat d = cpvdot(n, a);
574
575 cpVect v = verts[j];
576 while(!cpveql(v, b)){
577 cpFloat depth = cpvdot(n, v) - d;
578
579 if(depth > notch.d){
580 notch.d = depth;
581 notch.i = j;
582 notch.v = v;
583 notch.n = n;
584 }
585
586 j = Next(j, count);
587 v = verts[j];
588 }
589
590 j = Next(j, count);
591 }
592
593 return notch;
594 }
595
IMAX(int a,int b)596 static inline int IMAX(int a, int b){return (a > b ? a : b);}
597
598 static void
ApproximateConcaveDecomposition(cpVect * verts,int count,cpFloat tol,cpPolylineSet * set)599 ApproximateConcaveDecomposition(cpVect *verts, int count, cpFloat tol, cpPolylineSet *set)
600 {
601 int first;
602 cpVect *hullVerts = alloca(count*sizeof(cpVect));
603 int hullCount = cpConvexHull(count, verts, hullVerts, &first, 0.0);
604
605 if(hullCount != count){
606 struct Notch notch = DeepestNotch(count, verts, hullCount, hullVerts, first, tol);
607
608 if(notch.d > tol){
609 cpFloat steiner_it = FindSteiner(count, verts, notch);
610
611 if(steiner_it >= 0.0){
612 int steiner_i = (int)steiner_it;
613 cpVect steiner = cpvlerp(verts[steiner_i], verts[Next(steiner_i, count)], steiner_it - steiner_i);
614
615 // Vertex counts NOT including the steiner point.
616 int sub1_count = (steiner_i - notch.i + count)%count + 1;
617 int sub2_count = count - (steiner_i - notch.i + count)%count;
618 cpVect *scratch = alloca((IMAX(sub1_count, sub2_count) + 1)*sizeof(cpVect));
619
620 for(int i=0; i<sub1_count; i++) scratch[i] = verts[(notch.i + i)%count];
621 scratch[sub1_count] = steiner;
622 ApproximateConcaveDecomposition(scratch, sub1_count + 1, tol, set);
623
624 for(int i=0; i<sub2_count; i++) scratch[i] = verts[(steiner_i + 1 + i)%count];
625 scratch[sub2_count] = steiner;
626 ApproximateConcaveDecomposition(scratch, sub2_count + 1, tol, set);
627
628 return;
629 }
630 }
631 }
632
633 cpPolyline *hull = cpPolylineMake(hullCount + 1);
634
635 memcpy(hull->verts, hullVerts, hullCount*sizeof(cpVect));
636 hull->verts[hullCount] = hullVerts[0];
637 hull->count = hullCount + 1;
638
639 cpPolylineSetPush(set, hull);
640 }
641
642 cpPolylineSet *
cpPolylineConvexDecomposition_BETA(cpPolyline * line,cpFloat tol)643 cpPolylineConvexDecomposition_BETA(cpPolyline *line, cpFloat tol)
644 {
645 cpAssertSoft(cpPolylineIsClosed(line), "Cannot decompose an open polygon.");
646 cpAssertSoft(cpAreaForPoly(line->count, line->verts, 0.0) >= 0.0, "Winding is backwards. (Are you passing a hole?)");
647
648 cpPolylineSet *set = cpPolylineSetNew();
649 ApproximateConcaveDecomposition(line->verts, line->count - 1, tol, set);
650
651 return set;
652 }
653