I'm making an app which controls a drone (DJI) and takes photos. In one particular feature, the user can draw a polygon (let's keep it a convex quadrilateral for now) and the app should generate a serpentine path for the drone to fly over the entire region.

Example from DJI GS Pro app

Input: 4 vertices of the polygon

Output: Array of coordinates of the path.

Any heads up on which algorithm to use? I've looked in to Boustrophedon Cell Decomposition, but there's not much documentation on it.

  • 1
    $\begingroup$ Hi @Ramsundar Shandilya, did you ever manage to complete this? I don't see an accepted answer. Which language did you use to generate your coverage path to the serpantine line. I am looking for examples on how to do exactly this in preferably python, C# or SQL... My search on the internet is not really producing any tangible example on how to achieve this $\endgroup$ Jan 30 '20 at 13:23

This thing is generally called coverage path planning.

If you are particularly interested in Boustrophedon Cell Decomposition, you may have a look at the paper introducing it: Choset and Pignon (1998).

You may also want to check out this survey paper.

  • $\begingroup$ Thanks @PetchPuttichai. The survey paper was really useful. Do you have recommendations as to which approach to use, given the input I have is in Cartesian coordinates? Thanks $\endgroup$ Oct 31 '17 at 20:20
  • $\begingroup$ I'm not very familiar with coverage path planning (I mainly work on motion planning) so I can't give you any recommendation. However, if the problem is as you stated where the area is convex, using a basic exact algorithm like Boustrophedon Cell Decomposition will do just fine. Using fancier algorithms will likely not make big differences and probably cause you more time to implement. $\endgroup$ Nov 1 '17 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.