map algorithm question

L

Lou Lipnickey

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
 
C

Chris Smith

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

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

Chris Smith - Lead Software Developer/Technical Trainer
MindIQ Corporation
 
C

Chris Uppal

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

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
 
L

Lou Lipnickey

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
 
C

Chris Uppal

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

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
 
R

Roedy Green

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
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top