19
$\begingroup$

Recently, I was mowing my yard and was thinking about how to use the least amount of time/fuel and how to simulate.

Mowing a yard that is shaped as a convex polygon is not difficult, you can just make a spiral. So,the code:

outMostPolygon = RandomPolygon[{"Convex", 7}];
mowerWidth = 0.03;
tracks = Table[
   outMostPolygon // 
    ScalingTransform[{1 - i*mowerWidth, 1 - i*mowerWidth}, 
     RegionCentroid[outMostPolygon]],
   {i, 0, Floor[1/mowerWidth]-1 }
   ];
Graphics[{EdgeForm[{Thickness[.005],RGBColor[93/255, 189/255, 0]}], FaceForm[RGBColor[124/255, 252/255, 0]], tracks},AspectRatio->Automatic]

gives an example image:

Convex polygonal yard whose treads are essentially its straight line skeleton.

but the problem is most yards have things in them. And the shapes can be concave as well as the yard being concave so the solution is not always a straight line skeleton. And since repeating a point is allowed (we don't care about the aesthetics of the tread lines), FindShortestPath doesn't work or if it can be used it is not straight forward.

Here is a problematic example:

A similar picture above, it is a convex polygon with it's straight line segment skeleton, but it has a random purple concave polygon inside of it.

that was created by using the code:

outMostPolygon = RandomPolygon[{"Convex",  RandomInteger[{3,10}]}];
mowerWidth = 0.03;
tracks = Table[
   outMostPolygon // 
    ScalingTransform[{1 - i*mowerWidth, 1 - i*mowerWidth}, 
     RegionCentroid[outMostPolygon]],
   {i, 0, Floor[1/mowerWidth]-1 }
   ];
pts = RandomPoint[outMostPolygon, RandomInteger[{3,10}]];
centroid = Mean[pts];
sortedPts = SortBy[pts, ArcTan @@ (# - centroid) &];innerPoly = Polygon[sortedPts];
Show[
  Graphics[{EdgeForm[{Thickness[.005],RGBColor[93/255, 189/255, 0]}], FaceForm[RGBColor[124/255, 252/255, 0]], tracks},AspectRatio->Automatic],
  Graphics[{EdgeForm[{RGBColor[122/255, 55/255, 122/255], Thick}], FaceForm[RGBColor[163/255, 73/255, 164/255]], innerPoly},AspectRatio->Automatic]
]

I personally am partial to straight lines only existing and curves and circles don't exist, but if someone wants to throw a curve ball they are welcome to.

$\endgroup$
6
  • 1
    $\begingroup$ I do not think there is much to compute. The area is always the same so any path that does not cross itself is optimal. $\endgroup$ Commented Oct 25, 2023 at 12:25
  • $\begingroup$ @azerbajdzan In some instances, can an optimal path be one that does cross itself? If it was discrete points only, the answer would be no. But for the continuous case, I am not sure. Also, dependencies on how the lattice is made, I am not sure all the hamiltonian paths have the same length. $\endgroup$
    – Teg Louis
    Commented Oct 25, 2023 at 12:44
  • 1
    $\begingroup$ No, path that crosses itself cannot be optimal, since in such a case some of the area would be mowed more than once which means you waste your fuel, time and also the final path length is larger. $\endgroup$ Commented Oct 25, 2023 at 12:51
  • 1
    $\begingroup$ "Any path that does not cross itself is optimal" only holds if turning is free, but it's not (according to the utility function of fuel and time) $\endgroup$
    – Ben Voigt
    Commented Oct 25, 2023 at 14:42
  • 5
    $\begingroup$ This is known as the "Lawn Mowing Problem", and finding the optimal route turns out to be NP-hard. Here's a recent review of the subject, including links to a Jupyter GitHub repository implementing the algorithms. $\endgroup$ Commented Oct 25, 2023 at 18:53

1 Answer 1

19
$\begingroup$

enter image description here

This is just starting ideas for arbitrary regions. Perhaps you can improve it.


Version 1

Define concave region with holes, which can be generalizable to arbitrary complexity:

eq=x^2/2-y^2<=1&&x^2+y^2/7>1/2&&-3<x<3&&-3<y<3;
R=ImplicitRegion[eq,{x,y}];
RegionPlot[R]

enter image description here

Define a grid that covers the region:

grd = Tuples[Range[-30, 30]/10, 2];

By adjusting density / number of grid points you can match the width of the mower. Pick those grid points inside the region:

grdR=Select[grd,RegionMember[R]];

Graphics[Point[grdR], Frame -> True]

enter image description here

Find shortest path:

path=grdR[[FindShortestTour[grdR][[2]]]];

Graphics[Line@path]

enter image description here

This path feels like it is something Jack Nicholson would walk with a mower in the 1980 "The Shining" movie. We can try to improve by introducing a penalty into the distance function. By default the the distance function is simply EuclideanDistance. But consider the following modification:

disF=(1+Abs[CosineDistance[#1+#2,#2-#1]-1]^10)EuclideanDistance[#1,#2]&;

It makes preferable the paths orthogonal to radial vectors from the origin with the hope that it would make path more like a gradual spiral. Power ^10 is a tunable parameter you can use to change the path a bit. By using this distance function we get the image shown at the top left:

path=grdR[[FindShortestTour[grdR,DistanceFunction->disF][[3]]]];
Graphics[{Line@path,Red,Point[grdR]}]

enter image description here

So why is it not a spiral? My first, perhaps wrong, guess is -- it's due to constraint of FindShortestTour giving a tour -- meaning close loop. If you could start at the origin and and at the periphery, perhaps the path would be more spiral-like. That's why you can try using FindHamiltonianPath via building first a Graph. FindHamiltonianPath allows for start and end of the path.


Version 2

I do not have enough computing power to build this one. So this is a toy example. First, build a graph based on a mesh of your region:

g = MeshConnectivityGraph[DiscretizeRegion[R, MaxCellMeasure -> 1]]

I made it intentionally low-resolution due to computing power limitation. Pick some start and end vertices - one inside and another on outside:

In[]:= se = VertexList[g][[{67, 41}]]
Out[]= {{0, 67}, {0, 41}} 

HighlightGraph[g, se, GraphHighlightStyle -> "Thick"]

enter image description here

Find Hamiltonian Path and plot it -- as shown on the top image right. It does look like a spiral. For better results use finer mesh, but FindHamiltonianPath might take long time.

hami = FindHamiltonianPath[g, Sequence @@ se];
HighlightGraph[g, PathGraph@hami, GraphHighlightStyle -> "Thick"]

enter image description here

$\endgroup$
3
  • 4
    $\begingroup$ I think a penalty for turns might be something to add too. You generally want long straight paths when mowing a lawn, avoid intricate little wiggles like your top left example has on all the main diagonals. It'd definitely be preferable to avoid those 45° switchbacks that you have along the curves, too; better to follow the curve than zigzag back and forth all along it. $\endgroup$
    – Hearth
    Commented Oct 25, 2023 at 13:58
  • 1
    $\begingroup$ @Hearth what the code would look like? $\endgroup$ Commented Oct 25, 2023 at 19:51
  • 1
    $\begingroup$ No clue, I'm afraid. $\endgroup$
    – Hearth
    Commented Oct 25, 2023 at 19:54

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.