Re: The largest Inscribed Circle in a Polygon
 From: ellieandrogerxyzzy@xxxxxxxxxxxxxxxxxxxxxx (Roger Stafford)
 Date: Sun, 18 Mar 2007 03:17:53 GMT
In article <ef50c93.1@xxxxxxxxxxxxxxxxxxxxxxx>, "Frank Mielsen"
<frank230458@xxxxxxxx> wrote:
Can anyone here help me or point me to where I can find a mfile with
code to calculate the largest Inscribed Circle in a Polygon?
Thanks in advance
A few questions. 1) Is this a convex polygon? Otherwise this would be
a quite difficult problem. 2) When you say "inscribed circle", do you
require the circle to necessarily be tangent to each polygon side? 3) Do
you require that the polygon not cross into the interior of the circle at
any point (surely you do)? 4) Are you concerned with execution time, or
is an order n^3 algorithm satisfactory?
Assuming your answers are 1) yes, 2) no, 3) yes, and 4) O(n^3) is okay,
I can think of a method that tests each possible combination of three
sides, giving an order n^3 algorithm for a polygon with n sides. With a
large number of sides it would take a long time to execute.
Unfortunately, that's the best I have come up with at this point. There
are very likely people in this field who can do much better than this.
However, I'll describe this idea for what it's worth.
Suppose a, b, and c are any three not necessarily adjacent sides of the
polygon. In general we can extend these sides to form a triangle. If
that triangle lies entirely outside the polygon (that is, lies on the
wrong side of one of the sides,) we abandon the triple of sides, but
otherwise it is possible to compute the radius of the inscribed circle in
the triangle in terms of the six endpoints of the three polygon sides.
There are just two possibilities. Either the polygon crosses this circle
or it doesn't. If it doesn't, this must be the circle you seek  there
can be no larger circle lying within the polygon because it must also lie
within this triangle. If it does cross, that implies that whatever the
largest inscribed circle in the polygon is, it must have a smaller radius
than this one  any other circle within the triangle must be a smaller
one. Therefore you search for the circle with the smallest such radius
among all triples of the polygon's sides and that will be your largest
inscribed circle. You don't need to actually test whether the polygon
crosses the circle as you try out various triples. If the radius is the
smallest one, you are assured that this can't happen.
The formula for the radius of the inscribed circle of a triangle in
terms of endpoints of segments within the three triangle sides is a fairly
straightforward formula, but I won't attempt to give it at this point,
since I don't know for sure that my assumptions about the above four
questions are justified.
There is one aspect of this problem that puzzles me. This question is
really not, properly speaking, a matlab question but rather one in
computational geometry. That is, it is a problem in algorithms involving
geometrical concepts and formulas, not one of making use of efficient
matlab techniques. Why is it you have chosen to pose it to this
newsgroup? Are you working with some application which uses matlab?
Roger Stafford
.
 References:
 The largest Inscribed Circle in a Polygon
 From: Frank Mielsen
 The largest Inscribed Circle in a Polygon
 Prev by Date: finding the index of the row of a line of text
 Next by Date: Re: finding the index of the row of a line of text
 Previous by thread: Re: The largest Inscribed Circle in a Polygon
 Next by thread: How to setup a web server running a Matlab program and let people upload input data
 Index(es):
Relevant Pages
