2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 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$
    – Joachim Prinsloo
    Commented Jan 30, 2020 at 13:23

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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$
    – Ramsundar Shandilya
    Commented Oct 31, 2017 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$
    – Petch Puttichai
    Commented Nov 1, 2017 at 3:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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