Finding the maximum inscribed circle in C#

  • Thread starter Thread starter marc.selman
  • Start date Start date
M

marc.selman

Is there anyone who has or know how to implement an algorithm to find
the maximum inscribed circle in C# (or maybe Java, VB etc.) code?

I've been looking for this a long time and stil have not found
anything.
I'm not familiar with the math enough to do it myself.

Thank you,
Marc Selman
 
Hi,
are you looking to find it for quadrilaterals like square, rectangle or it
could be anything like a star, a pentagone or any polygon?

if it's for quadrilaterals, you can try to find the smallest width you have
available and then draw your circle into that... well I can't draw something
in ascii, but if you have a rectangle with 30px width and 20px height, the
center of your circle will be at (15,10) and the radius of your circle will
be of 10px.

if it's for any polygons, you'll have to divide your polygon to sub polygons
to find the most optimal placement.

that's as far as I can go...

good luck

ThunderMusic
 
Hi,
Actually, you should probably go to www.gamedev.net... they are game
oriented, but they have a forum specificaly for Maths, so there is probably
someone who know the answer to your problem there... ;)

I hope it helps

ThunderMusic
 
Your problem is not trivial, and there is no C# code that does this straight
out of the box. You will have to write your own. I found the problem
intriguing, and did some research, so here are a few clues that may help.

First, here's an answer in "plain English" from mathforum.org:

http://mathforum.org/library/drmath/view/67030.html

The answer references Voronoi Diagrams as a methodology for making the
process more efficient. In researching Voronoi diagrams, in conjunction with
the "maximum empty circle" problem (same problem, different name), I came
across this informative paper:

http://www.cosy.sbg.ac.at/~held/teaching/compgeo/slides/vd_slides.pdf

It was written by Martin Held, a Computational Geometry professor at the
University of Salzberg in Austria. Further investigation of Dr. Held's
writings yielded a couple of good articles:

http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html
http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

Further research into Vornoi Diagrams yielded the following site:

http://www.voronoi.com/

This site has lots of information, code in various languages, and links to
other resources.

Finally, here is the URL to the Mathematics and Computational Sciences
Division of the National Institute of Standards and Technology (U.S.), a
wealth of information and links regarding mathematics of all sorts:

http://math.nist.gov/mcsd/

--
HTH,

Kevin Spencer
Microsoft MVP

Printing Components, Email Components,
FTP Client Classes, Enhanced Data Controls, much more.
DSI PrintManager, Miradyne Component Libraries:
http://www.miradyne.net


This includes functionality for creating triangulated Voronoi Diagrams from
a set of points.
 
Back
Top