This is an archive post and is likely to contain missing media, broken links or opinions on long-since abandoned technologies.

Actionscript Path Correction Part 2

After my initial success in removing dead ends and backtracking from a directed path, I realised I was only half way to solving the problem. In the original post, points A, B and C were all single point digressions away from the main path.

With the addition of the new points at D, the previous solution would only have removed the segments marked in green, still leaving a large part of D that we don’t want.

To remedy this, I have made 2 additions to the original solution. First, I created a method that allows me to recursively check the corrected path, with the corrected points being fed back into the correction algorithm a specified number of times. Initially I thought this would be all I needed, but I was still getting problem points left along the path. The key was to check the distance between the 2 points left remaining after an adjoining point had been removed. If it is below a certain distance, the next point along the path is also culled from the new route. The example below shows correction of a path with some complex faults:

Recursive path correction example swf
I’m quite pleased with this solution, so far its proved to eliminate every one of the features I’ve sought to remove. I can’t go into my own uses for it yet, but it’s applications could vary from optimising a route through a maze to auto correcting a shape drawn from user input.

I have created the DirectedPath class to encapsulate the 2 methods I created.

Removes dead ends and vertices that double back on themselves from a path of consecutive points. The threshold value specifies the minimum allowable angle between any 3 consecutive points.

var correctedPath:Array = DirectedPath.correctPath(arrayOfPoint, 12);

If the path is found to find faults, the path is recursively corrected until no more faults are found, or the maxLevels parameter is reached.

var correctedPath:Array = DirectedPath.correctPathRecursive(arrayOfPoint, 12, 10, 4);

View source for
View DirectedPath Documentatation