Polygonal Auto-Waypoints "Math"

Good Evening All,

I was looking to read into the math behind automatic waypoint generation for a simple lawn mower pattern (as outputted by Mission Planner). Would someone be able to point me towards the code that handles the waypoint generation end of things.

If it helps, here is some code I put together to generate a lawn mower pattern from any arbitrary polygon:

https://github.com/RiceCreekUAS/rc-flight/tree/master/src/survey

The underlying concept is that the ground station sends just the polygon up to the aircraft (just a few coordinates) and the aircraft then computes the specific route and waypoints itself and then trickles that back down to the ground station for display. Creating a new route and sending it up is thus extremely quick … often I wouldn’t even start drawing the polygon area until after I launched the aircraft. Looks like I did this 3-4 years ago, but I might remember a few things if you have any specific questions.

This is part of my own hobby/diy autopilot ecosystem, and is optimized for fixed wing flying (the transact angle is perpendicular to the estimated wind so all the turns are upwind to minimize turn radius. Unfortunately it’s not setup to run with px4 or ardupilot, but anyone can feel free to borrow stuff if there is anything there that seems interesting or useful.

Edit: I did some of the geometry in wgs84 (lon/lat) space so that complicates some of the dependencies as I pull in modules to help do the fancy oblate ellipsoid math.

Edit 2: apparently I even wrote a short slightly cringeworthy blog article back in the day with a couple pictures: http://gallinazo.flightgear.org/uas/generating-survey-area-coverage-routes/

2 Likes

I also wrote a routine (perhaps not a sophisticated as Curtis’s) that runs from the command line to develop an outside-in spiral mowing pattern before Michael Oborne built it into Mission Planner (and MP works a little better than mine, I think). What allowed me to accomplish the task was finding a library named Clipper that did the heavy math for me. Mission Planner uses that library also.

My code is at https://github.com/ktrussell/MowPlan
I demonstrated my program at https://www.youtube.com/watch?v=WplfVcRodPo and https://www.youtube.com/watch?v=PjTcID7TA-c. I do think Mission Planner is superior, in general, but the code may be of interest if you are just trying to understand how it is done.

The Mission Planner code is located here: MissionPlanner/Grid.cs at master · ArduPilot/MissionPlanner (github.com). I believe the CreateRotary() function creates the spiral pattern.

2 Likes

The geometry problem is usually described as “polygon buffering,” although the Clipper library uses the term “offset” to mean the same thing. It’s a non-trivial problem, especially in geodetic coordinate space. Mission Planner uses a rather clever approach with the Clipper library, since Clipper only accepts integer arguments. The coordinates are first converted to UTM and then multiplied by a factor of 1000 to improve accuracy. So long as the spiral pattern doesn’t stray too far from a single UTM grid zone, the accuracy is quite good. Creating a transoceanic pattern would likely get a bit messy with that method…

I must admit, I’m curious what problem you’re trying to solve.

I recently had some success adding some small features to Mission Planner that were somewhat specific to lawnmowing path planning. You can gain access to those features by going to the help page and downloading the latest beta update.

2 Likes