On Oct 15, 2010, at 7:32 AM, Tim Kroeger wrote:
> I see, sounds good. However, it's not quite the same as what I meant.
> Consider the following situation (use a monospaced font to display this):
>
> A - - - - - - - B - - - C - - - D
> | | | |
> | | | |
> | * | | |
> | E - - - F - - - G
> | | | |
> | | | |
> | | | |
> H - - - - - - - I - - - J - - - K
>
> At the position indicated by "*", your algorithm would return the value at
> node E, but mine would return the value at node B because the element in
> which "*" is contained does not know about node E.
I think this is a vote _for_ my algorithm, not against!
> On the other hand, for the purpose I need this for, this is actually not
> really too much of importance, so I might be satisfied with your algorithm.
>
> Anyway, if you have already implemented such a thing, why don't you just send
> it to me? Or, if it is clean enough, why don't you just check it in?
Unfortunately, my algorithm isn't exactly this... it's just related.
> Yes, I certainly should do this. This makes it even slower. I really think,
> I should use your method. Anyway, I think it would be nice to have such a
> thing in the library. What would be the correct API? I would propose
>
> Mesh::get_nearest_node_to(const Point& point);
> System::get_value_at_nearest_node_to(const Point& point, std::vector<Number>&
> values, unsigned int var=invalid_int);
>
> What do you think?
>
> BTW: I will be calling this function extremly often, and in succesive calls
> the points will often be close to each other, so that I think that the method
> should do some fast check to see whether the node might be the same as
> before. One possibility to do that would be that Mesh::get_nearest_node_to()
> will remember the Point and the node that was returend, as well as the
> difference between the distance to this node and the distance to the
> second-nearest node. Then, by the triangle inequality, the next call can be
> short-circuited if the distance of the new point and the remembered point is
> smaller than the remembered difference. The only thing is that I don't know
> how to figure out whether the mesh has changed since the last call, because
> then of course this fast check cannot be used.
I like the general idea of these two functions... however I'm not sure how
useful they would actually be. Like you start to get into here in this last
paragraph... if you are doing this kind of thing then you want it to be highly
optimized (for instance we've hand tuned these algorithms in our code to
perfectly match our situation). Optimizing them for the general case can be
tricky. My point is that when you get into this spatial search game and you
are depending on it being fast... you are almost always going to need to write
something yourself to cater to your particular needs.
That said... again, I don't have anything against adding these functions... I
just wanted to inject a bit of reality. For us, while they are somewhat
related to what we are doing... we wouldn't actually be able to use them. But
maybe they could help people get started.
As for helping you out with the code... here is some pseudocode:
get_nearest_node_to_point(point)
{
Node * closest_node;
Real closest_distance = RealMax;
for(cur_node in active_nodes)
{
Real cur_distance = (cur_node - point).size();
if(cur_distance < closest_distance)
{
closest_node = cur_node;
closest_distance = cur_distance;
}
}
return closest_node;
}
There are a couple more things to think about here as well. This kind of
algorithm will only work with SerialMesh. If you are using ParallelMesh then
the closest node might be on another processor. In that case the whole
algorithm gets a TON more complicated (you need to look for batches of closest
nodes to keep down parallel communication). Also, like you mentioned you may
want to somehow "cache" the closest node... however I would caution against
doing that _in_ this function. Instead I would do it in your own code on the
outside of this function. The reason for that is that the mesh might change
and this function won't know it.
Finally, after you have a working function I would rewrite it using NodeRange
and parallel_reduce() so that it actually runs threaded. Once you get to that
point I can help you out more with that.
Hope that points you in the right direction!
Derek
------------------------------------------------------------------------------
Download new Adobe(R) Flash(R) Builder(TM) 4
The new Adobe(R) Flex(R) 4 and Flash(R) Builder(TM) 4 (formerly
Flex(R) Builder(TM)) enable the development of rich applications that run
across multiple browsers and platforms. Download your free trials today!
http://p.sf.net/sfu/adobe-dev2dev
_______________________________________________
Libmesh-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/libmesh-devel
