## Re: [Algorithms] Distance between box and triangle

 Re: [Algorithms] Distance between box and triangle From: Paul_F - 2004-11-29 16:37:09 ```gdalgorithms-list-admin@... wrote on 29/11/2004 16:12:47: > Have you looked at Minkowski sums? I used to have a really good web link for > graphical examples using Java but have since lost it. :( I'm sure it came > from this list though. I have a page at http://www.pfirth.co.uk/collision.html and http://www.pfirth.co.uk/minkowski.html which might be of use... :-) If you only want positive distance, GJK will be the fastest way to compute this. Probably. If not, you could either explicitly form the MD from the two shapes and take the minimum from the origin to each face of the MD as the minimum distance between the two, or you could use Gino van den Bergen's EPA algorithm (which is similar to GJK and takes the output of GJK as its input). Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe ```

 [Algorithms] Distance between box and triangle From: Andreas.B - 2004-11-29 15:54:20 ```Hi, does anyone know where I can find code that computes the distance between a box and a triangle. I was first thinking about extending David Eberly's rectangle to triangle distance code, but I think the original code is too long as it is (every case written out explicitely). I'm also thinking about formulating the problem as a quadtratic programming problem with constraints but haven't been able to find a small free solver that is easy to integrate into my code. Any pointers would be much appreciated. /A.B. ########################################### This message has been scanned by F-Secure Anti-Virus for Microsoft Exchange. For more information, connect to http://www.F-Secure.com/ ```
 Re: [Algorithms] Distance between box and triangle From: Martin Piper - 2004-11-29 16:08:55 ```Have you looked at Minkowski sums? I used to have a really good web link for graphical examples using Java but have since lost it. :( I'm sure it came from this list though. Martin Piper http://www.ReplicaNet.com - Network middleware powering games. ----- Original Message ----- From: To: Sent: Monday, November 29, 2004 3:54 PM Subject: [Algorithms] Distance between box and triangle > Hi, > > does anyone know where I can find code that computes the distance between a > box and a triangle. I was first thinking about extending David Eberly's > rectangle to triangle distance code, but I think the original code is too > long as it is (every case written out explicitely). I'm also thinking about > formulating the problem as a quadtratic programming problem with constraints > but haven't been able to find a small free solver that is easy to integrate > into my code. Any pointers would be much appreciated. > > /A.B. > ########################################### > > This message has been scanned by F-Secure Anti-Virus for Microsoft Exchange. > For more information, connect to http://www.F-Secure.com/ > > > ------------------------------------------------------- > SF email is sponsored by - The IT Product Guide > Read honest & candid reviews on hundreds of IT Products from real users. > Discover which products truly live up to the hype. Start reading now. > http://productguide.itmanagersjournal.com/ > _______________________________________________ > GDAlgorithms-list mailing list > GDAlgorithms-list@... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_id=6188 ```
 Re: [Algorithms] Distance between box and triangle From: Paul_F - 2004-11-29 16:37:09 ```gdalgorithms-list-admin@... wrote on 29/11/2004 16:12:47: > Have you looked at Minkowski sums? I used to have a really good web link for > graphical examples using Java but have since lost it. :( I'm sure it came > from this list though. I have a page at http://www.pfirth.co.uk/collision.html and http://www.pfirth.co.uk/minkowski.html which might be of use... :-) If you only want positive distance, GJK will be the fastest way to compute this. Probably. If not, you could either explicitly form the MD from the two shapes and take the minimum from the origin to each face of the MD as the minimum distance between the two, or you could use Gino van den Bergen's EPA algorithm (which is similar to GJK and takes the output of GJK as its input). Cheers, Paul. ********************************************************************** This email and any files transmitted with it are confidential and intended solely for the use of the individual or entity to whom they are addressed. If you have received this email in error please notify postmaster@... This footnote also confirms that this email message has been checked for all known viruses. ********************************************************************** Sony Computer Entertainment Europe ```
 Re: [Algorithms] Distance between box and triangle From: - 2004-11-29 18:59:08 Attachments: Message as HTML ```Andreas Brinck skrev: > does anyone know where I can find code that computes the distance=20 between a > box and a triangle. I was first thinking about extending David Eberly's > rectangle to triangle distance code, but I think the original code is=20 too > long as it is (every case written out explicitely). I'm also thinking=20 about > formulating the problem as a quadtratic programming problem with=20 constraints > but haven't been able to find a small free solver that is easy to=20 integrate > into my code. Any pointers would be much appreciated. I'm not aware of any small freely-available QP solvers, but if you are willing to implement them from scratch, the most promising ones for small problems seem to be the randomized algorithms of G=E4rtner and of Botkin. As others have mentioned, the GJK algorithm will give you the result you need, and there's code available for it. You can also implement it in terms of simpler primitives by recognizing that (for non-intersecting primitives) the closest points must be a vertex, on an edge or on a face of each primitive. You then write tests for all feature pairs, picking the pair of points giving the globally smallest distance. Trivially you can reduce this to triangle- triangle distance computations, but those are sort of expensive in themselves. However, if you look at all feature-feature tests, there are certain tests that are not needed, such as face-face tests (which are subsumed by others). In your case I would probably go for GJK, because its pretty fast and code already exists. Christer Ericson Sony Computer Entertainment, Santa Monica ```