**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