framework2

1
#ifndef OF_POLYLINE_H
2
#include "ofPolyline.h"
3
#endif
4

5
#include "ofRectangle.h"
6
#include "ofGraphicsBaseTypes.h"
7
#include "ofVectorMath.h"
8
#include "ofAppRunner.h"
9
#include "ofMath.h"
10
#include "ofLog.h"
11
#include "ofConstants.h"
12

13
//----------------------------------------------------------
14
template<class T>
15
ofPolyline_<T>::ofPolyline_(){
16
    setRightVector();
17
	clear();
18
}
19

20
//----------------------------------------------------------
21
template<class T>
22
ofPolyline_<T>::ofPolyline_(const std::vector<T>& verts){
23
    setRightVector();
24
	clear();
25
	addVertices(verts);
26
}
27

28
//----------------------------------------------------------
29
template<class T>
30
ofPolyline_<T> ofPolyline_<T>::fromRectangle(const ofRectangle& rect) {
31
	ofPolyline_ polyline;
32
    polyline.addVertex(rect.getMin());
33
    polyline.addVertex(rect.getMaxX(),rect.getMinY());
34
    polyline.addVertex(rect.getMax());
35
    polyline.addVertex(rect.getMinX(),rect.getMaxY());
36
    polyline.close();
37
    return polyline;
38
}
39

40
//----------------------------------------------------------
41
template<class T>
42
void ofPolyline_<T>::clear() {
43
	setClosed(false);
44
	points.clear();
45
	curveVertices.clear();
46
    flagHasChanged();
47
}
48

49
//----------------------------------------------------------
50
template<class T>
51
void ofPolyline_<T>::addVertex(const T& p) {
52
	curveVertices.clear();
53
	points.push_back(p);
54
    flagHasChanged();
55
}
56

57
//----------------------------------------------------------
58
template<class T>
59
void ofPolyline_<T>::addVertex(float x, float y, float z) {
60
	curveVertices.clear();
61
	addVertex(T(x,y,z));
62
    flagHasChanged();
63
}
64

65
//----------------------------------------------------------
66
template<class T>
67
void ofPolyline_<T>::addVertices(const std::vector<T>& verts) {
68
	curveVertices.clear();
69
	points.insert( points.end(), verts.begin(), verts.end() );
70
    flagHasChanged();
71
}
72

73
//----------------------------------------------------------
74
template<class T>
75
void ofPolyline_<T>::addVertices(const T* verts, int numverts) {
76
	curveVertices.clear();
77
	points.insert( points.end(), verts, verts + numverts );
78
    flagHasChanged();
79
}
80

81
//----------------------------------------------------------
82
template<class T>
83
void ofPolyline_<T>::insertVertex(const T &p, int index) {
84
    curveVertices.clear();
85
    points.insert(points.begin()+index, p);
86
    flagHasChanged();
87
}
88

89
//----------------------------------------------------------
90
template<class T>
91
void ofPolyline_<T>::insertVertex(float x, float y, float z, int index) {
92
	insertVertex(T(x, y, z), index);
93
}
94

95

96
//----------------------------------------------------------
97
template<class T>
98
void ofPolyline_<T>::removeVertex(int index) {
99
	if(index >= points.size()){
100
		ofLogError("ofPolyline") << "removeVertex(): ignoring out of range index " << index << ", number of vertices is" << points.size();
101
	}else{
102
		curveVertices.clear();
103
		points.erase(points.begin()+index);
104
		flagHasChanged();
105
	}
106
}
107

108

109
//----------------------------------------------------------
110
template<class T>
111
size_t ofPolyline_<T>::size() const {
112
	return points.size();
113
}
114

115
//----------------------------------------------------------
116
template<class T>
117
const T& ofPolyline_<T>::operator[] (int index) const {
118
	return points[index];
119
}
120

121
//----------------------------------------------------------
122
template<class T>
123
T& ofPolyline_<T>::operator[] (int index) {
124
    flagHasChanged();
125
	return points[index];
126
}
127

128
//----------------------------------------------------------
129
template<class T>
130
void ofPolyline_<T>::resize(size_t size){
131
	points.resize(size);
132
    flagHasChanged();
133
}
134

135
//----------------------------------------------------------
136
template<class T>
137
void ofPolyline_<T>::setClosed( bool tf ) {
138
	bClosed = tf;
139
    flagHasChanged();
140
}
141

142
//----------------------------------------------------------
143
template<class T>
144
bool ofPolyline_<T>::isClosed() const {
145
	return bClosed;
146
}
147

148
//----------------------------------------------------------
149
template<class T>
150
void ofPolyline_<T>::close(){
151
    setClosed(true);
152
}
153

154
//----------------------------------------------------------
155
template<class T>
156
bool ofPolyline_<T>::hasChanged(){
157
    if(bHasChanged){
158
        bHasChanged=false;
159
        return true;
160
    }else{
161
        return false;
162
    }
163
}
164

165
//----------------------------------------------------------
166
template<class T>
167
void ofPolyline_<T>::flagHasChanged() {
168
    bHasChanged = true;
169
    bCacheIsDirty = true;
170
}
171

172
//----------------------------------------------------------
173
template<class T>
174
std::vector<T> & ofPolyline_<T>::getVertices(){
175
    flagHasChanged();
176
	return points;
177
}
178

179
//----------------------------------------------------------
180
template<class T>
181
const std::vector<T> & ofPolyline_<T>::getVertices() const {
182
	return points;
183
}
184

185

186
//----------------------------------------------------------
187
template<class T>
188
void ofPolyline_<T>::setCircleResolution(int res){
189
	if (res > 1 && res != (int)circlePoints.size()){
190
		circlePoints.resize(res);
191
        
192
		float angle = 0.0f;
193
		const float angleAdder = glm::two_pi<float>() / (float)res;
194
		for (int i = 0; i < res; i++){
195
			circlePoints[i].x = cos(angle);
196
			circlePoints[i].y = sin(angle);
197
			circlePoints[i].z = 0.0f;
198
			angle += angleAdder;
199
		}
200
	}
201
}
202

203
//----------------------------------------------------------
204
template<class T>
205
// wraps any radian angle -FLT_MAX to +FLT_MAX into 0->2PI range.
206
// TODO, make angle treatment consistent across all functions
207
// should always be radians?  or should this take degrees?
208
// used internally, so perhaps not as important
209
float ofPolyline_<T>::wrapAngle(float angleRadians) {
210
	return ofWrap(angleRadians, 0.0f, glm::two_pi<float>());
211
}
212

213
//----------------------------------------------------------
214
template<class T>
215
void ofPolyline_<T>::bezierTo( const T & cp1, const T & cp2, const T & to, int curveResolution ){
216
	// if, and only if poly vertices has points, we can make a bezier
217
	// from the last point
218
	curveVertices.clear();
219
    
220
	// the resolultion with which we computer this bezier
221
	// is arbitrary, can we possibly make it dynamic?
222
    
223
	if (size() > 0){
224
		float x0 = points[size()-1].x;
225
		float y0 = points[size()-1].y;
226
		float z0 = points[size()-1].z;
227
        
228
		float   ax, bx, cx;
229
		float   ay, by, cy;
230
		float   az, bz, cz;
231
		float   t, t2, t3;
232
		float   x, y, z;
233
        
234
		// polynomial coefficients
235
		cx = 3.0f * (cp1.x - x0);
236
		bx = 3.0f * (cp2.x - cp1.x) - cx;
237
		ax = to.x - x0 - cx - bx;
238
        
239
		cy = 3.0f * (cp1.y - y0);
240
		by = 3.0f * (cp2.y - cp1.y) - cy;
241
		ay = to.y - y0 - cy - by;
242
        
243
		cz = 3.0f * (cp1.z - z0);
244
		bz = 3.0f * (cp2.z - cp1.z) - cz;
245
		az = to.z - z0 - cz - bz;
246
        
247
		for (int i = 1; i <= curveResolution; i++){
248
			t 	=  (float)i / (float)(curveResolution);
249
			t2 = t * t;
250
			t3 = t2 * t;
251
			x = (ax * t3) + (bx * t2) + (cx * t) + x0;
252
			y = (ay * t3) + (by * t2) + (cy * t) + y0;
253
			z = (az * t3) + (bz * t2) + (cz * t) + z0;
254
			points.emplace_back(x,y,z);
255
		}
256
	}
257
    flagHasChanged();
258
}
259

260
//----------------------------------------------------------
261
template<class T>
262
void ofPolyline_<T>::quadBezierTo(float x1, float y1, float z1, float x2, float y2, float z2, float x3, float y3, float z3, int curveResolution){
263
	curveVertices.clear();
264
	for(int i=0; i <= curveResolution; i++){
265
		double t = (double)i / (double)(curveResolution);
266
		double a = (1.0 - t)*(1.0 - t);
267
		double b = 2.0 * t * (1.0 - t);
268
		double c = t*t;
269
		double x = a * x1 + b * x2 + c * x3;
270
		double y = a * y1 + b * y2 + c * y3;
271
		double z = a * z1 + b * z2 + c * z3;
272
		points.emplace_back(x, y, z);
273
	}
274
    flagHasChanged();
275
}
276

277
//----------------------------------------------------------
278
template<class T>
279
void ofPolyline_<T>::curveTo( const T & to, int curveResolution ){
280
    
281
	curveVertices.push_back(to);
282
    
283
	if (curveVertices.size() == 4){
284
        
285
		float x0 = curveVertices[0].x;
286
		float y0 = curveVertices[0].y;
287
		float z0 = curveVertices[0].z;
288
		float x1 = curveVertices[1].x;
289
		float y1 = curveVertices[1].y;
290
		float z1 = curveVertices[1].z;
291
		float x2 = curveVertices[2].x;
292
		float y2 = curveVertices[2].y;
293
		float z2 = curveVertices[2].z;
294
		float x3 = curveVertices[3].x;
295
		float y3 = curveVertices[3].y;
296
		float z3 = curveVertices[3].z;
297
        
298
		float t,t2,t3;
299
		float x,y,z;
300
        
301
		for (int i = 1; i <= curveResolution; i++){
302
            
303
			t 	=  (float)i / (float)(curveResolution);
304
			t2 	= t * t;
305
			t3 	= t2 * t;
306
            
307
			x = 0.5f * ( ( 2.0f * x1 ) +
308
                        ( -x0 + x2 ) * t +
309
                        ( 2.0f * x0 - 5.0f * x1 + 4 * x2 - x3 ) * t2 +
310
                        ( -x0 + 3.0f * x1 - 3.0f * x2 + x3 ) * t3 );
311
            
312
			y = 0.5f * ( ( 2.0f * y1 ) +
313
                        ( -y0 + y2 ) * t +
314
                        ( 2.0f * y0 - 5.0f * y1 + 4 * y2 - y3 ) * t2 +
315
                        ( -y0 + 3.0f * y1 - 3.0f * y2 + y3 ) * t3 );
316
            
317
			z = 0.5f * ( ( 2.0f * z1 ) +
318
                        ( -z0 + z2 ) * t +
319
                        ( 2.0f * z0 - 5.0f * z1 + 4 * z2 - z3 ) * t2 +
320
                        ( -z0 + 3.0f * z1 - 3.0f * z2 + z3 ) * t3 );
321
            
322
			points.emplace_back(x,y,z);
323
		}
324
		curveVertices.pop_front();
325
	}
326
    flagHasChanged();
327
}
328

329
//----------------------------------------------------------
330
template<class T>
331
void ofPolyline_<T>::arc(const T & center, float radiusX, float radiusY, float angleBegin, float angleEnd, bool clockwise, int circleResolution){
332
    
333
    if(circleResolution<=1) circleResolution=2;
334
    setCircleResolution(circleResolution);
335
    points.reserve(points.size()+circleResolution);
336

337
    const float epsilon = 0.0001f;
338
    
339
    const size_t nCirclePoints = circlePoints.size();
340
    float segmentArcSize  = glm::two_pi<float>() / (float)nCirclePoints;
341
    
342
    // convert angles to radians and wrap them into the range 0-M_TWO_PI and
343
    float angleBeginRad = wrapAngle(ofDegToRad(angleBegin));
344
    float angleEndRad =   wrapAngle(ofDegToRad(angleEnd));
345
    
346
    while(angleBeginRad >= angleEndRad) angleEndRad += glm::two_pi<float>();
347
    
348
    // determine the directional angle delta
349
    float d = clockwise ? angleEndRad - angleBeginRad : angleBeginRad - angleEndRad;
350
    // find the shortest angle delta, clockwise delta direction yeilds POSITIVE values
351
    float deltaAngle = atan2(sin(d),cos(d));
352
    
353
    // establish the remaining angle that we have to work through
354
    float remainingAngle = deltaAngle;
355
    
356
    // if the delta angle is in the CCW direction OR the start and stop angles are
357
    // effectively the same adjust the remaining angle to be a be a full rotation
358
    if(deltaAngle < 0 || std::abs(deltaAngle) < epsilon) remainingAngle += glm::two_pi<float>();
359
    
360
	T radii(radiusX, radiusY, 0.f);
361
	T point(0);
362
    
363
    int currentLUTIndex = 0;
364
    bool isFirstPoint = true; // special case for the first point
365
    
366
    while(remainingAngle > 0) {
367
        if(isFirstPoint) {
368
            // TODO: should this be the exact point on the circle or
369
            // should it be an intersecting point on the line that connects two
370
            // surrounding LUT points?
371
            //
372
            // get the EXACT first point requested (for points that
373
            // don't fall precisely on a LUT entry)
374
			point = T(cos(angleBeginRad), sin(angleBeginRad), 0.f);
375
            // set up the get any in between points from the LUT
376
            float ratio = angleBeginRad / glm::two_pi<float>() * (float)nCirclePoints;
377
            currentLUTIndex = clockwise ? (int)ceil(ratio) : (int)floor(ratio);
378
            float lutAngleAtIndex = currentLUTIndex * segmentArcSize;
379
            // the angle between the beginning angle and the next angle in the LUT table
380
            float d = clockwise ? (lutAngleAtIndex - angleBeginRad) : (angleBeginRad - lutAngleAtIndex);
381
            float firstPointDelta = atan2(sin(d),cos(d)); // negative is in the clockwise direction
382
            
383
            // if the are "equal", get the next one CCW
384
            if(std::abs(firstPointDelta) < epsilon) {
385
                currentLUTIndex = clockwise ? (currentLUTIndex + 1) : (currentLUTIndex - 1);
386
                firstPointDelta = segmentArcSize; // we start at the next lut point
387
            }
388
            
389
            // start counting from the offset
390
            remainingAngle -= firstPointDelta;
391
            isFirstPoint = false;
392
        } else {
393
			point = T(circlePoints[currentLUTIndex].x, circlePoints[currentLUTIndex].y, 0.f);
394
            if(clockwise) {
395
                currentLUTIndex++; // go to the next LUT point
396
                remainingAngle -= segmentArcSize; // account for next point
397
                // if the angle overshoots, then the while loop will fail next time
398
            } else {
399
                currentLUTIndex--; // go to the next LUT point
400
                remainingAngle -= segmentArcSize; // account for next point
401
                // if the angle overshoots, then the while loop will fail next time
402
            }
403
        }
404
        
405
        // keep the current lut index in range
406
        if(clockwise) {
407
            currentLUTIndex = currentLUTIndex % nCirclePoints;
408
        } else {
409
            if(currentLUTIndex < 0) currentLUTIndex = nCirclePoints + currentLUTIndex;
410
        }
411
        
412
        // add the point to the poly line
413
        point = point * radii + center;
414
        points.push_back(point);
415
        
416
        // if the next LUT point moves us past the end angle then
417
        // add a a point a the exact end angle and call it finished
418
        if(remainingAngle < epsilon) {
419
			point = T(cos(angleEndRad), sin(angleEndRad), 0.f);
420
            point = point * radii + center;
421
            points.push_back(point);
422
            remainingAngle = 0; // call it finished, the next while loop test will fail
423
        }
424
    }
425
    flagHasChanged();
426
}
427

428
//----------------------------------------------------------
429
template<class T>
430
float ofPolyline_<T>::getPerimeter() const {
431
    if(points.size() < 2) {
432
        return 0;
433
    } else {
434
        updateCache();
435
        return lengths.back();
436
    }
437
}
438

439
//----------------------------------------------------------
440
template<class T>
441
float ofPolyline_<T>::getArea() const{
442
    updateCache();
443
    return area;
444
}
445

446
//----------------------------------------------------------
447
template<class T>
448
T ofPolyline_<T>::getCentroid2D() const{
449
    updateCache();
450
    return centroid2D;
451
}
452

453
//----------------------------------------------------------
454
template<class T>
455
ofRectangle ofPolyline_<T>::getBoundingBox() const {
456
    
457
	ofRectangle box;
458
    for(size_t i = 0; i < size(); i++) {
459
        if(i == 0) {
460
            box.set(points[i],0,0);
461
        } else {
462
            box.growToInclude(points[i]);
463
        }
464
    }
465
	return box;
466
}
467

468
//----------------------------------------------------------
469
template<class T>
470
ofPolyline_<T> ofPolyline_<T>::getSmoothed(int smoothingSize, float smoothingShape) const {
471
	int n = size();
472
	smoothingSize = ofClamp(smoothingSize, 0, n);
473
	smoothingShape = ofClamp(smoothingShape, 0, 1);
474
	
475
	// precompute weights and normalization
476
	std::vector<float> weights;
477
	weights.resize(smoothingSize);
478
	// side weights
479
	for(int i = 1; i < smoothingSize; i++) {
480
		float curWeight = ofMap(i, 0, smoothingSize, 1, smoothingShape);
481
		weights[i] = curWeight;
482
	}
483
	
484
	// make a copy of this polyline
485
	ofPolyline_ result = *this;
486
	
487
	for(int i = 0; i < n; i++) {
488
		float sum = 1; // center weight
489
		for(int j = 1; j < smoothingSize; j++) {
490
			T cur(0);
491
			int leftPosition = i - j;
492
			int rightPosition = i + j;
493
			if(leftPosition < 0 && bClosed) {
494
				leftPosition += n;
495
			}
496
			if(leftPosition >= 0) {
497
				cur += points[leftPosition];
498
				sum += weights[j];
499
			}
500
			if(rightPosition >= n && bClosed) {
501
				rightPosition -= n;
502
			}
503
			if(rightPosition < n) {
504
				cur += points[rightPosition];
505
				sum += weights[j];
506
			}
507
			result[i] += cur * weights[j];
508
		}
509
		result[i] /= sum;
510
	}
511
	
512
	return result;
513
}
514

515
//----------------------------------------------------------
516
template<class T>
517
ofPolyline_<T> ofPolyline_<T>::getResampledBySpacing(float spacing) const {
518
    if(spacing==0 || size() == 0) return *this;
519
	ofPolyline_ poly;
520
    float totalLength = getPerimeter();
521
    float f=0;
522
    for(f=0; f<=totalLength; f += spacing) {
523
        poly.lineTo(getPointAtLength(f));
524
    }
525
    
526
    if(!isClosed()) {
527
        if( f != totalLength ){
528
            poly.lineTo(points.back());
529
        }
530
        poly.setClosed(false);
531
    } else {
532
        poly.setClosed(true);
533
    }
534
    
535
    return poly;
536
}
537

538
//----------------------------------------------------------
539
template<class T>
540
ofPolyline_<T> ofPolyline_<T>::getResampledByCount(int count) const {
541
	float perimeter = getPerimeter();
542
	if(count < 2) {
543
		ofLogWarning("ofPolyline_") << "getResampledByCount(): requested " << count <<" points, using minimum count of 2 ";
544
		count = 2;
545
    }
546
	return ofPolyline_<T>::getResampledBySpacing(perimeter / (count-1));
547
}
548

549
//----------------------------------------------------------
550
// http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/
551
template<class T>
552
inline T getClosestPointUtil(const T& p1, const T& p2, const T& p3, float* normalizedPosition) {
553
	// if p1 is coincident with p2, there is no line
554
	if(p1 == p2) {
555
		if(normalizedPosition != nullptr) {
556
			*normalizedPosition = 0;
557
		}
558
		return p1;
559
	}
560
	
561
	float u = (p3.x - p1.x) * (p2.x - p1.x);
562
	u += (p3.y - p1.y) * (p2.y - p1.y);
563
	// perfect place for fast inverse sqrt...
564
	float len = glm::length(toGlm(p2 - p1));
565
	u /= (len * len);
566
	
567
	// clamp u
568
	if(u > 1) {
569
		u = 1;
570
	} else if(u < 0) {
571
		u = 0;
572
	}
573
	if(normalizedPosition != nullptr) {
574
		*normalizedPosition = u;
575
	}
576
	return glm::mix(toGlm(p1), toGlm(p2), u);
577
}
578

579
//----------------------------------------------------------
580
template<class T>
581
// a much faster but less accurate version would check distances to vertices first,
582
// which assumes vertices are evenly spaced
583
T ofPolyline_<T>::getClosestPoint(const T& target, unsigned int* nearestIndex) const {
584
	const ofPolyline_ & polyline = *this;
585
    
586
	if(polyline.size() < 2) {
587
		if(nearestIndex != nullptr) {
588
			nearestIndex = 0;
589
		}
590
		return target;
591
	}
592
	
593
	float distance = 0;
594
	T nearestPoint(0);
595
	unsigned int nearest = 0;
596
	float normalizedPosition = 0;
597
	unsigned int lastPosition = polyline.size() - 1;
598
	if(polyline.isClosed()) {
599
		lastPosition++;
600
	}
601
	for(int i = 0; i < (int) lastPosition; i++) {
602
		bool repeatNext = i == (int) (polyline.size() - 1);
603
		
604
		const auto& cur = polyline[i];
605
		const auto& next = repeatNext ? polyline[0] : polyline[i + 1];
606
		
607
		float curNormalizedPosition = 0;
608
		auto curNearestPoint = getClosestPointUtil(cur, next, target, &curNormalizedPosition);
609
		float curDistance = glm::distance(toGlm(curNearestPoint), toGlm(target));
610
		if(i == 0 || curDistance < distance) {
611
			distance = curDistance;
612
			nearest = i;
613
			nearestPoint = curNearestPoint;
614
			normalizedPosition = curNormalizedPosition;
615
		}
616
	}
617
	
618
	if(nearestIndex != nullptr) {
619
		if(normalizedPosition > .5) {
620
			nearest++;
621
			if(nearest == polyline.size()) {
622
				nearest = 0;
623
			}
624
		}
625
		*nearestIndex = nearest;
626
	}
627
	
628
	return nearestPoint;
629
}
630

631
//--------------------------------------------------
632
template<class T>
633
bool ofPolyline_<T>::inside(const T & p, const ofPolyline_ & polyline){
634
	return ofPolyline_<T>::inside(p.x,p.y,polyline);
635
}
636

637
//--------------------------------------------------
638
template<class T>
639
bool ofPolyline_<T>::inside(float x, float y, const ofPolyline_ & polyline){
640
	int counter = 0;
641
	int i;
642
	double xinters;
643
	T p1,p2;
644
    
645
	int N = polyline.size();
646
    
647
	p1 = polyline[0];
648
	for (i=1;i<=N;i++) {
649
		p2 = polyline[i % N];
650
		if (y > std::min(p1.y,p2.y)) {
651
            if (y <= std::max(p1.y,p2.y)) {
652
                if (x <= std::max(p1.x,p2.x)) {
653
                    if (p1.y != p2.y) {
654
                        xinters = (y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
655
                        if (p1.x == p2.x || x <= xinters)
656
                            counter++;
657
                    }
658
                }
659
            }
660
		}
661
		p1 = p2;
662
	}
663
    
664
	if (counter % 2 == 0) return false;
665
	else return true;
666
}
667

668
//--------------------------------------------------
669
template<class T>
670
bool ofPolyline_<T>::inside(float x, float y) const {
671
	return ofPolyline_<T>::inside(x, y, *this);
672
    
673
}
674

675
//--------------------------------------------------
676
template<class T>
677
bool ofPolyline_<T>::inside(const T & p) const {
678
	return ofPolyline_<T>::inside(p, *this);
679
}
680

681

682

683
//--------------------------------------------------
684
namespace of{
685
	namespace priv{
686

687
		//This is for polygon/contour simplification - we use it to reduce the number of points needed in
688
		//representing the letters as openGL shapes - will soon be moved to ofGraphics.cpp
689

690
		// From: http://softsurfer.com/Archive/algorithm_0205/algorithm_0205.htm
691
		// Copyright 2002, softSurfer (www.softsurfer.com)
692
		// This code may be freely used and modified for any purpose
693
		// providing that this copyright notice is included with it.
694
		// SoftSurfer makes no warranty for this code, and cannot be held
695
		// liable for any real or imagined damage resulting from its use.
696
		// Users of this code must verify correctness for their application.
697
		template<class T>
698
		struct Segment{
699
			T P0;
700
			T P1;
701
		};
702

703
		template<class T>
704
		static void simplifyDP(float tol, T* v, int j, int k, int* mk ){
705
			if (k <= j+1) // there is nothing to simplify
706
				return;
707

708
			// check for adequate approximation by segment S from v[j] to v[k]
709
			int     maxi	= j;          // index of vertex farthest from S
710
			float   maxd2	= 0;         // distance squared of farthest vertex
711
			float   tol2	= tol * tol;  // tolerance squared
712
			Segment<T> S	= {v[j], v[k]};  // segment from v[j] to v[k]
713
			auto u			= S.P1 - S.P0;   // segment direction vector
714
			double  cu		= glm::dot(toGlm(u), toGlm(u));     // segment length squared
715

716
			// test each vertex v[i] for max distance from S
717
			// compute using the Feb 2001 Algorithm's dist_ofPoint_to_Segment()
718
			// Note: this works in any dimension (2D, 3D, ...)
719
			T  w;
720
			T  Pb;                // base of perpendicular from v[i] to S
721
			float  b, cw, dv2;        // dv2 = distance v[i] to S squared
722

723
			for (int i=j+1; i<k; i++){
724
				// compute distance squared
725
				w = v[i] - S.P0;
726
				cw = glm::dot(toGlm(w), toGlm(u));
727
				if ( cw <= 0 ) dv2 = glm::length2(toGlm(v[i]) - toGlm(S.P0));
728
				else if ( cu <= cw ) dv2 = glm::length2(toGlm(v[i]) - toGlm(S.P1));
729
				else {
730
					b = (float)(cw / cu);
731
					Pb = S.P0 + u*b;
732
					dv2 = glm::length2(toGlm(v[i]) - toGlm(Pb));
733
				}
734
				// test with current max distance squared
735
				if (dv2 <= maxd2) continue;
736

737
				// v[i] is a new max vertex
738
				maxi = i;
739
				maxd2 = dv2;
740
			}
741
			if (maxd2 > tol2)        // error is worse than the tolerance
742
			{
743
				// split the polyline at the farthest vertex from S
744
				mk[maxi] = 1;      // mark v[maxi] for the simplified polyline
745
				// recursively simplify the two subpolylines at v[maxi]
746
				simplifyDP( tol, v, j, maxi, mk );  // polyline v[j] to v[maxi]
747
				simplifyDP( tol, v, maxi, k, mk );  // polyline v[maxi] to v[k]
748
			}
749
			// else the approximation is OK, so ignore intermediate vertices
750
		}
751
	}
752
}
753

754
//--------------------------------------------------
755
template<class T>
756
void ofPolyline_<T>::simplify(float tol){
757
    if(points.size() < 2) return;
758
    
759
	int n = size();
760
	
761
	if(n == 0) {
762
		return;
763
	}
764

765
	std::vector <T> sV;
766
	sV.resize(n);
767
    
768
    int    i, k, m, pv;            // misc counters
769
    float  tol2 = tol * tol;       // tolerance squared
770
    std::vector<T> vt;
771
    std::vector<int> mk;
772
    vt.resize(n);
773
	mk.resize(n,0);
774
    
775
    
776
    // STAGE 1.  Vertex Reduction within tolerance of prior vertex cluster
777
    vt[0] = points[0];              // start at the beginning
778
    for (i=k=1, pv=0; i<n; i++) {
779
		if (glm::length2((const glm::vec3&)points[i] - (const glm::vec3&)points[pv]) < tol2) continue;
780
        
781
        vt[k++] = points[i];
782
        pv = i;
783
    }
784
    if (pv < n-1) vt[k++] = points[n-1];      // finish at the end
785
    
786
    // STAGE 2.  Douglas-Peucker polyline simplification
787
    mk[0] = mk[k-1] = 1;       // mark the first and last vertices
788
	of::priv::simplifyDP( tol, &vt[0], 0, k-1, &mk[0] );
789
    
790
    // copy marked vertices to the output simplified polyline
791
    for (i=m=0; i<k; i++) {
792
        if (mk[i]) sV[m++] = vt[i];
793
    }
794
    
795
	//get rid of the unused points
796
	if( m < (int)sV.size() ){
797
		points.assign( sV.begin(),sV.begin()+m );
798
	}else{
799
		points = sV;
800
	}
801
    
802
}
803

804
//--------------------------------------------------
805
template<class T>
806
void ofPolyline_<T>::translate(const glm::vec3 & p){
807
    for(auto & point : points){
808
        point += p;
809
    }
810
    flagHasChanged();
811
}
812

813
//--------------------------------------------------
814
template<class T>
815
void ofPolyline_<T>::translate(const glm::vec2 &p){
816
    translate(glm::vec3(p, 0.0));
817
}
818

819
//--------------------------------------------------
820
template<class T>
821
void ofPolyline_<T>::rotateDeg(float degrees, const glm::vec3& axis){
822
    rotateRad(ofDegToRad(degrees), axis);
823
}
824

825
//--------------------------------------------------
826
template<class T>
827
void ofPolyline_<T>::rotateRad(float radians, const glm::vec3& axis){
828
    for(auto & point : points){
829
        point = glm::rotate(toGlm(point), radians, axis);
830
    }
831
    flagHasChanged();
832
}
833

834
//--------------------------------------------------
835
template<class T>
836
void ofPolyline_<T>::rotate(float degrees, const glm::vec3 &axis){
837
    rotateDeg(degrees, axis);
838
}
839

840
//--------------------------------------------------
841
template<class T>
842
void ofPolyline_<T>::rotateDeg(float degrees, const glm::vec2& axis){
843
    rotateRad(ofDegToRad(degrees), glm::vec3(axis, 0.0));
844
}
845

846
//--------------------------------------------------
847
template<class T>
848
void ofPolyline_<T>::rotateRad(float radians, const glm::vec2& axis){
849
    rotateRad(radians, glm::vec3(axis, 0.0));
850
}
851

852
//--------------------------------------------------
853
template<class T>
854
void ofPolyline_<T>::rotate(float degrees, const glm::vec2 &axis){
855
    rotateRad(ofDegToRad(degrees), glm::vec3(axis, 0.0));
856
}
857

858
//--------------------------------------------------
859
template<class T>
860
void ofPolyline_<T>::scale(float x, float y){
861
    for(auto & point : points){
862
        point.x *= x;
863
        point.y *= y;
864
    }
865
    flagHasChanged();
866
}
867

868
//--------------------------------------------------
869
template<class T>
870
void ofPolyline_<T>::draw() const{
871
	ofGetCurrentRenderer()->draw(*this);
872
}
873

874
//--------------------------------------------------
875
template<class T>
876
void ofPolyline_<T>::setRightVector(T v) {
877
    rightVector = v;
878
    flagHasChanged();
879
}
880

881
//--------------------------------------------------
882
template<class T>
883
T ofPolyline_<T>::getRightVector() const {
884
    return rightVector;
885
}
886

887
//--------------------------------------------------
888
template<class T>
889
float ofPolyline_<T>::getIndexAtLength(float length) const {
890
    if(points.size() < 2) return 0;
891
    updateCache();
892
    
893
    float totalLength = getPerimeter();
894
    length = ofClamp(length, 0, totalLength);
895
    
896
    int lastPointIndex = isClosed() ? points.size() : points.size()-1;
897
    
898
    int i1 = ofClamp(floor(length / totalLength * lastPointIndex), 0, lengths.size()-2);   // start approximation here
899
    int leftLimit = 0;
900
    int rightLimit = lastPointIndex;
901
    
902
    float distAt1, distAt2;
903
    for(int iterations = 0; iterations < 32; iterations ++) {	// limit iterations
904
        i1 = ofClamp(i1, 0, lengths.size()-1);
905
        distAt1 = lengths[i1];
906
        if(distAt1 <= length) {         // if Length at i1 is less than desired Length (this is good)
907
            distAt2 = lengths[i1+1];
908
            if(distAt2 >= length) {
909
                float t = ofMap(length, distAt1, distAt2, 0, 1);
910
                return i1 + t;
911
            } else {
912
                leftLimit = i1;
913
            }
914
        } else {
915
            rightLimit = i1;
916
        }
917
        i1 = (leftLimit + rightLimit)/2;
918
    }
919
    return 0;
920
}
921

922

923
//--------------------------------------------------
924
template<class T>
925
float ofPolyline_<T>::getIndexAtPercent(float f) const {
926
    return getIndexAtLength(f * getPerimeter());
927
}
928

929
//--------------------------------------------------
930
template<class T>
931
float ofPolyline_<T>::getLengthAtIndex(int index) const {
932
    if(points.size() < 2) return 0;
933
    updateCache();
934
    return lengths[getWrappedIndex(index)];
935
}
936

937
//--------------------------------------------------
938
template<class T>
939
float ofPolyline_<T>::getLengthAtIndexInterpolated(float findex) const {
940
    if(points.size() < 2) return 0;
941
    updateCache();
942
    int i1, i2;
943
    float t;
944
    getInterpolationParams(findex, i1, i2, t);
945
    return ofLerp(getLengthAtIndex(i1), getLengthAtIndex(i2), t);
946
}
947

948

949
//--------------------------------------------------
950
template<class T>
951
T ofPolyline_<T>::getPointAtLength(float f) const {
952
	if(points.size() < 2) return T();
953
    updateCache();
954
    return getPointAtIndexInterpolated(getIndexAtLength(f));
955
}
956

957
//--------------------------------------------------
958
template<class T>
959
T ofPolyline_<T>::getPointAtPercent(float f) const {
960
    float length = getPerimeter();
961
    return getPointAtLength(f * length);
962
}
963

964

965
//--------------------------------------------------
966
template<class T>
967
T ofPolyline_<T>::getPointAtIndexInterpolated(float findex) const {
968
	if(points.size() < 2) return T();
969
    int i1, i2;
970
    float t;
971
    getInterpolationParams(findex, i1, i2, t);
972
	T leftPoint(points[i1]);
973
	T rightPoint(points[i2]);
974
	return glm::mix(toGlm(leftPoint), toGlm(rightPoint), t);
975
}
976

977

978
//--------------------------------------------------
979
template<class T>
980
float ofPolyline_<T>::getAngleAtIndex(int index) const {
981
	return getDegreesAtIndex(index);
982
}
983

984
//--------------------------------------------------
985
template<class T>
986
float ofPolyline_<T>::getAngleAtIndexInterpolated(float findex) const {
987
	return getDegreesAtIndexInterpolated(findex);
988
}
989

990

991
//--------------------------------------------------
992
template<class T>
993
float ofPolyline_<T>::getDegreesAtIndex(int index) const {
994
	if(points.size() < 2) return 0;
995
	updateCache();
996
	return ofRadToDeg(angles[getWrappedIndex(index)]);
997
}
998

999
//--------------------------------------------------
1000
template<class T>
1001
float ofPolyline_<T>::getDegreesAtIndexInterpolated(float findex) const {
1002
	if(points.size() < 2) return 0;
1003
	int i1, i2;
1004
	float t;
1005
	getInterpolationParams(findex, i1, i2, t);
1006
	return ofRadToDeg(ofLerp(getDegreesAtIndex(i1), getDegreesAtIndex(i2), t));
1007
}
1008

1009

1010
//--------------------------------------------------
1011
template<class T>
1012
float ofPolyline_<T>::getRadiansAtIndex(int index) const {
1013
	if(points.size() < 2) return 0;
1014
	updateCache();
1015
	return angles[getWrappedIndex(index)];
1016
}
1017

1018
//--------------------------------------------------
1019
template<class T>
1020
float ofPolyline_<T>::getRadiansAtIndexInterpolated(float findex) const {
1021
	if(points.size() < 2) return 0;
1022
	int i1, i2;
1023
	float t;
1024
	getInterpolationParams(findex, i1, i2, t);
1025
	return ofLerp(getRadiansAtIndex(i1), getRadiansAtIndex(i2), t);
1026
}
1027

1028
//--------------------------------------------------
1029
template<class T>
1030
T ofPolyline_<T>::getRotationAtIndex(int index) const {
1031
	if(points.size() < 2) return T();
1032
    updateCache();
1033
    return rotations[getWrappedIndex(index)];
1034
}
1035

1036
//--------------------------------------------------
1037
template<class T>
1038
T ofPolyline_<T>::getRotationAtIndexInterpolated(float findex) const {
1039
	if(points.size() < 2) return T();
1040
    int i1, i2;
1041
    float t;
1042
    getInterpolationParams(findex, i1, i2, t);
1043
	return glm::mix(toGlm(getRotationAtIndex(i1)), toGlm(getRotationAtIndex(i2)), t);
1044
}
1045

1046
//--------------------------------------------------
1047
template<class T>
1048
T ofPolyline_<T>::getTangentAtIndex(int index) const {
1049
	if(points.size() < 2) return T();
1050
    updateCache();
1051
    return tangents[getWrappedIndex(index)];
1052
}
1053

1054
//--------------------------------------------------
1055
template<class T>
1056
T ofPolyline_<T>::getTangentAtIndexInterpolated(float findex) const {
1057
	if(points.size() < 2) return T();
1058
    int i1, i2;
1059
    float t;
1060
    getInterpolationParams(findex, i1, i2, t);
1061
	return glm::mix(toGlm(getTangentAtIndex(i1)), toGlm(getTangentAtIndex(i2)), t);
1062
}
1063

1064
//--------------------------------------------------
1065
template<class T>
1066
T ofPolyline_<T>::getNormalAtIndex(int index) const {
1067
	if(points.size() < 2) return T();
1068
    updateCache();
1069
    return normals[getWrappedIndex(index)];
1070
}
1071

1072
//--------------------------------------------------
1073
template<class T>
1074
T ofPolyline_<T>::getNormalAtIndexInterpolated(float findex) const {
1075
	if(points.size() < 2) return T();
1076
    int i1, i2;
1077
    float t;
1078
    getInterpolationParams(findex, i1, i2, t);
1079
	return glm::mix(toGlm(getNormalAtIndex(i1)), toGlm(getNormalAtIndex(i2)), t);
1080
}
1081

1082

1083
//--------------------------------------------------
1084
template<class T>
1085
void ofPolyline_<T>::calcData(int index, T &tangent, float &angle, T &rotation, T &normal) const {
1086
	int i1 = getWrappedIndex( index - 1 );
1087
	int i2 = getWrappedIndex( index     );
1088
	int i3 = getWrappedIndex( index + 1 );
1089

1090
	const auto &p1 = toGlm(points[i1]);
1091
	const auto &p2 = toGlm(points[i2]);
1092
	const auto &p3 = toGlm(points[i3]);
1093

1094
	auto v1(p1 - p2); // vector to previous point
1095
	auto v2(p3 - p2); // vector to next point
1096
	
1097
	v1 = glm::normalize(v1);
1098
	v2 = glm::normalize(v2);
1099

1100
	// If just one of p1, p2, or p3 was identical, further calculations 
1101
	// are (almost literally) pointless, as v1 or v2 will then contain 
1102
	// NaN values instead of floats.
1103

1104
	bool noSegmentHasZeroLength = (v1 == v1 && v2 == v2);
1105

1106
	if ( noSegmentHasZeroLength ){
1107
		tangent  = toOf( glm::length2(v2 - v1) > 0 ? glm::normalize(v2 - v1) : -v1 );
1108
		normal   = toOf( glm::normalize( glm::cross( toGlm( rightVector ), toGlm( tangent ) ) ) );
1109
		rotation = toOf( glm::cross( v1, v2 ) );
1110
		angle    = glm::pi<float>() - acosf( ofClamp( glm::dot( v1, v2 ), -1.f, 1.f ) );
1111
	} else{
1112
		rotation = tangent = normal = T( 0.f );
1113
		angle    = 0.f;
1114
	}
1115
}
1116

1117

1118
//--------------------------------------------------
1119
template<class T>
1120
int ofPolyline_<T>::getWrappedIndex(int index) const {
1121
    if(points.empty()) return 0;
1122
    
1123
    if(index < 0) return isClosed() ? (index + points.size()) % points.size() : 0;
1124
    if(index > int(points.size())-1) return isClosed() ? index % points.size() : points.size() - 1;
1125
    return index;
1126
}
1127

1128
//--------------------------------------------------
1129
template<class T>
1130
void ofPolyline_<T>::getInterpolationParams(float findex, int &i1, int &i2, float &t) const {
1131
    i1 = floor(findex);
1132
    t = findex - i1;
1133
    i1 = getWrappedIndex(i1);
1134
    i2 = getWrappedIndex(i1 + 1);
1135
}
1136

1137
//--------------------------------------------------
1138
template<class T>
1139
void ofPolyline_<T>::updateCache(bool bForceUpdate) const {
1140
    if(bCacheIsDirty || bForceUpdate) {
1141
        lengths.clear();
1142
        angles.clear();
1143
        rotations.clear();
1144
        normals.clear();
1145
        tangents.clear();
1146
        area = 0;
1147
		centroid2D = {0.f, 0.f, 0.f};
1148
        bCacheIsDirty = false;
1149
        
1150
        if(points.size() < 2) return;
1151

1152
        // area
1153
        for(int i=0;i<(int)points.size()-1;i++){
1154
            area += points[i].x * points[i+1].y - points[i+1].x * points[i].y;
1155
        }
1156
        area += points[points.size()-1].x * points[0].y - points[0].x * points[points.size()-1].y;
1157
        area *= 0.5;
1158
        
1159
        if(fabsf(area) < std::numeric_limits<float>::epsilon()) {
1160
            centroid2D = getBoundingBox().getCenter();
1161
        } else {
1162
            // centroid
1163
            // TODO: doesn't seem to work on all concave shapes
1164
            for(int i=0;i<(int)points.size()-1;i++){
1165
                centroid2D.x += (points[i].x + points[i+1].x) * (points[i].x*points[i+1].y - points[i+1].x*points[i].y);
1166
                centroid2D.y += (points[i].y + points[i+1].y) * (points[i].x*points[i+1].y - points[i+1].x*points[i].y);
1167
            }
1168
            centroid2D.x += (points[points.size()-1].x + points[0].x) * (points[points.size()-1].x*points[0].y - points[0].x*points[points.size()-1].y);
1169
            centroid2D.y += (points[points.size()-1].y + points[0].y) * (points[points.size()-1].x*points[0].y - points[0].x*points[points.size()-1].y);
1170
            
1171
            centroid2D.x /= (6*area);
1172
            centroid2D.y /= (6*area);
1173
        }
1174

1175
        
1176
        // per vertex cache
1177
        lengths.resize(points.size());
1178
        tangents.resize(points.size());
1179
        angles.resize(points.size());
1180
        normals.resize(points.size());
1181
        rotations.resize(points.size());
1182
        
1183
        float angle;
1184
		T rotation;
1185
		T normal;
1186
		T tangent;
1187

1188
        float length = 0;
1189
        for(int i=0; i<(int)points.size(); i++) {
1190
            lengths[i] = length;
1191

1192
            calcData(i, tangent, angle, rotation, normal);
1193
            tangents[i] = tangent;
1194
            angles[i] = angle;
1195
            rotations[i] = rotation;
1196
            normals[i] = normal;
1197
            
1198
			length += glm::distance(toGlm(points[i]), toGlm(points[getWrappedIndex(i + 1)]));
1199
        }
1200
        
1201
        if(isClosed()) lengths.push_back(length);
1202
    }
1203
}
1204

1205

1206
//--------------------------------------------------
1207
template<class T>
1208
typename std::vector<T>::iterator ofPolyline_<T>::begin(){
1209
	return points.begin();
1210
}
1211

1212
//--------------------------------------------------
1213
template<class T>
1214
typename std::vector<T>::iterator ofPolyline_<T>::end(){
1215
	return points.end();
1216
}
1217

1218
//--------------------------------------------------
1219
template<class T>
1220
typename std::vector<T>::const_iterator ofPolyline_<T>::begin() const{
1221
	return points.begin();
1222
}
1223

1224
//--------------------------------------------------
1225
template<class T>
1226
typename std::vector<T>::const_iterator ofPolyline_<T>::end() const{
1227
	return points.end();
1228
}
1229

1230
//--------------------------------------------------
1231
template<class T>
1232
typename std::vector<T>::reverse_iterator ofPolyline_<T>::rbegin(){
1233
	return points.rbegin();
1234
}
1235

1236
//--------------------------------------------------
1237
template<class T>
1238
typename std::vector<T>::reverse_iterator ofPolyline_<T>::rend(){
1239
	return points.rend();
1240
}
1241

1242
//--------------------------------------------------
1243
template<class T>
1244
typename std::vector<T>::const_reverse_iterator ofPolyline_<T>::rbegin() const{
1245
	return points.rbegin();
1246
}
1247

1248
//--------------------------------------------------
1249
template<class T>
1250
typename std::vector<T>::const_reverse_iterator ofPolyline_<T>::rend() const{
1251
	return points.rend();
1252
}
1253

1254