Walking route that covers the largest area in shortest distance

Question

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.

Answer 1

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[3]                                       #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. :)

Answer 2

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!