How to build a route inside a polygon OpenLayer

Question

I use OpeenStreetMap and the OpenLayers library, I need to build a route inside the polygon as in the mission planner program, here https://www.youtube.com/watch?v=MhHomssqD7k&ab_channel=AeroHawk at 2 minutes you can see how inside the polygon marked with red segments , the program automatically builds a route. How can I replicate this? What is this algorithm?

mission planer

Answer 1

I see you're talking about generating a drone flight path within a polygon, calculating the positions of way points.

Quite a fun challenge! I'll write out in words how the algorithm would work, but doing this in javascript would also be fun!

It should be possible to do this for a given (adjustable) angle of orientation, but I suggest you could simplify things initially by assuming the drone is to fly in passes orientated exactly East <-> West.

That also means the start way point is simply the northernmost corner of the polygon i.e. the vertex with the greatest latitude (Given a polygon with a northern edge like the one pictured, it doesn't matter which of the two top corners is the start point). Likewise the final way point is straightforward. The southernmost corner of the polygon.

We need to caculate all the waypoints in between. A series of locations on the left and right to create this laddered effect. Perhaps you'll want to start by building two lines (or ordered arrays of corner points) representing the left and right sides. The algrithm needs to "walk" down these sides, so maintain a lastLeft and lastRight point which are both intialised to the start of their lines. For both lines this is the start point at the top.

Each "walk step" down a line is going involve some calculation (sub-function!). They'll be a configured "gap" between the drone passes. This delta-latitude will be used at this point. For each walk step we're starting from the last point (lastLeft or lastRight) and so we've got a target latitude. targetLat = lastLeft.lat - gap. In a loop we can walk to the next point of the line (corner of the original polygon) if that lies within the gap, i.e. the latitude of that point is > targetLat. Another edge case is if the next point is actually the end point (break! we're done!). But otherwise we've got an edge that crosses the targetLat. We do the geometric calculation to find the point along the edge where it crosses the targetLat*. That point is our next way point!

*Geometric calculation to find the point along a line which has the targetLat? Possibly this part is do-able with something like TurfJS, although I couldn't tell you exactly which library call. But having worked out the rest of the algorithm, personally I'd probably just the code linear maths directly. You have known start and end to the line, therefore a known gradient. Take that and apply it to the known delta-lat to find the delta-lon.

We need to follow that algorithm for a "walk step", walking down the left line and then down the right line, and then down the right line and then down the left line, generating the ladder shaped series of way points all the way down to the end!