1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

// Copyright (C) 2010 Duncan Hall
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
package net.duncanhall.geom
{
	
	import flash.geom.Point
	
	
	public class DirectedPath
	{
		
		

		/**
		 * Removes dead ends and vertices that double back on themselves from a path of consecutive points.
		 * If the path is found to find faults, the path is recursively corrected until no more faults  
		 * are found, or the <code>maxLevels</code> parameter is reached.
		 *
		 * @param points		The path of points to correct
		 * @param threshold		The minimum allowable angle between any 3 consecutive points
		 * @param recursive		Whether the result of the correction will be passed back into the method  
		 * @param minDistance	If <code>recursive</code> is set to true, this specifies the minimum distance
		 *                      allowed between 2 points when their joining point has been removed.
		 * @param maxLevels		The maximum number of times that path should be checked.
		 * @return				The points along the new corrected path.
		 *
		 */
		public static function correctPathRecursive (points:Array, threshold:Number, minDistance:Number = 10, maxLevels:int = 4) : Array
		{
			var c:Array = correctPath(points, threshold, true, minDistance);
			var np:int = c.shift();
			if (np)
			{
				var i:int;
				while (i < maxLevels)
				{
					c = correctPath(c, threshold, true, minDistance);
					np = c.shift();
					if (np == 0) break;
					i++;
				}
			}
			return c;
		}
		
		
		
		
		/**
		 * Removes dead ends and vertices that double back on themselves from a path of consecutive points.
		 *
		 * @param points		The path of points to correct
		 * @param threshold		The minimum allowable angle between any 3 consecutive points
		 * @param recursive		Whether the result of the correction will be passed back into the method  
		 * @param minDistance	If <code>recursive</code> is set to true, this specifies the minimum distance
		 *                      allowed between 2 points when their joining point has been removed.
		 * @return				The points along the new corrected path. If the <code>recursive</code> property 
		 *						is set to true, the first item in the array is an integer value representing
		 *						the number of faults that were corrected.
		 *
		 */
		public static function correctPath (points:Array, threshold:Number, recursive:Boolean = false, minDistance:Number = 10) : Array
		{
			var numPoints:int = points.length;
			var corrected:Array = [];
			corrected.push(points[0]);
		 
			var p0:Point;
			var p1:Point;
			var p2:Point;
			var da:Number;
			var db:Number
			var dc:Number;
			var c:Number;
			var np:int;
			var n:int = numPoints - 1;
			
			for (var i:int = 1; i < n; i++)
			{
				p0 = points[i - 1];
				p1 = points[i];
				p2 = points[i + 1];
				da = Point.distance(p0, p1);
				db = Point.distance(p1, p2);
				dc = Point.distance(p0, p2);
				c = Math.acos((da * da + db * db - dc * dc) / (2 * da * db));
		 
				if ((c * 180 / Math.PI) >= threshold) 
				{
					corrected.push(p1);
				}
				else if (recursive)
				{
					np++;
					if (dc <= minDistance)
					{
						i++;
						continue;
					}
				}
			}
		 
			corrected.push(points[numPoints - 1]);
			if (recursive) corrected.unshift(np);
			return corrected;
		}
		
	}
}