CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Terms of use
Privacy Policy

Interactive Activities

Cut The Knot!
MSET99 Talk
Games & Puzzles
Arithmetic/Algebra
Geometry
Probability
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
My Logo
Math Poll
Other Math sites
Guest book
News sites

Recommend this site

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Products to download and subscription Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

CTK Exchange

Subject: "Triangle's smallest bounding circle"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange This and that Topic #593
Reading Topic #593
CliveT
Member since Mar-18-05
Mar-21-05, 02:27 PM (EST)
Click to EMail CliveT Click to send private message to CliveT Click to view user profileClick to add this user to your buddy list  
"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 mid-point 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.cut-the-knot.org/htdocs/dcforum/User_files/423f18b931e345b4.gif

  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top

  Subject     Author     Message Date     ID  
Triangle's smallest bounding circle CliveT Mar-21-05 TOP
  RE: Triangle's smallest bounding circle alexb Mar-22-05 1
  RE: Triangle's smallest bounding circle Mark Huber Mar-22-05 2
     RE: Triangle's smallest bounding circle CliveT Mar-22-05 3
         RE: Triangle's smallest bounding circle alexb Mar-22-05 4
             RE: Triangle's smallest bounding circle CliveT Mar-22-05 6
             RE: Triangle's smallest bounding circle CliveT Mar-22-05 7
                 RE: Triangle's smallest bounding circle alexb Mar-22-05 8
                     RE: Triangle's smallest bounding circle CliveT Mar-23-05 9
         RE: Triangle's smallest bounding circle CliveT Mar-22-05 5
             RE: Triangle's smallest bounding circle alexb Mar-24-05 10
  RE: Triangle's smallest bounding circle neat_maths Apr-29-05 11
     RE: Triangle's smallest bounding circle alexb Apr-29-05 12
  RE: Triangle's smallest bounding circle moffitt Sep-14-05 13
     RE: Triangle's smallest bounding circle alexb Sep-17-05 14

Conferences | Forums | Topics | Previous Topic | Next Topic
alexb
Charter Member
2286 posts
Mar-22-05, 01:32 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Reply | Reply With Quote | Top
Mark Huber
guest
Mar-22-05, 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 mid-point 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 Printer-friendly page | Reply | Reply With Quote | Top
CliveT
Member since Mar-18-05
Mar-22-05, 09:25 PM (EST)
Click to EMail CliveT Click to send private message to CliveT Click to view user profileClick to add this user to your buddy list  
3. "RE: Triangle's smallest bounding circle"
In response to message #2
 
   Alex and Mark - thank you both for your reply - may I impose upon your synapses a little further please..?

If I have an isosceles triangle with the unique angle somewhere between 90 and 60 degrees, would that imply that the centre of the smallest bounding circle is positioned somewhere between the mid-hypotenuse and equilateral-centre points?


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2286 posts
Mar-22-05, 09:28 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
4. "RE: Triangle's smallest bounding circle"
In response to message #3
 
   I am completely at a loss as to what you mean by

1. mid-hypotenuse
2. equilateral-centre point


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
CliveT
Member since Mar-18-05
Mar-22-05, 11:43 PM (EST)
Click to EMail CliveT Click to send private message to CliveT Click to view user profileClick to add this user to your buddy list  
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. mid-hypotenuse
>2. equilateral-centre 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 mid-point 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 Printer-friendly page | Reply | Reply With Quote | Top
CliveT
Member since Mar-18-05
Mar-22-05, 11:43 PM (EST)
Click to EMail CliveT Click to send private message to CliveT Click to view user profileClick to add this user to your buddy list  
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.cut-the-knot.org/htdocs/dcforum/User_files/4240f16f784ce10f.gif

  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2286 posts
Mar-22-05, 11:55 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
8. "RE: Triangle's smallest bounding circle"
In response to message #7
 
   >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...

No, it's either one or the other. In case of an acute angle (e.g., an isosceles triangle with the top vertex angle between 90 and 60), the circumcircle is the smallest circle.

To show that, assume there is a circle that contains all three vertices of a given triangle in its interior or boundary. If the three lie on the circle, it's the circumcircle. If all three lie in the interior, the circle can be shrunk a little and still contain the three points. So it can't be minimal. If only one or two of them lie in the interior, you can shift the circle a little to make all three vertices lie in the interior. So that in this case too, the circle is not minimal.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
CliveT
Member since Mar-18-05
Mar-23-05, 08:49 AM (EST)
Click to EMail CliveT Click to send private message to CliveT Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Reply | Reply With Quote | Top
CliveT
Member since Mar-18-05
Mar-22-05, 10:46 PM (EST)
Click to EMail CliveT Click to send private message to CliveT Click to view user profileClick to add this user to your buddy list  
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 co-ordinates 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 sphere-centre was more than the sphere-radius from the line.

Sometimes the line would pass through the sphere without actually touching the triangle, and I'd have to do all the line-intersecting-plane and point-outside-triangle 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 un-needed 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 Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2286 posts
Mar-24-05, 10:47 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
10. "RE: Triangle's smallest bounding circle"
In response to message #5
 
   Thank you for the writeup. I may use it, if you do not mid of course, in a future collection on uses of mathematics.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
neat_maths
Member since Aug-22-03
Apr-29-05, 08:45 PM (EST)
Click to EMail neat_maths Click to send private message to neat_maths Click to view user profileClick to add this user to your buddy list  
11. "RE: Triangle's smallest bounding circle"
In response to message #0
 
   What we have here is a circumcircle
See http://mathworld.wolfram.com/Circumcircle.html

take care
kind regards
JB


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2286 posts
Apr-29-05, 08:46 PM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
12. "RE: Triangle's smallest bounding circle"
In response to message #11
 
   >What we have here is a circumcircle

Not for an obtuse triangle. Read the thread.


  Alert | IP Printer-friendly page | Reply | Reply With Quote | Top
moffitt
guest
Sep-14-05, 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 Printer-friendly page | Reply | Reply With Quote | Top
alexb
Charter Member
2286 posts
Sep-17-05, 08:58 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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 Printer-friendly page | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to have a look at the old CTK Exchange archive.
Please do not post there.

|Store|

Copyright © 1996-2017 Alexander Bogomolny

Search:
Keywords:

Google
Web CTK