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.
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
In the absence of evidence, opinion is indistinguishable from prejudice.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
Read Where should I post X? if you're not absolutely sure you're posting in the right place.
Please read these before you post! —
Posts may use any of the Perl Monks Approved HTML tags:
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
| |
For: |
|
Use: |
| & | | & |
| < | | < |
| > | | > |
| [ | | [ |
| ] | | ] |
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.