Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

Re: Re: Map grid to boundary conversion algorithm

by Willard B. Trophy (Hermit)
on Apr 28, 2004 at 02:27 UTC ( [id://348690]=note: print w/replies, xml ) Need Help??


in reply to Re: Map grid to boundary conversion algorithm
in thread Map grid to boundary conversion algorithm

Sorry for the delay. With your comments in mind, I ended up coding it this way:
  1. define a zero-value one cell border around the whole array.
  2. walk through each row horizontally, looking for vertical changes in value. Store each one in a structure containing the left and right values, and the coordinates of the end points
  3. walk through each column vertically, looking for horizontal changes in value, as above.
  4. search for adjoining vertical segments, and merge them.
  5. search for adjoining horizontal segments, and merge them.
  6. Write out the lists of line segments.

It appears that the mapping tool we use is clever enough to join up adjacent lines into areas, so lines are all we need. The reason for the zero-value border isn't initially obvious, but it's necessary for the contouring routine to get its senses right.

I put an example of what a tiny (300m x 300m) test file in my blog, if anyone cares to see what it looks like.

I know my algorithm isn't that efficient; it took nearly 8 hours to process a real 73 x 58 km dataset on a P4-2800. My Fortran version (compiled with the excellent free-for-personal use Intel Fortran Compiler for Linux) looks like it will run at least an order of magnitude quicker.

I'm beginning to warm to Fortran (90, or 95; F77 I cannot love). It has a nifty WHERE command which is somewhere between map and grep.

Yes, at this point, you can say 'He's got away from us Jack.' ...

--
bowling trophy thieves, die!

Replies are listed 'Best First'.
Re: Re: Re: Map grid to boundary conversion algorithm
by BrowserUk (Patriarch) on Apr 28, 2004 at 03:32 UTC

    Glad you have a solution that works for you. It is an interesting problem that I think I would have enjoyed having a crack at, but it still isn't clear to me what format you want the output in? What would the line segments for your original example be?


    Examine what is said, not who speaks.
    "Efficiency is intelligent laziness." -David Dunham
    "Think for yourself!" - Abigail
      Okay, a full set of (small) examples are in my scratchpad. It's a knotty wee problem.

      --
      bowling trophy thieves, die!

        I could be wrong, but I think that you have an error in your algorithm. Your generating the correct line-segments + left-right z-value information, but your coordinates are being right/down-shifted by an interval (I think).

        According to the header of your DSAA data, the X-min/max values are 370/640 which means that your boundary coordinates should vary between 355 (between your imposed 0.0 border and the left edge of the data) and 655 at the right hand edge. But the X coordinates for your line segments varies between 385 and 685.

        A similar out by one interval error appears in the Y dimension with the range of Y-values 655 thru 955 when (I believe) they should be 625 thru 925.

        A little ascii art (scrunched to avoid the OSU PM wrapping:), may make it clearer. The X-370 interval which is part of the original data is not part of the resultant map, but there is a X-670 interval which was not a part of the original data. Similarly for the Y-640 and Y-940 intervals.

        DSAA 10 10 370 640 640 910 0.03 1.0 0.5 0.03 0.03 1.0 1.0 1.0 0.03 1.0 0.1 0.1 0.5 0.03 0.03 0.1 1.0 1.0 0.03 1.0 0.1 0.1 0.03 0.03 0.03 0.1 0.1 1.0 0.03 1.0 0.1 0.1 0.1 0.03 0.03 0.03 0.03 0.03 0.03 1.0 0.5 0.5 0.03 0.5 0.03 1.0 0.5 0.5 0.03 1.0 0.5 0.5 0.03 0.5 0.03 0.1 0.1 0.5 0.03 1.0 0.5 0.1 0.03 0.5 0.03 0.1 0.1 0.1 0.03 1.0 0.1 0.1 0.03 0.5 0.03 0.03 0.03 0.03 0.03 1.0 0.1 0.1 0.03 0.5 0.03 0.5 0.5 0.1 0.03 0.1 0.1 0.03 0.03 0.5 0.03 0.5 0.5 0.1 0.03 0.1 0.1 0.03 -370- 400 430 460 490 520 550 580 610 640 +670 ++ 385 415 445 475 505 535 565 595 625 655 +685 -640- | | | | | | | | | | + | 655-- +-----+-----+-----+-----+-----+-----+-----+-----+-----+---- +-+ 670 | .5 | .03 .03 | 1.0 1.0 1.0 | .03 | 1.0 | 0.1 0.1 + | 685-- + + +-----+ + + + + + 700 | .5 | .03 .03 | 0.1 | 1.0 1.0 | .03 | 1.0 | 0.1 0.1 + | 715-- +-----+ + +-----+ + + + + + 730 | .03 .03 .03 | 0.1 0.1 | 1.0 | .03 | 1.0 | 0.1 0.1 + | 745-- +-----+ +-----+-----+-----+ + +-----+---- +-+ 760 | .1 | .03 .03 .03 .03 .03 .03 | 1.0 | 0.5 0.5 + | 775-- +-----+-----+ +-----+-----+-----+ + + + + 790 | .03 | .5 | .03 | 1.0 | 0.5 0.5 | .03 | 1.0 | 0.5 0.5 + | 805-- + + + +-----+-----+ + + + +---- +-+ 820 | .03 | .5 | .03 | 0.1 0.1 | 0.5 | .03 | 1.0 | 0.5 | 0.1 + | 835-- + + + + +-----+ + +-----+ + + 850 | .03 | .5 | .03 | 0.1 0.1 0.1 | .03 | 1.0 | 0.1 0.1 + | 865-- + + + +-----+-----+-----+ + + + + 880 | .03 | .5 | .03 .03 .03 .03 .03 | 1.0 | 0.1 0.1 + | 895-- + + + +-----+-----+-----+ +-----+ +---- +-+ 910 | .03 | .5 | .03 | 0.5 0.5 | 0.1 | .03 | 0.1 0.1 | .03 + | 925-- + + + + + + + + + + +940+ | .03 | .5 | .03 | 0.5 0.5 | 0.1 | .03 | 0.1 0.1 | .03 + | 955-- +-----+-----+-----+-----+-----+-----+-----+-----+-----+---- +-+

        I think that demonstrates that all the coordinates in the final lines segments have been displaced right and down by 30 units in each dimension.

        That aside, plotting out your (uncorrected) line segments assigning a unique character to each provides an interesting picture of the results.

        a 0.03/1.00/2 475/655 475/685 b 0.50/0.00/3 385/715 385/655 415/655 c 0.50/0.03/3 415/655 415/715 385/715 d 0.00/0.03/2 385/715 385/745 e 1.00/0.10/5 535/745 535/715 505/715 505/685 475/685 f 1.00/0.03/3 565/655 565/745 535/745 g 1.00/0.10/2 625/655 625/745 h 0.00/0.10/3 685/745 685/655 625/655 i 0.00/0.10/2 385/745 385/775 j 0.03/0.10/3 415/775 415/745 385/745 k 1.00/0.03/3 475/805 475/775 505/775 l 1.00/0.50/2 505/775 505/805 m 0.50/0.00/2 685/745 685/805 n 0.03/0.50/3 565/835 565/775 505/775 o 1.00/0.50/2 625/745 625/835 p 0.50/0.10/4 685/805 655/805 655/835 625/835 q 0.10/0.03/4 565/835 565/865 475/865 475/805 r 0.03/1.00/2 595/655 595/895 s 1.00/0.10/3 625/835 625/895 595/895 t 0.10/0.00/2 685/805 685/895 u 0.03/0.50/2 415/775 415/955 v 0.03/0.50/3 445/955 445/775 415/775 w 0.50/0.03/3 475/955 475/895 535/895 x 0.50/0.10/2 535/895 535/955 z 0.03/0.10/3 565/955 565/895 535/895 A 0.03/0.10/2 595/895 595/955 B 0.03/0.10/3 655/955 655/895 685/895 C 0.03/0.00/3 685/895 685/955 655/955 D 0.03/0.10/2 385/775 415/775 E 0.03/0.00/3 415/955 385/955 385/775 F 0.00/0.50/2 415/955 445/955 G 0.03/0.00/2 415/655 475/655 H 0.00/0.03/2 445/955 475/955 I 0.10/1.00/2 475/805 505/805 J 0.10/0.03/3 535/745 475/745 475/685 K 0.00/0.50/2 475/955 535/955 L 1.00/0.00/2 475/655 565/655 M 0.50/0.10/4 565/835 535/835 535/805 505/805 N 0.00/0.10/2 535/955 565/955 O 0.03/0.00/2 565/655 595/655 P 0.00/0.03/2 565/955 595/955 Q 1.00/0.00/2 595/655 625/655 R 0.00/0.10/2 595/955 655/955 S 0.50/0.10/2 625/745 685/745

        gives

        370 400 430 460 490 520 550 580 610 640 670 385 415 445 475 505 535 565 595 625 655 +685 640 | | | | | | | | | | + | 655--- +bbbbb+GGGGGGGGGGG+LLLLLLLLLLLLLLLLL+OOOOO+QQQQQ+hhhhhhhhhh +hh 670 b c a f r g + h 685--- b c +eeeeee f r g + h 700 b c J e f r g + h 715--- +ccccc+ J eeeeeee f r g + h 730 d J e f r g + h 745--- +jjjjjj JJJJJJJJJJJJ+fffff+ r +SSSSSSSSSS +S+ 760 i j r o + m 775--- +DDDDD+vvvvvv kkkkkk+nnnnnnnnnnnn r o + m 790 E u v k l n r o + m 805--- E u v +IIIII+MMMMMM n r o ppppp +p+ 820 E u v q M n r o p + t 835--- E u v q MMMMMM+ r +pppppp + t 850 E u v q q r s + t 865--- E u v qqqqqqqqqqqqqqqqqqq r s + t 880 E u v r s + t 895--- E u v wwwwwwwwwwww+zzzzzz +ssssss BBBBB +B+ 910 E u v w x z A B + C 925--- E u v w x z A B + C 940 E u v w x z A B + C 955--- EEEEEE+FFFFF+HHHHH+KKKKKKKKKKK+NNNNN+PPPPP+RRRRRRRRRRR+CCCC +CC

        The left-z/right-z + line segment coords is a ... um ... ecclectic way of representing the topology? I assume that the there is some reasoning to do with the subsequent processing that uses the data, but quite why this representation is optimal eludes me:)

        Out of interest, how big a volume of data (X-extant/Y-extant) do you normally manage as a single batch? And how long does it take to perform the conversion using FORTRAN?


        Examine what is said, not who speaks.
        "Efficiency is intelligent laziness." -David Dunham
        "Think for yourself!" - Abigail

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://348690]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2024-04-25 14:46 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found