Thank you again Thomas! Is there some text referent to "bounding boxes" I can read? Is there some literature to follow what you are saying?
Just to make you understand better what I am doing: I am making a driver for a new type of low cost tablet for linux. Tablets in general have problems with linearization, so I am creating a way to convert the (u,v) voltages measured by the tablet, into (x,y) position in the screen. For that I need a linearization procedure, during which the user put the tablet stylus over marks in the screen. That is when the mesh of triangles mentioned before are created. After the mesh is ready and set, I use some Conformal Transform to transform the (u,v) voltages into (x,y) positions, based on the mesh. For that I need to determine in which triangle of the mesh the (u,v) voltages are contained. Everything needs to run in a PIC microcontroller. The tablet aims education and will be freeware. Thanks! Tor --- In [email protected], Thomas Hruska <[EMAIL PROTECTED]> wrote: > > pakachunka wrote: > > 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 > > Nope. Here's an example (assume a Cartesian coordinate plane): > > (20, 0), (5, -15), (0, 0) > > Sorting these points top-to-bottom, left-to-right results in: > > (0, 0), (20, 0), (5, -15) > > > That will help to do fast vertical elimination (the first point's y is > guaranteed to be the top, the last point's y is guaranteed to be the > bottom). You may want to add an extra "point" that specifies the min x > and max x values. In other words, creating a virtual rectangle around > each triangle. Also called a "bounding box". > > Each triangle in the mesh should know what its six adjacent neighbors > are to drastically speed up future operations. I assume you are going > to scan horizontally across the display - if you only have to compare > seven bounding boxes instead of hundreds or thousands, that will be a > big performance gain. > > -- > Thomas Hruska > CubicleSoft President > Ph: 517-803-4197 > > *NEW* MyTaskFocus 1.1 > Get on task. Stay on task. > > http://www.CubicleSoft.com/MyTaskFocus/ >
