[SciPy-user] Efficient way of finding the parent element of apoint in an unstructured triangular

[Dharhas Pothina]

Hi Robert,

Ok so if I understood you correctly what I would be doing is using the nearest neighbour algorithm to find the closest node to the point and then loop through the 5 or 6 elements that have that node as a vertex and check which whether the point is inside for each of those elements. 

>From the sound of it as long as the ANN search is fairly efficient I might be able to speed the process up quite a bit.

I'll probably try your second reference, I'm not too keen on installing the SVN version.

thanks,

- dharhas

>>> Robert Cimrman <cimrman3 at ntc.zcu.cz> 12/5/2008 4:09 AM >>>
Hi Dharhas,

Dharhas Pothina wrote:
> Hi,
> 
> I have an unstructured triangular mesh. ie a list of nodal locations
> and a list of element connectivity.
> 
> node #,x,y
> 1 10.0 10.0
> 2 10.0 12.0
> ...
> 
> element #, node1 ,node2 ,node3
> 1 4 3 5
> 2 1 3 7
> 3 2 9 6
> ...
> 
> where node1, node2 and node3 are the nodes that make each triangle
> element.
> 
> Given a set of x,y points I need to create a list of parent elements.
> ie for each point I need to find the triangle that contains it.
> 
> Presently for each point I cycle through the list of elements and for
> each element calculate whether the point is inside or outside the
> triangle by checking if the sum areas of the triangle formed by the
> point and the each node is the same as the area of the element.
> 
> This works but is inefficient because I'm cycling through the entire
> list of elements for each point and calculating the areas each time.
> Do any of you know of a more efficient way to do this?

You could create an inverted connectivity - like you have the list of 
elements which point to the nodes, you would have, for each node, a list 
of elements the node is contained in.

something like (not tested, slow, just to get the idea):

iconn = [[] for ii in xrange( nodes.shape[0] )]
for iel, row in enumerate( elements ):
     for node in row[1:]:
         iconn[node].append( iel )

Then you would have a problem for finding the nearest neighbours in two 
sets of points, for which several algorithms exist (see e.g. [1], [2]). 
After machting the points just look to the iconn and choose one of the 
elements.

cheers,
r.

[1] scipy.spatial.KDTree (in SVN version, added recently by Anne M. 
Archibald)
[2] http://www.cs.umd.edu/~mount/ANN/ 

_______________________________________________
SciPy-user mailing list
SciPy-user at scipy.org 
http://projects.scipy.org/mailman/listinfo/scipy-user