map algorithm question

Discussion in 'Java' started by Lou Lipnickey, Mar 6, 2006.

  1. I am working on an application which draws maps on a screen. This is
    done with using sets of x,y coordinates which are made into polygons and
    then drawn in a paintComponent. The user now wants to add elevation (a
    "z" component). The question at hand is how to quickly index into a data
    structure to find an elevation point based on the mouse location (x,y)
    of the screen.

    Which is the best data structure to use to look up an x,y point in order
    to get a z point (elevation). If the exact x,y is not present then
    return the closest.

    I was hoping that someone might either relate how they might have done
    something similar or a pointer to reference. Thanks - Lou
     
    Lou Lipnickey, Mar 6, 2006
    #1
    1. Advertising

  2. Lou Lipnickey

    Chris Smith Guest

    Lou Lipnickey <> wrote:
    > Which is the best data structure to use to look up an x,y point in order
    > to get a z point (elevation). If the exact x,y is not present then
    > return the closest.


    Google quadtree.

    --
    www.designacourse.com
    The Easiest Way To Train Anyone... Anywhere.

    Chris Smith - Lead Software Developer/Technical Trainer
    MindIQ Corporation
     
    Chris Smith, Mar 7, 2006
    #2
    1. Advertising

  3. Thanks, I'll check it out-Lou

    Chris Smith wrote:

    > Lou Lipnickey <> wrote:
    >
    >>Which is the best data structure to use to look up an x,y point in order
    >>to get a z point (elevation). If the exact x,y is not present then
    >>return the closest.

    >
    >
    > Google quadtree.
    >
     
    Lou Lipnickey, Mar 7, 2006
    #3
  4. Lou Lipnickey

    Roedy Green Guest

    On Mon, 6 Mar 2006 18:22:33 -0700, Chris Smith <>
    wrote, quoted or indirectly quoted someone who said :

    >> Which is the best data structure to use to look up an x,y point in order
    >> to get a z point (elevation). If the exact x,y is not present then
    >> return the closest.

    >
    >Google quadtree.


    see also "hanging moss algorithm"
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Mar 7, 2006
    #4
  5. Lou Lipnickey

    Chris Uppal Guest

    Lou Lipnickey wrote:

    > Which is the best data structure to use to look up an x,y point in order
    > to get a z point (elevation). If the exact x,y is not present then
    > return the closest.


    Besides Chris's suggestion of quadtrees, you might also consider the location
    of the sample points for elevations. It might be that they have been taken in
    an approximately regular grid (or even an exact one), in which case you can
    find the elevation more directly by usng a 2-d array of <elevation, sample
    position> pairs.

    -- chris
     
    Chris Uppal, Mar 7, 2006
    #5
  6. Chris - Thanks, I wound up putting together an index lookup structure
    using bin searches along the lines:

    - All values are pre-read into 3 arraylists (x, y, z)
    - The X list is 'collapsed' into a small list (which excludes
    duplicates) with an index which points to the first item in the yList
    which matches the determined xValue.
    - On inquiry, 2 binary searches are performed, first on the collapsed x
    values and then, using the index into the ylist, on only the y values
    which have the same xValue. The z is returned when the y has been "found".
    - Found is one of :
    .. the exact value
    .. the closer of the lower or higher
    .. the first z value if the x,y are in front of the list
    .. the last z value if the z,y are are behind the list.

    I am getting ~25 millisecond performance except in 2 cases where 40
    millisecs are obtained (but these might be optimized also). If arrays
    are used, it would probably get faster.

    I am going to look at the other mentioned earlier.
    Lou


    Chris Uppal wrote:

    > Lou Lipnickey wrote:
    >
    >
    >>Which is the best data structure to use to look up an x,y point in order
    >>to get a z point (elevation). If the exact x,y is not present then
    >>return the closest.

    >
    >
    > Besides Chris's suggestion of quadtrees, you might also consider the location
    > of the sample points for elevations. It might be that they have been taken in
    > an approximately regular grid (or even an exact one), in which case you can
    > find the elevation more directly by usng a 2-d array of <elevation, sample
    > position> pairs.
    >
    > -- chris
    >
    >
     
    Lou Lipnickey, Mar 7, 2006
    #6
  7. Lou Lipnickey

    Chris Uppal Guest

    Lou Lipnickey wrote:

    > I am getting ~25 millisecond performance except in 2 cases where 40
    > millisecs are obtained (but these might be optimized also). If arrays
    > are used, it would probably get faster.


    You may be searching Very Large datasets, or be running on a Very Slow CPU (a
    phone, say). But if not then that sounds a little on the slow side to me.
    That's about a million cycles to do a lookup which shouldn't be much worse in
    practise than log(N). I'd expect[*] a couple of orders of magnitude more speed
    at least.

    ([*] That's to say my gut feeling is that that should be possible, and I would
    want to know /why/ if I wasn't achieving it. Always assuming that I cared
    about performance -- which seems likely in this case.)


    > - On inquiry, 2 binary searches are performed, first on the collapsed x
    > values and then, using the index into the ylist, on only the y values
    > which have the same xValue. The z is returned when the y has been "found".


    What happens if the closest point doesn't match exactly in X ? E.g you have Z
    values for points:
    (10, 12)
    (11, 1000)
    and you try to find the closest point to (10, 1000). I may well have
    misunderstood your algorithm description, but I /think/ it would come up with
    (10, 12) rather than the (much!) closer (11, 1000).

    -- chris
     
    Chris Uppal, Mar 9, 2006
    #7
  8. Lou Lipnickey

    Roedy Green Guest

    On Thu, 9 Mar 2006 10:50:46 -0000, "Chris Uppal"
    <-THIS.org> wrote, quoted or indirectly
    quoted someone who said :

    >
    >> I am getting ~25 millisecond performance except in 2 cases where 40
    >> millisecs are obtained (but these might be optimized also). If arrays
    >> are used, it would probably get faster.


    One thing to think about is how much do you hop all over RAM in your
    lookup. You may be triggering some page faults.

    Try pruning away anything else using RAM. Think if it is possible to
    do the majority of your lookup process on smaller compact tables.

    It can be as simple as separating the lookup info from the data, so
    you are not paging in data during the early stages of the lookup.

    As always you want to profile to find out where the time is going. It
    could be chewed up in frequent GC. A bigger heap may be all you need.

    see http://mindprod.com/jgloss/profiler.html
    --
    Canadian Mind Products, Roedy Green.
    http://mindprod.com Java custom programming, consulting and coaching.
     
    Roedy Green, Mar 9, 2006
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. alex
    Replies:
    1
    Views:
    688
    Lau Lei Cheong
    Feb 4, 2005
  2. Ahmed Moustafa
    Replies:
    0
    Views:
    811
    Ahmed Moustafa
    Nov 15, 2003
  3. Michael Klatt

    Algorithm advice needed for std::map

    Michael Klatt, Apr 19, 2004, in forum: C++
    Replies:
    8
    Views:
    3,488
    Michael Klatt
    Apr 21, 2004
  4. Bapaiah Katepalli
    Replies:
    1
    Views:
    1,531
    Mike Treseler
    Jun 23, 2006
  5. cayblood
    Replies:
    5
    Views:
    6,282
    Calum Grant
    Nov 3, 2005
Loading...

Share This Page