Thanks. I mentioned it because I wanted feedback and I really appreciate yours.

Note that I was forced to invent the banding method single-handedly about 12 years ago at the job I had at that time. It was chosen to work well with a relational database. I was quite happy with it.

I was going to describe my approach in more detail but found that new details just kept cropping up so I just glossed over it. For example, you have to deal with the case when there are no other points in your band. You can also choose to use a bounding circle rather than square in order to trade a few floating point calculations (and more complex code) in hopes of having to read fewer records. My coordinates were integers so I used a bounding square but I I adjusted it as I went (whenever I found a new closest point). And it takes some careful factoring of the problem to make the code for this elegant.

Anyway, I didn't understand your brief explanation of Voronoi so I hit http://www.google.com/ and came up with a Java applet that draws Voronoi diagrams. That made the basic idea quite clear rather quickly. I'm still pretty fuzzy on the details of the algorithm, but I didn't have the time to study it. (:

It looks like Voronoi would present quite a challange for a relational database. The added complexity for the banding method is "add one index" (for Voronoi I'd think you'd probably need three new tables). The update method for the banding method is "insert one record" (for Voronoi you'd have to update all surrounding polygons).

Thanks for the info on Voronoi diagrams. I'll certainly remember that and will dig into them more in the future.

Another aspect of my problem that I solved with the banding method (since at that point I had the code for it written and working) was to find what "zone" a point fell in. Divide a 2-D space into polygons (each called a "zone") and then, given a point, find which zone it belongs to. Again, to make things easy to implement in a relational database, I broke each polygon into rectangles and triangles with all but the hypotenuses being either horizontal or veritcal. Then I built an index on int(log(max(width,height))).int(x/w).y and used the banding method iterating over int(log(size)) until I found a shape that contained the point.

I wasn't as happy with this approach but it work pretty well. Actually, the one table contained multiple pavings for different zone "types" and the algorithm would search for the matching zone of each of several types at once.

But I don't have a point; just "stream of consciousness" on the problem. (:

        - tye (but my friends call me "Tye")

In reply to (tye)Re2: Algorythym for searching closest neighbor by tye
in thread Algorythym for searching closest neighbor by belize

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • 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:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.