Efficient Algorithm for Rectangular Spiral Search

NASA’s Jet Propulsion Laboratory

An algorithm generates grid coordinates for a computationally efficient spiral search pattern covering an uncertain rectangular area spanned by a coordinate grid. The algorithm does not require that the grid be fixed; the algorithm can search indefinitely, expanding the grid and spiral, as needed, until the target of the search is found. The algorithm also does not require memory of coordinates of previous points on the spiral to generate the current point on the spiral.

Figure 1. A Rectangular Grid of n×m cells is overlaid on the area to be searched.

The search is started at a point (more precisely, in a grid cell), denoted the center of the spiral, that has been chosen previously as the point most likely to coincide with the target. The search is to be performed on a grid of n×m cells, where m>n and a ≡ m – n is denoted the rectangular excess of the search pattern (see Figure 1). The spiral search is performed in steps numbered simply 1, 2, 3..., and t represents the number of the current step.

Figure 2. A Spiral Search Pattern was generated in an area initially overlaid with a 3×5 grid.

The inputs to the algorithm are t and the rectangular excess that is either specified in advance or calculated from the rectangular grid used to span the initial search area. The output of the algorithm is the pair of integer coordinates (i,j) of the current point on the spiral with respect to the center of the spiral. Figure 2 presents, as an example, the first 15 steps of the spiral generated by this algorithm for a search that starts at a point in a 3×5 rectangle.

This work was done by Paul Brugarolas and William Breckenridge of Caltech for NASA’s Jet Propulsion Laboratory.

The software used in this innovation is available for commercial licensing. Please contact Karina Edmonds of the California Institute of Technology at (626) 395-2322. Refer to NPO-42057.