I was talking about this post with a co-worker today who has been working on polygon tracing for farms as well and he pointed out that the solution in this post, while good at minimizing the fence/perimeter, it will likely have issues when a user tries to draw something that really does look like the before images in this post like if they have a lake or something else that cuts a jagged edge in to the perimeter then this software will mess it up. While the example at the top is a bit annoying, it’s not too hard to learn the right way to do things and not have the problem from now on. But with this solution, the software is modifying your data to fit it’s own model of what looks right and you can’t change your behaviour because the software is always trying to optimise for the smallest fence line which isn’t always a reality.
From our current experience, we might be able to handle this case too.
Take the cases of the errors we have recorded in the blog, there are cases where it does fail because it isn’t the smallest path. It is fairly easy and intuitive for a user to add more points such that the path goes through what is required.
At the same time, it is not going to work always, so yes there are those few cases where it will still not work, and we are fine to make the user do more work there (delete everything, start again) while at the same time optimizing for the majority cases.
Thanks for the response. How well does it behave while editing? I can imagine such a system might radically change the polygon while editing and it finds shorter paths with a new node added. Also is the performance decent for real time editing with things like dragging a node around the map?
Sometimes it does goes bad, but most of the time it is more intuitive than any other User interface we tried. Check these 2 links which show that it will work after a few manageable tries:
But again in terms of possibilities, there is always going to be a case which is not going to work at all (sadly). And it does change radically and unexpectedly at times. One clever trick here is to stick the initialization to the user marked points, because most likely they did mark them in close to correct order.
Regarding performance, we are using 2-opt algorithm, so our number of steps are limited by N^2 * number of iterations
We can set these number of iterations based on expectations of N. For example, we work with 10 iterations and it seems to converge well most of the times. Assuming 20 points, and each iteration being ~1ms, it would take 4 seconds. In reality, I have never seen it become unresponsive even for 50 points(which means the iteration duration is far lower than 1ms).
This was really cool! Sounds like the team has a lot of empathy for users, and is able to leverage their technical knowledge in a way that actually helps those users, without getting lost in the weeds of over complicating the solution. It’s also funny that this would even be something out of the ordinary, or worth mentioning, but I’ve seen so many smart teams completely miss the mark when it comes to solving challenges like this. Often the “serious” programmers would consider this the UI/UX folks’ problem, and that a mathematical solution would be too much, or the mathematical solution wouldn’t take into account the end user’s experience and frustration.
I thought the article was really easy to read also (coming from someone who is interested in technical/algorithmic solutions to problems but lacks the background to really grok most articles I see like this). So kudos to the author, and thank you!
Thanks for sharing this, I love looking at geo problems. They all seem so simple on the surface but when you dig in to them they get very complex very fast. I am building an app that uses a lot of GPS data and some seemingly simple parts have taken weeks because of the unexpected complexities. The fairly complex geometry of the earth makes calculations fairly complex. Often I have written functions that produce a wrong value but it’s close enough to work for what I need and it’s much faster and simpler than a correct function.
Really fun article! One question: what was the reasoning behind implementing a solver yourself instead of using an off the shelf solution? Was it because of the “it must run on an old smartphone” requirement?
Honestly, I wanted to use a library but couldn’t find any Javascript solver which uses any of the old boring(read fast) algorithms such as 2-opt or 3-opt or the LKH solutions I wanted.
You will find a few JS implementations which are based on Genetic algorithms, but though they are cooler, I don’t like the idea of using non-deterministic algorithms.
Again, 2-opt is so easy that it is documented on Wikipedia :) So I had no inhibitions to implement it myself. The best available heuristic (LKH) is a lot more complicated, which is why I haven’t implemented it (yet).
I was talking about this post with a co-worker today who has been working on polygon tracing for farms as well and he pointed out that the solution in this post, while good at minimizing the fence/perimeter, it will likely have issues when a user tries to draw something that really does look like the before images in this post like if they have a lake or something else that cuts a jagged edge in to the perimeter then this software will mess it up. While the example at the top is a bit annoying, it’s not too hard to learn the right way to do things and not have the problem from now on. But with this solution, the software is modifying your data to fit it’s own model of what looks right and you can’t change your behaviour because the software is always trying to optimise for the smallest fence line which isn’t always a reality.
From our current experience, we might be able to handle this case too.
Take the cases of the errors we have recorded in the blog, there are cases where it does fail because it isn’t the smallest path. It is fairly easy and intuitive for a user to add more points such that the path goes through what is required.
At the same time, it is not going to work always, so yes there are those few cases where it will still not work, and we are fine to make the user do more work there (delete everything, start again) while at the same time optimizing for the majority cases.
Thanks for the response. How well does it behave while editing? I can imagine such a system might radically change the polygon while editing and it finds shorter paths with a new node added. Also is the performance decent for real time editing with things like dragging a node around the map?
Sometimes it does goes bad, but most of the time it is more intuitive than any other User interface we tried. Check these 2 links which show that it will work after a few manageable tries:
But again in terms of possibilities, there is always going to be a case which is not going to work at all (sadly). And it does change radically and unexpectedly at times. One clever trick here is to stick the initialization to the user marked points, because most likely they did mark them in close to correct order.
Regarding performance, we are using 2-opt algorithm, so our number of steps are limited by
N^2 * number of iterationsWe can set these number of iterations based on expectations of N. For example, we work with 10 iterations and it seems to converge well most of the times. Assuming 20 points, and each iteration being ~1ms, it would take 4 seconds. In reality, I have never seen it become unresponsive even for 50 points(which means the iteration duration is far lower than 1ms).
I think they have a manual override, although presented as tongue in cheek:
This was really cool! Sounds like the team has a lot of empathy for users, and is able to leverage their technical knowledge in a way that actually helps those users, without getting lost in the weeds of over complicating the solution. It’s also funny that this would even be something out of the ordinary, or worth mentioning, but I’ve seen so many smart teams completely miss the mark when it comes to solving challenges like this. Often the “serious” programmers would consider this the UI/UX folks’ problem, and that a mathematical solution would be too much, or the mathematical solution wouldn’t take into account the end user’s experience and frustration.
I thought the article was really easy to read also (coming from someone who is interested in technical/algorithmic solutions to problems but lacks the background to really grok most articles I see like this). So kudos to the author, and thank you!
Thanks for sharing this, I love looking at geo problems. They all seem so simple on the surface but when you dig in to them they get very complex very fast. I am building an app that uses a lot of GPS data and some seemingly simple parts have taken weeks because of the unexpected complexities. The fairly complex geometry of the earth makes calculations fairly complex. Often I have written functions that produce a wrong value but it’s close enough to work for what I need and it’s much faster and simpler than a correct function.
Really fun article! One question: what was the reasoning behind implementing a solver yourself instead of using an off the shelf solution? Was it because of the “it must run on an old smartphone” requirement?
Honestly, I wanted to use a library but couldn’t find any Javascript solver which uses any of the old boring(read fast) algorithms such as 2-opt or 3-opt or the LKH solutions I wanted.
You will find a few JS implementations which are based on Genetic algorithms, but though they are cooler, I don’t like the idea of using non-deterministic algorithms.
Again, 2-opt is so easy that it is documented on Wikipedia :) So I had no inhibitions to implement it myself. The best available heuristic (LKH) is a lot more complicated, which is why I haven’t implemented it (yet).
Makes perfect sense. Thank you for explaining!