Hey Thomas, thank you! The idea of pre-sorting is very good, specially because I have a known number of triangles from start, so I can do a optimized search tree.
However, I forgot to say that my mesh is not regular, that is, the size and orientation of the triangles vary. So, when you say sort the points, what do you mean? Sort by the distance to (x=0, y=0) calculated by pitagoras? Make two sorted lists, one for x and another one for y? But them the triangle vertice found in list X may not be the same found in list Y, right? Thanks Tor --- In [email protected], Thomas Hruska <[EMAIL PROTECTED]> wrote: > > pakachunka wrote: > > Hello! > > > > Suppose I have a 2D Mesh Data Structure already set. > > > > I need to determine which triangle in the 2D mesh contains a given > > point (x,y). > > > > I need to do that very quick, since I will implement my code on a Risc > > Microcontroller, with very limited processing capabilities and very > > limited memory. > > > > Can you suggest some efficient algorithm for that? > > > > Thank you! > > Possible ideas: > > - Sort the points of each triangle in the mesh. > - "Rectangles" would make a quick exclusion mechanism. > - Adjacent points will only need to consider current and adjacent > "rectangles" on the next iteration. > > Storage limitations do make things interesting. Sorting points (and the > triangles themselves?) is an excellent start. You may be able to figure > something out by just doing that. > > -- > Thomas Hruska > CubicleSoft President > Ph: 517-803-4197 > > *NEW* MyTaskFocus 1.1 > Get on task. Stay on task. > > http://www.CubicleSoft.com/MyTaskFocus/ >
