Walking route that covers the largest area in shortest distance

I regularly need to walk across field searching for bird nests. The field are often squares or polygons and the bird nests could be anywhere on the ground in the field. To stand the best chance of finding bird nests, I generally zig-zag across the fields. I have also assumed that zig-zagging covers the largest area in the shortest distance.

Below is a hypothetical field and my current zig-zag approach for walking the field. However, I'm wondering if there is a better way of walking the field in order to cover the largest area?

Assume that I can see 10m either side of line. Can anyone provide R code for routes that would cover 10%, 20%, 30%……90%, 100% of the field?

I'm particularly interested in R code to calculate a walking route, hence why I've used the R tag. • This is a really interesting question! I don't have an answer but intrigued to see what it is. My intuition is that the answer for a rectangle might not generalise to any field shape. I think you'll also need to say how far either side of your path you can 'see'. This turns your walking path into an area instead of a line – ASeaton Jul 5 '17 at 9:41
• One thing to note - your zigzag is probably not optimal as when you turn the sharp corner you are likely surveying the same area twice. If you approximate what you can see as a square around you (say 10m edge) then you should walk horizontally across until you are 5m from the edge of the field. 90 degree turn to the right then walk 10m (to perfectly line up what you have already surveyed) and then 90 degree turn to the right again and traverse the other way. I think if you minimise the areas of overlap where you survey the same area twice you will also minimise distance travelled. – ASeaton Jul 5 '17 at 9:47
• I'd say the spiral will provide a better coverage. The answer also depends on a fraction you are ok with not being surveyed – FelixIP Jul 5 '17 at 10:04
• It's the same problem as finding the optimal route for agricultural machinery, has a name, just can't remember it at the mo – nmtoken Jul 5 '17 at 11:55
• Question edited to assume that I can see 10m either side of line. Im interested in R code for lines that would cover 10%, 20%…90%, 100% of field – luciano Jul 5 '17 at 13:32

This is a really interesting question. I think that the zig-zag is the optimal geometry because this is the path that light would take if both boundaries were mirrors. The slight overlap in area is made up for by the increased efficiency in spanning the square, when walking at an angle to the edge.

While writing R code, we might, therefore want to choose incident angle as the variable that determines the % coverage. Larger the incident angle, less the coverage of space and shorter the path. Here is a sample code using the library gpclib:

#Assume the field is a square of side 100 m.

library(gpclib)
i<-seq(5, 90, 5)                                #set up a range of angles of incidence

inc<-i                                       #demonstrating for a single angle of incidence
#can loop later and plot the relationship with area
y_inc<- sin(pi*inc/180)*100                     #The y increment at each limb of the zig-zag

starts<-seq(0, 110, y_inc)                      #set up the list of y-values at the start of each limb
plot(0, xlim=c(0,100), ylim=c(0,100), type="n", xlab=NA, ylab=NA)
xvals<-cbind(c(0,0,100,100), c(100,100,0,0))

all_poly<-as(cbind(c(0,0),c(0,0)), "gpc.poly")
for(j in 1:(length(starts))){
if (j%%2==0) {                                #to decide whether to pick forward or reverse x-axis
x_poly<-xvals[,2]
}
else x_poly<-xvals[,1]
polygon(x_poly, c(starts[j]-10, starts[j]+10, #plot each polygon
starts[j+1]+10, starts[j+1]-10), col=rgb(1,0,0,0.5))
poly<-as(cbind(x_poly, c(starts[j]-10, starts[j]+10, starts[j+1]+10, starts[j+1]-10)), "gpc.poly")
all_poly<-union(all_poly, poly)               #make a gpc.poly object, calculate union with other polygons
}

perc_area<-area.poly(all_poly)/100              #% area covered in this path

It uses a for loop and therefore, is probably not the most efficient way to do this. But it works! For study design, one could do this over a range of incident angles, plot it against %area covered, fit a curve to the function and find the angles of incidence that lead to 10%, 30% etc of coverage.

But thanks to this question, I did go down a rabbit hole to discover packing problems.

Also, I'd like to read the spiral solution - although it might be impractical for a field study. :)

I suspect this formation is the most efficient for a rectangular space:

xxxxxxxx

.............x

.............x

xxxxxxxx

x.............

x.............

xxxxxxxx

.............x

Farmers, Archaeologists, and scuba divers all use a grid search pattern. So I would just line up your paths 10m from the edges and each other and get walking!