arndt@ttds.UUCP (Arndt Jonasson) (03/29/85)
<>
In the Finite Element Method (FEM), two-dimensional regions are divided
into triangles. The corners of these triangles are called nodes. The
triangulation may then be represented by these vectors:
xp: ARRAY [1 .. no_of_nodes] (* The x coordinate of a point *)
yp: ARRAY [1 .. no_of_nodes] (* The y coordinate of a point *)
tri: ARRAY [1 .. 3, 1 .. no_of_triangles] (* The corners of a triangle *)
Problem: Given a pair of coordinates (x,y), what is the best way to
determine what triangle it lies in?
Traversing the whole tri vector and testing whether the point lies within
each triangle is a straightforward method, but rather ineffective when the
number of triangles is large. What are the methods commonly used in FEM for
this problem?
One way that comes to my mind is to compile a table of neighbourhood
triangles for each triangle. If the points p1 lies near the next point p2,
which will be the case when scanning the region e.g. for drawing a graphic
picture of the FEM solution, p2 will be found in one of the neighbour
triangles, and only about 10 triangles need be tested.
If the points are independent of each other, this won't work. Hashing of some
sort may be feasible. Does anyone know whether this can be done?
Of course the problem doesn't get less interesting when three and more-
dimensional regions are considered, as well as other shapes than triangles.
Arndt Jonasson
--------------------------------------------
UUCP: {decvax,philabs}!mcvax!enea!ttds!arndt