Mega Code Archive
Traverse an array spirally outwards
<![CDATA[
Title: Traverse an array spirally outwards
Question: When working on mapping application, I needed to find the "best" point between two locations. To do this I needed to search bitmap pixels between the locations. A good solution was to work from a pixel centred beween the locations and spiral outwards. I could not find any outward spiral array search examples on the web but I am sure they must exist
The solution provided shows how to perform this spiral traverse in a clockwise direction.
Answer:
See the code comments for details
The solution...
procedure TForm1.btnSpiralClick(Sender: TObject);
type
TDirection = ( dirRightwards,
dirDownwards,
dirLeftwards,
dirUpwards);
const
// a simple array
a : array[0..6, 0..6] of char =
(
('z', 'y', 'd', 'o', 'g', 'o', 'n'),
('a', 'n', 'f', 'o', 'x', 'j', 'a'),
('l', 'w', 'e', 'q', 'u', 'u', 'h'),
('e', 'o', 'h', 'T', 'i', 'm', 'o'),
('h', 'r', 'b', 'k', 'c', 'p', 't'),
('t', 'r', 'e', 'v', 'o', 's', 'T'),
('y', 'a', 'd', 's', 'r', 'u', 'h')
);
var
mechanicalResult : string; // mechanically obtained result
processedResult : string; // programmatically obtained result
isMatch : string; // success or failure string
direction : TDirection; // which way to move
numElementsToCheck : integer; // how many to move by
iKount : integer; // for loops
xCoord, yCoord : integer; // x and y array coordinates
numEntries : integer; // size of array =(x * y)
iterations : integer; // how many elements processed
// used to check against numEntries
function test_Coord(coordNum : integer) : boolean;
begin
// ensure that the x or y Coordinate is valid
case coordNum of
0: result := ((xCoord = 0) and (xCoord 1: result := ((yCoord = 0) and (yCoord else
result := false; // satisfy compiler warning
end;
end;
function canProcess : boolean;
begin
// verify we don't exceed movement counter
result := (iKount end;
procedure processElement;
begin
// do something with the element value
processedResult := processedResult + a[yCoord, xCoord];
end;
begin
{
Traverse sequences on number of moves for a clockwise sequence
cycle 1 2 3 4
-------------------------------
left 1 3 5 7 up 1 3 5 on this iteration
right 2 4 6
down 2 4 6
}
// get x and y coordinate lengths
xCoord := length(a[0]);
yCoord := length(a);
// calculate the number of elements
numEntries := xCoord * yCoord;
// find the centre-most array element
xCoord := floor(xCoord / 2);
yCoord := floor(yCoord / 2);
// set the initial direction
direction := dirLeftwards;
// set first movement value
numElementsToCheck := 1;
// identify the solution for a clockwise spiral
mechanicalResult := 'ThequickbrownfoxjumpsoverthelazydogonahotThursday';
// set the first value
processedResult := a[yCoord, XCoord];
// We've done one iteration for the first element
iterations := 1;
// the main loop
while (iterations iKount := 1;
case direction of
dirRightwards: begin
// test to ensure that element is within array
if test_Coord(0) then begin
// increase the xCoord +ve as going right
inc(xCoord);
// Place tests on while loop
while ((canProcess) and test_Coord(0)) do begin
processElement; // do something with element
inc(xCoord); // move to next element
inc(iKount); // increment the loop control counter
end;
dec(xCoord); // gone too far
inc(direction); // set next direction
end;
end; //dirRightwards
dirDownwards: begin
// see cooments for dirRightwards
if test_Coord(1) then begin
inc(yCoord);
while ((canProcess) and test_Coord(1)) do begin
processElement;
inc(yCoord);
inc(iKount);
end;
dec(yCoord);
inc(direction);
inc(numElementsToCheck);
end;
end; //dirDownwards
dirLeftwards: begin
// see cooments for dirRightwards
if test_Coord(0) then begin
dec(xCoord);
while ((canProcess) and test_Coord(0)) do begin
processElement;
dec(xCoord);
inc(iKount);
end;
inc(xCoord);
inc(direction);
end;
end; // dirLeftwards
dirUpwards: begin
// see cooments for dirRightwards
if test_Coord(1) then begin
dec(yCoord);
while ((canProcess) and test_Coord(1)) do begin
processElement;
dec(yCoord);
inc(iKount);
end;
inc(yCoord);
direction := dirRightwards;
inc(numElementsToCheck);
end;
end; // dirUpwards
end; //case
// end of main loop, increment the iterations counter
// by the number of times the direction loop
// has been processed.
inc(iterations, iKount-1);
end; //while
// Test the output to see if correct
if (mechanicalResult = processedResult) then
isMatch := 'is correct'
else
isMatch := 'is in error';
MessageDlg( 'Correct Output' + chr(013) +
mechanicalResult + chr(013) +
'Evaluated Output' + chr(013) +
processedResult + chr(013) +
isMatch, mtInformation, [mbOK], 0);
end;
This example uses a square array. Non square arrays can be handled by checking array boundaries. Also you could pick a non-centre start point but again would need to check array boundaries carefully.
regards
]]>