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

Dharhas Pothina Dharhas.Pothina@twdb.state.tx...
Thu Dec 4 12:00:54 CST 2008

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

thanks,

- dharhas

```