File Grid.h

↰ Parent directory (ADS/graph)

The visits of a GRID, the implicit graph whose nodes are the cells ( r , c ) of a rows x cols matrix and whose edges are the moves from a cell to the cells at the given differences ( dr , dc ) that are inside the matrix and free: FOUR_MOVES (the four sides of a cell), EIGHT_MOVES (the sides and the corners, the king) and KNIGHT_MOVES (the knight).

Definition (ADS/graph/Grid.h)

Detailed Description

The graph is never built: the cells are its nodes and a vector of moves its adjacency, so that each visit takes :math:` Theta( R C ) ` time for k moves per cell treated as a constant, against the :math:` Theta( R C k ) ` space of the lists of adjacency that it saves.

  • gridDistances(), the visit in breadth of section 9.5 from several sources at once, all of them at distance 0 in the queue: each cell gets its distance in moves from the nearest source, INF if none reaches it. It is the algorithm of Lee for the routing on a grid, and with the sources a whole set it gives the distance transform of an image; with no obstacles the two raster passes of Rosenfeld and Pfaltz compute the same distances for FOUR_MOVES and EIGHT_MOVES in the same time without a queue;

  • gridDistance(), the distance from one cell to another, the visit stopping when the target leaves the queue; the A* of Hart, Nilsson and Raphael, with the distance of Manhattan as its admissible heuristic, examines fewer cells when the target is far from the obstacles, with the same bound in the worst case;

  • floodFill(), the paint bucket: the cell ( r , c ) and every cell joined to it by moves through cells of its colour get the new colour; the visit paints a cell when it enters the queue, so that the colour itself marks the cells reached and no other matrix is needed. The fill by spans of Smith pushes a run of a row at a time instead of a cell, with fewer operations on the queue for the same bound;

  • knightDistance(), the fewest moves of a knight between two squares of an n x n board, INF if there is no way (only on the boards of 1, 2 and 3 squares a side): a visit in breadth of the graph of the knight moves, :math:` Theta( n^2 ) `; on the infinite board the distance has a closed form, computed in O( 1 ), which differs from that of a finite board near its corners.

The contracts [see File Contract.h]: the grid has rows, cols >= 0, the matrices are rectangular, each source or start is a cell of the grid (and free, for the visits); at the level of the audits gridDistances() ensures that its distances are those of a breadth first visit (0 on the sources, and each reached cell but a source one move farther than a neighbour). The functions are defined in Grid.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, section 9.5, https://algoritmicamente.it/materiali/libro/capitoli/cap09.pdf

    1. Moore, The shortest path through a maze, Proceedings of the International Symposium on the Theory of Switching, 285-292, 1959

    1. Lee, An algorithm for path connections and its applications, IRE Transactions on Electronic Computers EC-10(3), 346-365, 1961, doi:10.1109/TEC.1961.5219222

  1. Rosenfeld, J. L. Pfaltz, Sequential operations in digital picture processing, Journal of the ACM 13(4), 471-494, 1966, doi:10.1145/321356.321357

    1. Hart, N. J. Nilsson, B. Raphael, A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics 4(2), 100-107, 1968, doi:10.1109/TSSC.1968.300136

    1. Smith, Tint fill, Proceedings of SIGGRAPH 1979, 276-283, 1979, doi:10.1145/800249.807456

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Typedefs

Variables