# [SciPy-user] Efficient way of finding the parent element of a point in an unstructured triangular mesh.

Robert Cimrman cimrman3@ntc.zcu...
Fri Dec 5 04:09:37 CST 2008

```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/

```