Which means we are looking at a Euclidean Travelling Salesman Problem.
The 2-opt algorithm is highly dependent on the initialization that we pick for our data.
I started with using Nearest neighbour based initial path (ie Choose the nearest point as the next point in path), since theoretically, it gives the best result.
A very simple example where there are just 4 points, but it takes 2 attempts for a user to get it right.
Expectation of how the software should work " data-medium-file="https://i1com/crondev.blog/wp-content/uploads/2018/08/Wrong.gif?
Alas, it doesn’t work in the cases below (which I must mention are very much real farms and not a figment of my imagination 🙂 ) Trying to re-analyze our problem, we are trying to find a best bounding polygon for a set of points, i.e. Any intersecting edges would produce an invalid polygon (with respect to physical land entities) since it would lead us to having a negative area.
(Theoretically, there can be negative areas, eg: a farm around a house, but realistically, we don’t handle any such cases) Using Triangle inequality, the shortest path when walking along all of these points is guaranteed to have no intersecting lines.The weights between the points (sites) involved are taken to be the Euclidean distance between the points.If in an optimal tour some pair of edges AC and BD cross as shown below (Figure 4, top), then this can not be an optimal tour. Consider the tour where the edges A’B’ and D’C’ replace the edges AC and BD in our tour.In this post, we will be exploring an extremely interesting implementation of the Travelling Salesman Problem. We at Lean Agri, work towards digitising farmlands by tagging coordinates of a farm.This is helpful for various purposes: Getting an exact area of the farm, Remote monitoring farm area using satellites, Obtaining weather predictions for the specific region etc.It isn’t needed to walk along, but we can simply mark these corners.From our data, we have realized that the users are unable to mark these points in order and they need to do it over and over again.We know that AQ QB is larger than A’B’ (because in the triangle AQB, the sum of any two sides has Euclidean length greater than the third side). Intuitively for a user, the travelling salesman problem solution is going to make the most sense. TSP is solvable in time which for 15 points is going to be ~10^15 iterations!Please note that humans are extremely good at solving the Travelling Salesman Problem. Fortunately, a lot of research is done on this problem to generate approximate heuristic solutions much faster than the brute force solution.fit=173,300&ssl=1" data-large-file="https://i1com/crondev.blog/wp-content/uploads/2018/08/Wrong.gif? fit=320,556&ssl=1" class="size-medium wp-image-2199" src="https://i1com/crondev.blog/wp-content/uploads/2018/08/Wrong.gif? resize=173,300&ssl=1" alt="" width="173" height="300" data-recalc-dims="1" /How to make it work " data-medium-file="https://i2com/crondev.blog/wp-content/uploads/2018/08/Right.gif?fit=173,300&ssl=1" data-large-file="https://i2com/crondev.blog/wp-content/uploads/2018/08/Right.gif? fit=320,554&ssl=1" class="size-medium wp-image-2198" src="https://i2com/crondev.blog/wp-content/uploads/2018/08/Right.gif? resize=173,300&ssl=1" alt="" width="173" height="300" data-recalc-dims="1" / So, isn’t the solution to train users to mark them in order always?