map algorithm question

Thread view:

Lou Lipnickey - 06 Mar 2006 21:36 GMT

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

Reply to this Message

Chris Smith - 07 Mar 2006 01:22 GMT

> 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.

Signature

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

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation

Reply to this Message

Lou Lipnickey - 07 Mar 2006 03:19 GMT

Thanks, I'll check it out-Lou

>>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.

Reply to this Message

Roedy Green - 07 Mar 2006 07:23 GMT

>> 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"

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

Chris Uppal - 07 Mar 2006 10:58 GMT

> 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

Reply to this Message

Lou Lipnickey - 07 Mar 2006 22:52 GMT

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

>>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
[quoted text clipped - 7 lines]
>
> -- chris

Reply to this Message

Chris Uppal - 09 Mar 2006 10:48 GMT

> 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

Reply to this Message

Roedy Green - 09 Mar 2006 18:04 GMT

On Thu, 9 Mar 2006 10:50:46 -0000, "Chris Uppal"
<chris.uppal@metagnostic.REMOVE-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

Signature

Canadian Mind Products, Roedy Green.
http://mindprod.com Java custom programming, consulting and coaching.

Reply to this Message

map algorithm question

Free Magazines