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

Dharhas Pothina Dharhas.Pothina@twdb.state.tx...
Fri Dec 5 12:07:37 CST 2008


Dear Maggoo,

This is an interesting algorithm, do you have a name or reference for it? One question I have is how you would decide what to use for the size of the uniform grid cells(i.e. dx & dy). I can see that a larger cell size would involve searching through more elements but a cell size which is too small would have the problem of cells that don't contain any nodes. 

- dharhas

>>> Maggoo <heliocbortolon@gmail.com> 12/5/2008 11:55 AM >>>
Dear Dharhas Pothina,

I think this is a common task in Computational Geometry.

1. Embed your unstructured grid into an ordinary uniform grid.
2. The grid being uniform, the position of the point gives the indexes
of the horizontal and vertical positons of the square it pertains to:
          xidx = int( point.x / grid.dx )
          yidx = int( point.y / grid.dy )
3. You will have to make a connection matrix of the nodes in your
unstructured grid to the squares in the structured one, and relate
each of the elements to which the nodes are part of to the cited
square, i.e.,
           Nodes k1,...,kN are in the square S.
           These nodes are vertices of the elements e1,...,eN.
           So S is connected to e1,...,eN.
4. If the point is in S, so you search only through the elements
e1,...,eN.

I hope this gives you some starting point.


On 5 dez, 14:40, "Dharhas Pothina" <Dharhas.Poth...@twdb.state.tx.us>
wrote:
> 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 <cimrm...@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-u...@scipy.orghttp://projects.scipy.org/mailman/listinfo/scipy-user 
>
> _______________________________________________
> SciPy-user mailing list
> SciPy-u...@scipy.orghttp://projects.scipy.org/mailman/listinfo/scipy-user 
_______________________________________________
SciPy-user mailing list
SciPy-user@scipy.org 
http://projects.scipy.org/mailman/listinfo/scipy-user


More information about the SciPy-user mailing list