From: Hans-Bernhard B. <HBB...@t-...> - 2010-12-12 18:22:57
|
On 12.12.2010 16:51, Alexandre Felipe wrote: > Find all the triangle pairs for wich the nearest vertex of firstis > nearer than the farthest of the vertexes of the second triangle, and the > farthest vertex of first is farther than the nearest of the vertexes of > the second triangle. [...] You've pretty much re-invented the Newell-Newell-Sancha algorithm that I've mentioned before, except that their textbook algorithm doesn't split the job into two passes (first splitting, second sorting) like you did. That avoids a good deal of unnecessary splitting. > After proceeding in this way you can use any criteria to sort the > triangles, i think this is the minimal algorithm, it takes about 1 days > to be coded ant two or three to get working :D If only. You would be amazed at the kind of precision problems you'll run into with this algorithm in practice. Just for starters, consider what all those tests will do with a pair of triangles that just so happen to share a vertex, or an edge. |