FIGURE 1
..
Moving
like an Unintelligent
Mouse
In a Labyrinth
The basic idea of the algorithm is the desciption of the movement of an unintelligent mouse in a labyrinth with clockwise spin if the move fails and a counter clock wise spin if the move succeeds for the next exploring direction. Versus the contouring other authors like of Paul. D. Brouke it delivers open or closed polygons (rings) and it is possible to create faces over on height intersection plane. To build a DEM or body of heigth lines the algorithm will take more than height intersections and therefore more computational power.
In technical terms of the time the routine was implemented as a direct drawing routine to the, in recent considerations, low resoluted PC DOS screen. I extract the these parts from the routine and try to make it industial hard, to check border conditions, uniqe existence polygons of each height itnersected part.
The common way is to show 3 dimensional functions and data sets is to use well known perspective projections. These projections looking very good but they have a big disadvantage. You can't look behind the in front shown hills and it is difficult to estimate the distance of between some certain "hills" objects because of the perspective distortion.
The procedure to get these facts more comfortable in viewing is to create contour maps and it works as follows Make a certain height intersection (plain parallel to the xy-plane; height=z=const) and mark all levels or grid points witch are grater or equal as the height (binary=1 or RED) and (binary=0 or yellow).
In this case you have a coarse assuption to the countour of your function or data set but the location of the border line will be unsharp (can differ defined by gridwidth).
After locating the points aroud the "hill" you can interplate the exact location of the intersection point ("hill to gound") inside of your grid position.
Figure 1 shows the 3D perspective projection of function of the well known function f(x,y) = 5 exp(-x²) exp (-y²) - 2.5 and the intersection plain of this function g(x,y) = 0. And how to get the binary field to determin the contout corresponding to the intersection height.
FIGURE 1
Now will take only the gridpoints of these "height cut" and consider them as a binary labyrinth while the gridpoints lager or equal the intersection will be "wall points" and the points lower than the intersection height will be "work able points" (.. see figure 2).
FIGURE 2
Now we imagine that we have a little friend, a mouse. But forunally the mouse is a mad in mind so she can only turn clockwise if a move to the next point fails and she can only turn counter clock wise if a move is successful. So she have in every time a hand at the wall (or "hill"). Now we let move the mouse through the labyrinth (or "landscape") to explore it.
At first we have to lead her to the next wall point. We explore the the possible pathes from west to est and from north to south so we can find only wallpoints coming from north and all wall points we have visited laying in western direction, because we want to find the all. If we find a wall point, the point before will be our start point (be carefull, what happens if the point is at the border of your grid ..whats the point before). Figure 3 will show how we lead the mouse agent to a start point.
FIGURE 3
How will walk the mouse agent. After a succesfull move the agent will turn counter clockwise to select his next walk point. After a faild move the agent will turn clockwise to select his his next walk point.
FIGURE 4
Figure 4 shows the following moving of the mouse:
FIGURE 5
FIGURE 6
Now we have the path way where th mouse moves along the wall and we have to interpolate the real height between last successfull mouse position and the current "move failed position". To illustrate this see figure 7.
FIGURE 7
But there can exist cursor positions where an interpolation is not possible
like heigth field points touching the grid extention (..see next chapter).
FIGURE 8
If an object was detected, the algorithm set the binary field to a so called visited state. If a second object should be detected it can happens, that a former detected object overwrite the start boundary condition. That means it switches the binary grid transitition 0 - 1 to 2 - 1 (if 0 is ground, 1 is hill and 2 is visited) an agent searching from north a new transitition code will find nothing.
I' solve that problem by oversampling with factor two (double each grid element twice). By the way, the interpolation will be smoother by getting "corner" and "frame" elements. The solution will be shown in figure 9.
FIGURE 9
The next problem is created by poor formed boundary handler the grid binary. In some cases, when the height field touches the grid extentions, the mouse agent has to move out of the grid extention. Interpolations are in this case not possible becaus heigthvalues are not available and so the move in and out of the grid can't be exact discribed. You have make some "rounding" or "setting" assumtions. For the formulation of the algorithm it is unimportant, because I can set flag for the location of the cursor and handle these assumptions later. To realize the grid extention boundary handling, the binary grid is equiped thit a border belt to allow the cursor movings out oft the extention of the grid claim a special flag.
At least I' will show the resulting contour for following code:
Procedure MakeBitmap(FileName:String);
Var aBMP:TBitmap;
x,y: Double;
//---------------------------------------------------------------------
Procedure Draw(Color:TColor);
Var bi,bj:Integer;
Begin
aBMP.Canvas.Pen.Color:=Color;
With Contour Do
For bi:=1 To NumOfRings Do Begin
For bj:= 1 To Rings[bi].NumOfMoves Do
If bj=1 Then
aBMP.Canvas.Moveto(
Round(Rings[bi].Moves[bj].CorrectX(height)*cBMPOverSample),
Round(Rings[bi].Moves[bj].CorrectY(height)*cBMPOverSample))
Else
aBMP.Canvas.LineTo(
Round(Rings[bi].Moves[bj].CorrectX(height)*cBMPOverSample),
Round(Rings[bi].Moves[bj].CorrectY(height)*cBMPOverSample))
End;
End;
//---------------------------------------------------------------------
Begin
Max:=51;
SetLength(TF,Max);
aBMP:=TBitmap.Create;
aBMP.Width := Max*cBMPOverSample;
aBMP.Height:= Max*cBMPOverSample;
aBMP.Pixelformat:=pf24bit;
For i:=0 To max-1 Do Begin
Setlength(TF[i],Max);
x:=(i - (Max-1)/2) / Max * 4;
For j:=0 To Max-1 Do Begin
y:=(j - (Max-1)/2) / Max * 4;
TF[i,j]:=5 * exp(-sqr(x))*exp(-sqr(y))-2.5;
End;
End;
RawContour(False,-2.49,TF,Contour);
Draw(RGB(0,0, 50));Contour.Clear;
RawContour(False,-2.25,TF,Contour);
Draw(RGB(0,0,100));Contour.Clear;
RawContour(False,-2,TF,Contour);
.......
RawContour(False, 2,TF,Contour);
Draw(RGB(150, 50, 150));Contour.Clear;
RawContour(False, 2.25,TF,Contour);
Draw(RGB(150, 100, 150));Contour.Clear;
RawContour(False, 2.49,TF,Contour);
Draw(RGB(150, 150, 150));Contour.Clear;
aBMP.Canvas.TextOut(10,10,'5 * exp(-sqr(x))*exp(-sqr(y))-2.5');
Writeln('.. storing to file '+FileName);
aBMP.SaveToFile(FileName);
Writeln('.. Ready results are in bitmap '+Filename);
aBMP.Free;
The resulting contour will be shown in figure 10.
The copyright of the basic algorithm holds Markus Weber - 1990. The copyright of the Delphi port, technical extraction as well modifications to make the routine save laying by Alexander Weidauer (c) - II/2002. The contents of this files are used with permission, subject to the Mozilla Public License Version 1.1 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License athttp://www.mozilla.org/MPL/MPL-1.1.html
Software distributed under the License is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License for the specific language governing rights and limitations under the License.