..back to Geographic tools

MUMIL - a cursor based contouring routine

mouse.png .. Moving like an Unintelligent Mouse In a Labyrinth

 Intro     Basic algorithm     Existence & Conditons     Copyright    Downloads

Introduction

The following contouring routine was published in germany 1987 by Markus Weber Turbopascal Tools Practical usage of Turbo Pascal in nature science and I adopt it in 1990 for general use from the third edition of these book ISBN-3-528-24543-3.

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.

 ..to Top

Description of the basic algorithm

The aim to create contouring maps is to create a top view of a given analytical function of f(x,y):R² ->R³ or three dimensional datafield like a digital elevation modell.

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:

  1. Last move was from point 1 to point 2 in direction south. The move was successful and now the mouse try to turn left.
  2. The next move is in direction east but the there is a wall so she turn right again back to south but there is also a wall so she turn to west.
  3. The mouse can move to point 3 sucessfully and turn left wise to south.
  4. The move to point 4 also sucessfull and she will turn east
  5. ...
The next figures will show the moving of the mouse cursor for critical binary grid configurations. If you consider these 4 grphics you can see, that all cases of agent moving are in volved. You only have to turn each image 90 slices of 90 degrees to get all these cases. The mouse moving behavior is invariant about turnig so the existence to come back to the startpoint is fullyfied for all cases.

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).
 

 ..to Top

Unique existence of polygons and interpolation conditions at the grid border

In his book M. Weber used the contour as a drawing routine and he defined a minimal contouring area as a atleast quadratic area with at least 4 points. As I tested then routine as "coordinate oriented" contourer two errors occour.
  1. Sometimes small select hight fields where not found by theexploring mouse.
  2. Some of the side interpolations at broder are not right.
The first problem was relativly easy to solve and is shown demonstrated in figure 8.

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.
FIGURE 10

Copyright

 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 at
  http://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.

 ..to Top

Downloads

 ..to Top

 © - V/2001 Alexander Weidauer