Convex hull for circles

> > Hi Everyone ....can somebody please help me get the

> > code in any language to find the convex hull of

> > circles of same radii.

You'll have to discretize the circles and then use

Graham's scan or any other algorithm for finding

the convex hull of the discretized points.

javafora@gmail.coma at 2007-7-9 6:15:14 >

> could you please be more specific. what do you mean

> by discretize?

discretize:

http://www.webopedia.com/TERM/D/discretize.html

> will i be able to get a code from

> somewhere? I went through many papers and it just

> says...It is same as that of points ....and can be

> obtained by growing faces of convex hull of centers.

> I understood the meaning of it but i donot know how

> those changes can be made programatically. My centers

> are represented as (x,y) and radius r. Please help

> me....

Do you understand the Graham Scan when working with points?

If so, in what way does it differ from getting a convex hull from a set of circles whose radii are the same?

prometheuzza at 2007-7-9 6:15:14 >

All this talk about convex hulls of circles, and how the hulls will have portions of circular arcs and not one person has asked, Why?

So forgive me for asking, but why? Other than as an exercise in computational geometry, why do you need a convex hull of a bunch of circles. True, knowing what you are using it for won't change the answer but since you seem to be mystified by why or even how you can use any standard hull algorithm, please humor me and tell me why.

The reason you can use any standard hull algorithm with a set of circles of constant radius is this.

Run any old convex hull algorithm on the centers of your circles. This gives you a polygon. The polygon connects between the centers of some of the circles. That is almost the hull of all the circles. All you need to do now is to "push" each edge outward i.e. translate it by a distance r in the direction that is perpendicular to the edge itself.

Pushing the edges outward disconnects every vertex on the original polygon. The edges must be reconnected by a little portion of a circular arc of radius r that is centered at the vertex that you broke.

So there you go. You need to create some disgusting path thing that holds both line segments and arc segments to hold the results of your hull of circles. Now why on earth would you need such a thing? What are you going to do with it, now that you got it?

marlin314a at 2007-7-9 6:15:14 >

Hey guys...thanks a million for all ur suggestions. I'm was actually stuck in drawing a boundary for a set of circles. Through convex hull i'm am getting sharp edges...so i thought i take tangents of two circles and join the points of tangency.....but here i need to drop a perpendicular as tangents are perpendicular to the original line. I dont have a method to find the point to where the perpendicular is drawn.....if you guys could help me out with that....then that'll be wonderful.

sujjyoa at 2007-7-9 6:15:14 >