Oops... I forgot. This is the link to the lib: http://www.partow.net/projects/fastgeo/index.html
pakachunka <[EMAIL PROTECTED]> wrote: In my case "mesh" means an irregular set of triangles (different size , format and orientation) that don't overlap. The "mesh" is defined by a list of vertices and a list of connectivity between vertices. The problem is how to find which triangle contains a given point (x,y), but I will later implement this code in a microcontroller with very limited processing capability, and I need to find the triangle very quick in a list of perhaps 50 triangles. Very quick means real time, for interaction with humans that move the point (x,y) through the mesh with a stylus (like a pen). Perhaps an R-Tree may be the solution, but it seems too complicated for me. Neverthless, you code may be useful. If you want more details about what we are doing, let me know. Pakachunka --- In advanced_delphi@yahoogroups.com, Rich _ <[EMAIL PROTECTED]> wrote: > > You can find out if a given Point(X, Y) is in a polygon (these routines require that only three points exist) and I would think you can use that for triangles. If "mesh" means the triangles don't overlap then you can exit the search when you find the first hit. If the triangle can overlap then you'll either need a z-order to know the top most triangle or you can return a list of triangles that contain the point. > > If this sounds like what you need, let me know and I can probably get you the code. > > Jeremy Grand <[EMAIL PROTECTED]> wrote: There is a technique for knowing whether you're inside or outside a rectilinear figure. I don't know the name, but it involves finding the equation of a line that intersects any one of the sides of the figure, then finding how many times the ray beginning at your target point intersects a boundary. And then you do have to deal with points that are on a vertex. > > One might hope that working with triangles would provide some simplifying conditions, but they don't occur to me. Consider the triangle with vertices (0,5), (2,0), (3,3). Is the point (1,1) inside or outside? Depends on the slope of the closest edge I think. > > Jeremy > > -----Original Message----- > From: advanced_delphi@yahoogroups.com on behalf of pakachunka > Sent: Sun 3/23/2008 1:52 PM > To: advanced_delphi@yahoogroups.com > Subject: [advanced_delphi] Re: How to find to which triangle a given point (x,y) belongs in a 2D MESH? > > Hello, > > Description of my problem: > > Suppose you have a mesh defined by a list of vertices and a list of > connectivity between vertices. Now I provide you with a point (u,v) > and I ask you to which triangle this point belongs. > > I need to do this very efficiently, because after prototyping the > solution in Delphi (or Kylix), I will implement it in a > microcontroller. > > I had this initial idea of sorting the points, but I can´t figure > out what would be a good rule to determine which point comes before > another. It is hard to determine an order for (u1,v1), (u2,v2) etc. > > From another list I am participating, I Thomas mentioned using > Bounding Rects, but I am not sure about what to do. > > Note that the mesh is irregular, that is, triangles change in size, > format and orientation. > > Regards, > > Pakachunka > > --- In advanced_delphi@yahoogroups.com, "Jeremy Grand" <jeremy@> > wrote: > > > > Sounds interesting. How is the mesh embodied? Array in memory? > Set of > > rules? In other words, what exactly are we searching? > > > > ________________________________ > > > > From: advanced_delphi@yahoogroups.com > > [mailto:[EMAIL PROTECTED] On Behalf Of pakachunka > > Sent: Friday, March 21, 2008 4:41 PM > > To: advanced_delphi@yahoogroups.com > > Subject: [advanced_delphi] How to find to which triangle a given > point > > (x,y) belongs in a 2D MESH? > > > > > > > > I need some help to select the algorithm to be implemented Delphi > or > > Kylix. > > > > I have to find to which triangle in a 2D Mesh a selected point > belongs. > > > > I need to find this very quickly, since my code will be running as > the > > firmware of a Microcontroller (PIC, Cyrix, whatever). > > > > So I need a very quick search algorithm to scan the mesh in order > to > > determine to which triangle given point (x,y) belongs. > > > > Can you help me? > > > > > > > > > --------------------------------- > Be a better friend, newshound, and know-it-all with Yahoo! Mobile. Try it now. > --------------------------------- You rock. That's why Blockbuster's offering you one month of Blockbuster Total Access, No Cost.
