Re^2: Contour mapping?

[BrowserUk]

I cannot immediately see whether or not your triangle data set will help. Are the triangles all supposed to be in the same contour band, or are those just surface polygons which could be all over, height-wise?

No. They are just form the mesh via which the "heights" were calculated (FEM). The mesh is generated prior to the heights being calculated, so there's no immediate help there.

That said, if I start at a triangle on the periphery, check each of its node for the highest; then check each of the nodes of all the other triangle that contain that highest point; and so on, eventually it ought to get me to the highest point. But nah, .... I can find that by in a single pass of the nodes data.

So, start at the highest point, follow each of edges of each of the triangles that contain that point, recursively ... to what end? Where am I going?...

Thanks for all the links. Looks like I've a lot of reading to do.

And no, this isn't about plotting; its about calculating and collating all these damned angles.

[pryrt]

So, start at the highest point, follow each of edges of each of the triangles that contain that point, recursively ... to what end? Where am I going?...

I have no idea how efficent this will be; probably, the official literature will get you down a better path. However, my thought:

1. Make a subset of all the points that are connected to the top point (directly or indirectly) that are within deltaz from the top z_t. (So you might end up going down a few triangles, but stop if any of the z are less than z_t-deltaz)
2. sort the subset by each point's angle from z_t; example:

   $top = [$x_t,$y_t,$z_t]; # you got this from your maxima search
   @subset = ( [$x0,$y0,$z0], [$x1,$y1,$z1], ...); # the subset in step1
   @contour = sort { 
     atan2($a->[1] - $top->[1], $a->[0] - $top->[0]) 
     <=> 
     atan2($b->[1] - $top->[1], $b->[0] - $top->[0]) 
   } @subset;
   

3. that sorted list is now the contour line -- every point in that list is within the same height band, and it is sorted such that you could draw a counterclockwise line through those points as your "contour", or calculate other angles as needed along the same contour.

[pryrt]

And no, this isn't about plotting; its about calculating and collating all these damned angles.

Actually, since plotting isn't your goal, I'm not sure you'll need the angle-sort I suggested... or maybe even the local maxima search-connected. It really depends: do you need to keep two different "islands" separate?

              6     g f e d
       7       6            c b
     7   7     6     7 7 7     a
     7 9   7   6   7       7
       7 7    6  7     8   7
             6     7 7   7 7 
                       7

If you have a grid as pictured, would you want to keep the two rings of height=7 separate, or would they all be the same "contour", in terms of the angles you need to calculate? And for calculating angles, assuming the alphabet ridge were all at the same height, would you need to know that a was adjacent to b, and b adjacent to c, but a not adjacent to c (etc)? Or would you just not care about ordering and adjacency, because you just have to compute so many annoying angles?

• If adjacency doesn't matter, and you just need bands of approximately equal height, whether or not they are part of the same ring, then you don't need the local min/max searches, and you don't need the angle sorting
• If adjacency doesn't matter, but you do need to treat the two rings of 7s separately, then you'll still have to do the min/max search, but not the angle sorting
• If adjacency does matter and the rings need to be separate, then the procedure I outlined before is probably a good starting thought.

[BrowserUk]

Or would you just not care about ordering and adjacency, because you just have to compute so many annoying angles?

You're further down the road thinking about this than I am :)

My assumption (perhaps desire is a better term here) is that the contours won't cross those of a higher or lower value (or band); despite that there may be other contours else where that are at the same level.

My first thought reading your reply was that I had a much bigger problem on my hands that I first thought. Detecting whether the contours cross other already discovered contours; or those yet to be discovered would be a exponential explosion of processing and a total nightmare.

Then I thought again; and (I think) that I can get away without that.

Having followed some of your links; and some of the links they contained; a word in one of them -- otherwise not related -- stuck in my brain. The word was "strata".

My current plan of approach is:

• Discover the min and max heights whilst reading the data; divide that range into a series of strata -- I'm using 100 which is arbitrary, but divides up the data into a nice bell-curve of buckets, with ~450 in the extreme edges and 100,000 in the middle bucket.
• Then, within each of those buckets I find the min&max X&Y, and use that to split the area in a (say) a 10 x 10 grid of rectangular regions.
• I then sort the points within each region by X then Y (or vice versa) to speed searching.
• Then I pick a point at random within a bucket, and copy it into a 'contour array'; and then look for the nearest point in the bucket to connect it to.

  The 10 x 10 spacial grid means that I will only have to look in the current region; or the 8 surrounding regions for the next nearest point. Unless they are empty in which case the next one over.

  That will also allow me to detect if one end runs off the edge of the data space.

  The search completes when I find myself connecting back to the first point; or when both ends have left the building.

• Repeat for all strata.

As algorithm definitions go; its kinda sketchy and definitely incomplete; but I have something to explore, which is a sight more than I had a couple of hours ago.

So thank you for the links and questions; they've both served to prompt my brain into gear.