How to find in which triangle a point falls

[Tim Hutton]

At 11:58 02/03/00 +0200, you wrote:
>Hi there
>
>I'm quite new to VTK and I thought the fastest way to decide if I must use
>VTK or my own algorithm will be through the people who are already
>experienced with VTK!  Here is my question :
>
>I have a set of data with elements that basically look like this :
>TriangleID, x1,y1,x2,y2,x3,y3 
>
>The three coordinates are the three points of a triangle (if you couldn't
>guess it from the description ;) and all the triangles make up an
>interconnected mesh.  (Much like a terrain mesh, but only 2D)
>
>If I have a point (x,y) I would like to know in which triangle it falls in
>as short a time as possible.  The total dataset I must eventually work
>through (triangles and points falling in them) will be about 30GB so an
>efficient algorithm is quite important for me.
>
>It seems as if VTK can help me with this, but it is such an all encompassing
>library that I think it will be faster to implement my own algorithm that
>learning to use the whole VTK!  That is, unless you guys can help me by
>suggesting which VTK classes will do the job best.  For example, how do I
>know if a point falls within a certain triangle - is there something in VTK
>that can do that for me, or must I do it myself?
>
>I have played around a bit with VTK and have got a BASIC knowledge of it's
>data structures, so I'm not completely in the dark (I have already used the
>Delaunay2D class successfully to build a TIN).
>
>Any help would be greatly appreciated.
>Etienne

This is just one way to do it:

vtkCellLocator will do exactly what you want, and I think quite efficiently
using buckets. Put your triangles as VTK_TRIANGLE cells into a vtkPolyData,
leaving all the z-coords as zero. Call vtkCellLocator::SetDataSet(my_polys)
and then vtkCellLocator::BuildLocator(). Then for each sample point, call
vtkCellLocator::IntersectWithLine(), passing it a line between +0.1 and
-0.1 on the z-axis, say, to give it something to work with. One of the
return parameters will be the id of the cell that was hit.

It's a bit kludgy to get around the fact that vtkCellLocator is really for
3d data but I use this method successfully. If anyone knows a 2d way then
I'd be interested too.

Actually worse than that, there used to be a bug (there still may be), that
is all the z-coords are zero then vtkCellLocator doesn't work, so I perturb
the first point by a tiny amount and then it works. This was still a
problem in 2.4, may have been solved in 3.1

I use this for doing piecewise affine warps of images using two
corresponding triangulations.

Hope this helps, vtk really can do what you want!

Cheers,

Tim.



---------------------------------------------------------------------------
Tim Hutton, Research Assistant            Email: T.Hutton at eastman.ucl.ac.uk
MINORI Project                          Eternal: T.Hutton at excite.co.uk
Dental and Medical Informatics     http://www.eastman.ucl.ac.uk/~dmi/MINORI
          
Eastman Dental Institute, UCL                    Tel: [+44] (0207) 915 2344
256 Gray's Inn Road, London WC1X 8LD, UK         Fax: [+44] (0207) 915 2303
---------------------------------------------------------------------------
This email represents the views of the sender alone and must not be
construed as representing the views of the Eastman Dental Institute. It may
contain confidential information and may be protected by law as a legally
privileged document and copyright work. Its content should not be disclosed
and it should not be given or copied to anyone other than the person(s)
named or referenced above. If you have received this email in error, please
contact the sender.

--------------------------------------------------------------------
This is the private VTK discussion list. Please keep messages on-topic.
Check the FAQ at: <http://public.kitware.com/cgi-bin/vtkfaq>
To UNSUBSCRIBE, send message body containing "unsubscribe vtkusers" to
<majordomo at public.kitware.com>. For help, send message body containing
"info vtkusers" to the same address.
--------------------------------------------------------------------