







CTK Exchange
CliveT
Member since Mar1805

Mar2105, 02:27 PM (EST) 

"Triangle's smallest bounding circle"

Hi everyone. A few years ago I was faced with the problem of having to find the smallest possible circle which would enclose a triangle. I know that by bisecting the sides and drawing lines through these midpoints you are able to find the centre of a circle which touches all 3 corners. This seems ok for some triangles (figure 1) but is quite wasteful for others (figure 2). With some it's better to take the midpoint of the longest line and use that as the centre of the circle (figure 3). So, how do I decide which method to use? Or is there a method better than both? This problem has bugged me for years  any ideas would be most appreciated!

Attachments
http://www.cuttheknot.org/htdocs/dcforum/User_files/423f18b931e345b4.gif

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


alexb
Charter Member
2286 posts 
Mar2205, 01:32 PM (EST) 

1. "RE: Triangle's smallest bounding circle"
In response to message #0

For acute triangles, i.e. for triangles with all three angles acute, the circumcircle is the smallest among enclosing the triangle. If one of the angle is obtuse, then the smallest enclosing circle is the one with the logest side as diameter. It's all exactly as you described. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 


Mark Huber
guest

Mar2205, 02:03 PM (EST) 

2. "RE: Triangle's smallest bounding circle"
In response to message #0

>A few years ago I was faced with the problem of having to >find the smallest possible circle which would enclose a >triangle. > >I know that by bisecting the sides and drawing lines through >these midpoints you are able to find the centre of a circle >which touches all 3 corners. >This seems ok for some triangles (figure 1) but is quite >wasteful for others (figure 2). With some it's better to >take the midpoint of the longest line and use that as the >centre of the circle (figure 3). > >So, how do I decide which method to use? >Or is there a method better than both? When one of the angles of a triangle is obtuse, one of the sides of the triangle will be greater in length that the other two. Making this side the diameter of the circle gives the smallest circle that contains it. When you have an acute triangle (so all angles are less than 90 degrees) then the method you described above using the circle that touches all three vertices gives the smallest circle. The proof of these facts is not too difficult, but is not trivial by any means. Mark Huber 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 







CliveT
Member since Mar1805

Mar2205, 11:43 PM (EST) 

6. "RE: Triangle's smallest bounding circle"
In response to message #4

>I am completely at a loss as to what you mean by > >1. midhypotenuse >2. equilateralcentre point Sorry  I think I should have said 'base' instead of hypotenuse. I'm picturing a triangle with a horizontal base and a point at the top. By 1. I meant the centre of the circle chosen by taking the midpoint of the base. By 2. I meant the centre of the circle which touches all three corners. I can understand that if all angles were 60 degrees then the smallest circle would be the one touching all 3 corners. I can understand that if one angle increased to 90 degrees then it would then be touching a circle whose centre was the midpoint of the line opposite it. But I suspect that there are times when the 'smallest bounding circle' has it's centre somewhere between centres 1 and 2. I apologise for my struggle to explain this  happy to draw more pictures if it will help decipher my ramblings... 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




CliveT
Member since Mar1805

Mar2205, 11:43 PM (EST) 

7. "RE: Triangle's smallest bounding circle"
In response to message #4

Hi again Alex, thanks for taking the time to help with this. I've enclosed a picture which will hopefully help. In figure 1 I can work out the centre of the smallest bounding circle by bisecting the triangle's sides. In figure 2 (with the triangle having the same base) I know that the requred circle's centre is at the midpoint of the base. I understand why this applies to any angle greater than 90 degrees too. My confusion lies in the situation where the angle is between 60 and 90 degrees. My intuition suggests that the centre of the smallest circle would be somewhere between the previously found centres... 
Attachments
http://www.cuttheknot.org/htdocs/dcforum/User_files/4240f16f784ce10f.gif

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




CliveT
Member since Mar1805

Mar2305, 08:49 AM (EST) 

9. "RE: Triangle's smallest bounding circle"
In response to message #8

Alex, you've just activated the part of my brain which was rudely not joining in when I looked at this problem before. I see that the centre in figure 3 IS closer to the base, but more importantly IS STILL the centre of the circumcircle. It gets closer as the angle reaches 90 degrees and then the centre leaves the triangle, at which point the circle can only get bigger. Your descriptive explanation has enabled me to see that it does work, and  more valuably  why it works. Many thanks indeed. 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 




CliveT
Member since Mar1805

Mar2205, 10:46 PM (EST) 

5. "RE: Triangle's smallest bounding circle"
In response to message #3

P.S. Just wanted to explain how I was first introduced to this problem. It doesn't change the question, but may be of interest to show how a small improvement in method can have important results.I'm a programmer of computer games, and quite often need to decide whether a laser beam has hit a player, whether an enemy can 'see' you, and many other situations requiring the computer to draw a line between two points and decide whether or not the line passes through a wall or other scenery. In most 3D games the 'world' consists of areas and objects made from triangles, although these days computers are powerful enough to draw so many triangles that a surface made from them can look quite curved. Clever lighting can make this smoothness even more realistic, but even so they are still usually made from triangles. To test whether a line segment passes through every single triangle in a scene would be wasteful, so every opportunity is taken to reject ones which are 'nowhere near' the line. Don't test the line against enemies or objects in a different room, for example. And divide your landscape into chunks and only test against the chunks that the line passes through. Store the coordinates of a sphere which encloses an object and see if the line passes through the sphere  if it doesn't then you don't need to test against any of the object's triangles. Etc. Once you've rejected as many triangles as possible, you then have to do some more serious calculation. For each triangle you need to find the point where the line intersects the plane of the triangle. You then have to find out whether this point is inside the triangle or not. This issue is discussed in Irina Mikheeva's archive question entitled 'Point inside a triangle'. As Alexander wisely pointed out, to save computation time we stored the formulae for each side and used them to test whether the point was inside the triangle or not. (As the triangle was at an arbitry 3D angle, we actually stored the formulae for the planes passing through each edge and perpendicular to the plane). To speed things up, I also wanted to reject triangles that were far enough away from the line to be irrelevant. By storing a bounding sphere for each triangle (computer memory wasn't an issue) I was able to discard triangles whose spherecentre was more than the sphereradius from the line. Sometimes the line would pass through the sphere without actually touching the triangle, and I'd have to do all the lineintersectingplane and pointoutsidetriangle calculations for no reason. Making the bounding spere as small as possible (hence my question) it makes this process as efficient as possible. By giving each triangle it's own bounding sphere, we were able to avoid unneeded calculation, and speed up collision testing and screen drawing. With the large amount of graphics we were using, this made the difference between a jerky, unplayable game and a smooth playable one. Result!


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 







moffitt
guest

Sep1405, 03:56 PM (EST) 

13. "RE: Triangle's smallest bounding circle"
In response to message #0

You probably have the answer by now, but seeing as I'm looking at the same problem, I'd mention that to decide which method to use is fairly simple. If the triangle is acute, use the cicumcenter of the triangle (as you defined it). If the triangle is a right triangle, the circumcenter is located at the midpoint of the hypotenuse. In this case, and for all obtuse triangles, the midpoint of the hypotenuse is the way to go. Of course, in 3D space you want to use bounding spheres in lieu of circles. Now I have a question. What is the cheapest way to generate the circumcenter of a triangle? 

Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



alexb
Charter Member
2286 posts 
Sep1705, 08:58 AM (EST) 

14. "RE: Triangle's smallest bounding circle"
In response to message #13

>You probably have the answer by now, but seeing as I'm >looking at the same problem, I'd mention that to decide >which method to use is fairly simple. If the triangle is >acute, use the cicumcenter of the triangle (as you defined >it). Computing the angles may be expensive. Given a circumcenter, if it lies inside the triangle, use it. Otherwise, find the midpoint of the longest side. >If the triangle is a right triangle, the circumcenter >is located at the midpoint of the hypotenuse. In this case, >and for all obtuse triangles, the midpoint of the hypotenuse You mean "the logest side," right? >is the way to go. Of course, in 3D space you want to use >bounding spheres in lieu of circles. > >Now I have a question. What is the cheapest way to generate >the circumcenter of a triangle? The cheapest, in terms of what?


Alert  IP 
Printerfriendly page 
Reply 
Reply With Quote  Top 



You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
Store
Copyright © 19962017 Alexander Bogomolny

