4 ms·

What's wrong with "the lawnmower approach"? Imagine you're mowing the lawn in a spiral from the outside in. When a section is completely mowed, just continue sp

What's wrong with "the lawnmower approach"? Imagine you're mowing the lawn in a spiral from the outside in. When a section is completely mowed, just continue spiraling in the remaining area. The center is the last place with high grass. The only drawback I see is that you could get multiple answers for certain shapes. But for the ones in the post, I think the answer is about the same.

deleted 9y ago
[deleted]
ricardobeat 9y ago
Im not sure about the exact cost, but at first sight this approach would still require a lot more operations per line - you need to keep the lawnmower inside by measuring distance/intersection to closest edge, plus track the already mowed area. Maybe making the lawnmower wide enough could make it fast and accurate enough for specific use cases.
theoh 9y ago
That's equivalent to calculating the "straight skeleton", which is mentioned in the article as being among the published solutions, but too slow and error-prone. https://en.wikipedia.org/wiki/Straight_skeleton https://en.wikipedia.org/wiki/Straight_skeleton There's no explicitly spiraling/lawnmower aspect to the straight skeleton: you may have a raster-based incremental literally spiralling solution in mind, but for the geometric examples they show this would probably be inefficient. It's going to have to traverse a large multiple of the perimeter of the polygon as it spirals.
Houshalter 9y ago
That would give you the thickest part of the shape, not necessarily the center. If I'm understanding correctly anyway. E.g. imagine a long skinny shape with a big thick circle at the end. The lawnmower would finish shaving the main part of the shape and declare the circle the center! If I had to design an algorithm to do this, my idea would be to sample a bunch of points on the polygon, then take their median x and y values. Then find the closest spot on the polygon to that value, if it's not inside the polygon.
- iak8god 9y ago
  > That would give you the thickest part of the shape, not necessarily the center. But we're looking for the "visual center," defined in the article as "a point inside a polygon with as much space as possible around it."
  - Houshalter 9y ago
    Right, but I think that definition falls apart if you look at pathological shapes instead of nice convex ones. If you just randomly generate polygons, the thickest part of the shape can appear anywhere, including a very far off edge. And if you cut a tiny opening into that part of the shape, the center would completely move.
iak8god 9y ago
I was imagining a solution that I think is equivalent to what you suggest. repeatedly shrink the object by a one (or small n) pixel margin. When there's nothing left, back up one step. You'll have one (maybe a few) tiny object that should be inside your largest inscribed circle and near its center.
- iak8god 9y ago
  Too late to edit(?) so self-reply. This shows the shrinking approach (and was a fun excuse to play around with octave-image): http://imgur.com/a/cM8TU http://imgur.com/a/cM8TU

deleted 9y ago

[deleted]

ricardobeat 9y ago

Im not sure about the exact cost, but at first sight this approach would still require a lot more operations per line - you need to keep the lawnmower inside by measuring distance/intersection to closest edge, plus track the already mowed area. Maybe making the lawnmower wide enough could make it fast and accurate enough for specific use cases.

theoh 9y ago

That's equivalent to calculating the "straight skeleton", which is mentioned in the article as being among the published solutions, but too slow and error-prone. https://en.wikipedia.org/wiki/Straight_skeleton https://en.wikipedia.org/wiki/Straight_skeleton There's no explicitly spiraling/lawnmower aspect to the straight skeleton: you may have a raster-based incremental literally spiralling solution in mind, but for the geometric examples they show this would probably be inefficient. It's going to have to traverse a large multiple of the perimeter of the polygon as it spirals.

Houshalter 9y ago

That would give you the thickest part of the shape, not necessarily the center. If I'm understanding correctly anyway. E.g. imagine a long skinny shape with a big thick circle at the end. The lawnmower would finish shaving the main part of the shape and declare the circle the center! If I had to design an algorithm to do this, my idea would be to sample a bunch of points on the polygon, then take their median x and y values. Then find the closest spot on the polygon to that value, if it's not inside the polygon.

iak8god 9y ago
> That would give you the thickest part of the shape, not necessarily the center. But we're looking for the "visual center," defined in the article as "a point inside a polygon with as much space as possible around it."
- Houshalter 9y ago
  Right, but I think that definition falls apart if you look at pathological shapes instead of nice convex ones. If you just randomly generate polygons, the thickest part of the shape can appear anywhere, including a very far off edge. And if you cut a tiny opening into that part of the shape, the center would completely move.

iak8god 9y ago

I was imagining a solution that I think is equivalent to what you suggest. repeatedly shrink the object by a one (or small n) pixel margin. When there's nothing left, back up one step. You'll have one (maybe a few) tiny object that should be inside your largest inscribed circle and near its center.

iak8god 9y ago
Too late to edit(?) so self-reply. This shows the shrinking approach (and was a fun excuse to play around with octave-image): http://imgur.com/a/cM8TU http://imgur.com/a/cM8TU