need urgent help

Kennung Eins · 04-26-2002, 21:31 | posts: 1,619 | Location: C000-CFFF

Ok, 
I just need an idea, QUICK... 
 
Do you know binary search trees? 
Do you have an idea how to realize a 2-dimensional binary search tree? 
 
Normally binary search trees do only compare ONE property, but I need to compare & sort TWO of them...DAMN... 
 
The reason: imagine a coordinate system. 
I have the values (x,y) of different fields within the coordinate system. 
Now I need to compare several fields with their (x,y) coordinates. 
 
I want to use the binary search tree to localize at first (x) and then (y). 
 
Any idea? 
I know, it's difficult... 
 
BTW: you're helping me with my semester work! <IMG SRC="smileys/smile.gif"> 
It needs to be finished in 4 days <IMG SRC="smileys/frown.gif"> This message was edited by Kennung Eins on 26 Apr 2002 01:34 PM

Abdul Alhazred · 04-26-2002, 22:17 | posts: 2,726 | Location: kTbc10, Andromeda

I don't know exactly what you're talking about (way above my level of math) and this might sound stupid, but couldn't you first compare the x coordinate and then have another search for the y coordinate, the x now being fixed? That's how I adjust objects in 2D and 3D space. Dunno. <IMG SRC="smileys/confused.gif">

Kennung Eins · 04-26-2002, 22:36 | posts: 1,619 | Location: C000-CFFF

Hmm yeah I just thought of this several minutes ago, and now I'm doing it exactly this way. 
 
When I'd get the other way (if I could get it to work) working then I could definately show-off in front of my professor ;-)

05-02-2002, 09:10 | posts: n/a

hmm.. seems i am late nw, but u tried to get the intersection ?? 
or what do u mean with vcompare? if their the same? what else could u compare in a 2d area? 
are it recs? 
anyway tpo late now.. 
 
so how was it? finnished? got it to work?

David · 05-04-2002, 00:51 | posts: 3,395 | Location: Kansas

If you're using Java, make a Node object which stores the x, y coordinates and then use a seperate key to sort through them. 
 
1.6 GHz AMD Athlon XP 1900+ @ 1.71 GHz 
OCZ Goliath W/ Delta 50 CFM HSF 
Epox 8HKA+ Motherboard 
512 MB OCZ PC2700 DDR 
IBM Deskstar 60GXP 60 GB HD 
Gainward GeForce4 Ti4400 @ 300/650 
Hercules Game Theater XP 
Enermax 451P-VE 431 Watt PS 
Antec 1030B Case Modded w/ Dual 120mm blowholes 
 
Windows XP Pro, Det. 28.80 
3DMark2001 Score: 10635 <A HREF="http://service.madonion.com/compare?2k1=3242988" TARGET=_blank>http://service.madonion.com/compare?2k1=3242988</A>

Kennung Eins · *Last edited by Kennung Eins; 04-26-2010 at 20:11.*

<BLOCKQUOTE>quote:<HR>Originally posted by -ARP-the_anti_christ: 
hmm.. seems i am late nw, but u tried to get the intersection ?? 
or what do u mean with vcompare? if their the same? what else could u compare in a 2d area? 
are it recs? 
anyway tpo late now.. 
so how was it? finnished? got it to work?<HR></BLOCKQUOTE> 
I wanted to do it the following way: 
 
I have an object which has coordinates (int x,int y) included. 
You know how a search Tree works? 
Let's say you have the numbers 8,5,4,9,6 
it does it this way: 

 
-At 1st it takes the 8, puts it into the root. 
-Then it takes the 5, puts it left of the 8, becasuse it's smaller than the 8. 
-Takes the 4, puts it left of the 8, left of the 5, because it's smaller than 8 and 5. 
-takes the 9, puts it right of the 8 because its bigger than 8 
-takes the 6, puts it left of the 8, right of the five because it's smaller then 8 but bigger than 5 
 
But now I wanted to have a tree that does not save entries with only one dimension, but two. 
Now tell me: How can I use a binary search tree to compare these elements (just some examples): 
(8,2),(12,33),(1,1),(8,9),(5,11) 
Is this possible? 
 
Or should I need 2 search trees, one for the (x)-Element and one for the (y) element, while each (x)-Element has an own tree of the (y) elements? This message was edited by Kennung Eins on 12 May 2002 06:47 AM

Kennung Eins · 05-12-2002, 14:51 | posts: 1,619 | Location: C000-CFFF

<BLOCKQUOTE>quote:<HR>Originally posted by DarkWeasel: 
If you're using Java, make a Node object which stores the x, y coordinates and then use a seperate key to sort through them.<HR></BLOCKQUOTE>I noticed I could do it much easier than with a search tree. 
I just used a simple double linked list to store all the elements and then just searched for the element I wanted to find. If it was not included then this was enough for me to know.