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/
