[SciPy-user] Efficient way of finding the parentelementofapoint in an unstructured triangular

[Dharhas Pothina]

>>> "Anne Archibald" <aarchiba at physics.mcgill.ca> 12/5/2008 2:49 PM >>>
> 2008/12/5 Dharhas Pothina <Dharhas.Pothina at twdb.state.tx.us>:
>
> If you build a kd-tree, it's not too hard to design a recursive algorithm:

I have no idea how a kd-tree works. I'm going to have to read up on it before I can follow your algorithm below.

> If you want to use a grid, you can test whether a grid cell meets a
> triangle reasonably easily: they meet if and only if either some grid
> corner is inside the triangle or some triangle corner is in the grid
> cell. If you are feeling devious you can possibly even use OpenGL
> hardware acceleration to determine which grid cells a triangle falls
> into.

Seems like generating this list is going to be pretty expensive. Unless I'm missing something, for each cell I need to cycle through each triangles using 7 point_in_poly checks. It will be useful when I am doing lots of look ups which I may need in the future, but presently I'm just looking for about 15 points so I'm cycling through all the triangle 15 times and doing 1 point_in_poly lookup for each triangle. It may be useful if I pre-generate the list for a given grid and save it to a file.

thanks for your ideas they have really helped me think this through some.

- dharhas