Re: The largest Inscribed Circle in a Polygon

In article <ef50c93.-1@xxxxxxxxxxxxxxxxxxxxxxx>, "Frank Mielsen"
<frank230458@xxxxxxxx> wrote:

Can anyone here help me or point me to where I can find a m-file 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

Relevant Pages

  • [LogoForum] Re: Help - Beginner!
    ... How would you use `polygon' to make a circle? ... Points' can the mathematical notion of a circle be made from ... make the triangle and square shapes you requested. ...
  • Re: Church-Turing compared to Zuse-Fredkin thesis (two new papers)
    ... >Maybe higher roots can be broken down into square and cube. ... They quit teaching square root by hand in the 1960s in the ... >of 180,000 sides containing the unit circle, each side is very ... >of the polygon are virtually indistinguishable. ...
  • ANN: FastGEO Computational Geometry Library
    ... * 2D/3D Segment intersection point calculation ... * 2D/3D Triangle, quadix, rectangle, circle and polygon perimeter ... * Closest point on segment from a point ...
  • Re: History of trigonometry
    ... except a triangle's interior angle is 1pi ... So, for example, for a polygon of 100 ... its exterior angle is 198 pi. ... radian is the arc length subtended by the angle, of the unit circle. ...
  • Re: conformal map regular polygone into unit circle.
    ... > maps the unit circle into a REGULAR polygon ... > way too complex to be integrated (I'm trying to find the mapping for a ... > circle in the S-C transform because out of the symmetry of the problem, ... they should also be on a regular polygon. ...