<br><br><div class="gmail_quote">2008/4/29 Eric Fowler <<a href="mailto:eric.fowler@gmail.com">eric.fowler@gmail.com</a>>:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br><div class="gmail_quote"><div class="Ih2E3d">On Mon, Apr 28, 2008 at 8:33 PM, Sylvain Bougerel <<a href="mailto:sylvain.bougerel.devel@gmail.com" target="_blank">sylvain.bougerel.devel@gmail.com</a>> wrote:<br></div>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="Ih2E3d">
Sorry this comes a little late:<br>
<div><br>
On Fri, Apr 25, 2008 at 12:16 PM, Eric Fowler <<a href="mailto:eric.fowler@gmail.com" target="_blank">eric.fowler@gmail.com</a>> wrote:<br>
> I have a toy app that is storing a set<> of pointers to a PlanePoint object,<br>
> itself little more than a wrapper for {int x, y;}.<br>
><br>
> Since I am storing pointers I want to store pointers in my KDTree too. With<br>
> that in mind, I wrote this:<br>
><br></div><br></div><div class="Ih2E3d">
Now, in the KD tree, as Paul explained in this mail, we use an<br>
accessor to get the data, we do not directly manipulate the element.<br>
So you need to define the accessor just as Paul told you.<br>
<br>
May be, according to your example, it will look like smth like this:<br>
<br>
struct accessor {<br>
typedef int result_type;<br>
int operator () (const PlanePoint *e, int k) const { return<br>
(k==0)?e->x, e->y; }<br>
};</div></blockquote><div><br>I had done something like this at some point and was still getting errors.But I have made progress and shall revisit it. <br><br> </div><div class="Ih2E3d"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
<br>
Okay I haven't tried. Of course, as Paul says you shouldn't move your<br>
PlanePoint around in memory. But if you're using pointers in your<br>
set<> as well, I don't think there is a danger.<br>
</blockquote><div> </div></div><div class="Ih2E3d"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Why just not using a pointer at all? Your object is just a few `int'?<br>
You will gain in performance when you need to do computation (cause it<br>
does not need to access the memory of the pointer) and you will also<br>
gain in ease with your implementation. You might consume more memory,<br>
but not necessarily, because you will not leak memory with copies of<br>
your plane object.</blockquote></div><div><br>Hmm, that is an idea. I was thinking of something like this: <br><br>class MyPoint<br>{<br>public: int x, y; <br><br>char * data; <br>int more_data;<br>double still_more_data;<br>
bool by_now_you_get_the_idea;<br>
};<br><br>...and did not want to duplicate all that stuff in the kdtree, especially since I had reasons for storing the structs elsewhere (need to lookup on different criteria, effectively a different index). <br></div></div>
</blockquote><div><br>if that is the extent of your data, then it would just use copies inside the kdtree instead of pointers.<br><br>i use pointers when i need to find an item, and then refer back to where it was originally in the vector... or if there was a *lot* of data in each point.<br>
<br>check sizeof(MyPoint), it'll be about 18 bytes or so. thats not much. even if you had a million items, thats only 18mb. trivial relative to ram these days. start to worry when your tree is something like 100mb or you have to be careful of lots of copies... otherwise you are optimising prematurely.<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="gmail_quote"><div><br>So I could just use the x,y, and a pointer to the MyPoint in a new struct that is made just for KDTree-ability, and store and search over them. This is a little redundant but the coding is simpler and memory-wise only a little more costly. <br>
</div></div></blockquote><div><br>if you use the accessor, then you wont clutter your class up with operators you'll never use without kdtree.<br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="gmail_quote"><div><br>But I think I will try to make the pointers work, mainly because that sort of thing is my style, and I am getting too old to change =-)<br> </div></div></blockquote><div><br>go for it<br>
</div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="gmail_quote"><div><br></div><div class="Ih2E3d"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
<br>
Also there is one side effect that Paul did not mention: you cannot<br>
change the coordinate of your PlanePoint once they are inside the<br>
tree. It's easy to overlook this with pointers because it can be done.<br>
But you would completely invalidate your tree. You would not get<br>
memory corruption, but it will just return weird results when you send<br>
a query.</blockquote></div><div>Yes, I intend to be cautious. I understand the procedure is: (1) remove point from KDTree; (2) change coordinates; (3) re-insert into KDTree; (4) optimiZe() the tree. <br></div><div class="Ih2E3d">
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
</blockquote></div></div></blockquote><div><br>like Sylvain says, you won't get a segfault or crash or memory
corruption - because the pointers are still valid. but it'll throw
kdtree's find off the scent so it may skip entire bits of the tree when
searching.<br>
<br>
no need to remove and re-add... i think it'll be ok if you simply make the change to the item, and then optimise.<br><br>or, i think it will be fine if you remove, and then reinsert without optimisation (? check this, i assume the tree will be just as correct as before, but a little deeper ?)<br>
<br><br> </div><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="gmail_quote"><div class="Ih2E3d"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<br>
<br>
<br>
I recommend against the use of pointers. It does not mean that<br>
libkdtree should not support it. But it's generally a bad idea.<br>
<font color="#888888"></font></blockquote></div></div></blockquote><br>thats one opinion. my opinion is use what is appropriate. if you have a huge amount of data with the locations buried in the data, then use pointers. if you do it without pointers and find that the performance is adequate (in terms of memory usage and copy time), then don't use pointers. there is a greater chance that the compiler will be able to optimise things when you use less pointers and function pointers. and its easier to comprehend once you get used to the idea. and its more STL-like (so you can improve your skills in that coding style).<br>
<br>use pointers, but be aware that you need to remember what the pointers are pointing to, and where. and you need to preserve the target block of memory. its one more thing to remember.<br></div><br><br>