[SciPy-user] Efficient way of finding the parent element of apoint in an unstructured triangular
Fri Dec 5 10:40:28 CST 2008
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.
>>> Robert Cimrman <email@example.com> 12/5/2008 4:09 AM >>>
Dharhas Pothina wrote:
> 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
> 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 )]
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. , ).
After machting the points just look to the iconn and choose one of the
 scipy.spatial.KDTree (in SVN version, added recently by Anne M.
SciPy-user mailing list
More information about the SciPy-user