Path Algorithm

Post date: Dec 14, 2013 10:43:21 PM

The "Path Algorithm" takes as inputs a distance and 3 or more coordinates that create a valid polygon. The output of the algorithm is a set of waypoints that define the path the lawnmower can take in order to travel within the valid polygon's entire area. The coordinates are the corners of the cutting-field, whereas the valid polygon is the cutting-field itself. The lawnmower path that results from the Path Algorithm is supposed to resemble the conventional "zig-zag" or "stripped" pattern performed by those who mow lawns. The "distance" mentioned earlier is the amount space between each straight line the lawnmower would take to reach the opposite ends of the cutting-field.

The java applet from the link below demonstrates the Path Algorithm. Please note, in addition to the applet itself, a temporary shared library that contains the compiled Path Algorithm is also loaded onto the computer. Since only 32- and 64-bit libraries were compiled for Windows (i.e. dll), the applet will not operate on other operating systems.

Launch AlpAlgorithmJava as an Applet (Windows only)

Launch AlpAlgorithm with Java Web Start (Windows only)

Click anywhere within the frame to create a corner. Click and drag a corner in order to move the selected corner. Double clicking a corner will eliminate the corner. 3 or more corners that create a valid polygon will cause the Path Algorithm to execute and thus the lawnmower path (in green) will appear.

The implementation of the Path Algorithm is done in C++ so as to be consistent with the rest of the ALP project's software. Below is a figure that graphically describes conceptually what the software does.

The corners (i.e. the black dots) of the cutting-field are used to define a polygon shape that represents the cutting-field (picture 1). The longest side of the polygon is replicated across the polygon and the intersections (i.e. the yellow dots) between the replicates (i.e. the red lines) and the polygon's perimeter (i.e. the white line) are recorded (picture 2). Next, one of the corners of the perimeter is selected from the polygon's longest side and then becomes the current "guide point". For every new guide point, the point is first added to the end of the lawnmower path (i.e. a set of points) and then a new guide point is selected. The next guide point is the closest intersection point that has yet to be a guide point. However, the closest intersection point on the same red line as the current guide point takes precedence over the other intersection points (picture 3). Once all the intersection points are added to the lawnmower path, the algorithm is complete (picture 4).