Implementation

 

Home Introduction Algorithm Implementation References



Input: given a convex polygon P(P1, P2, ..., Pn) on the halfsphere with the radius R at the point O(x0, y0, z0).

Output: the largest inscribed circle in P.


1. Compute h1, h2, ..., hn, determined by edges of P and O(x0, y0, z0).

2. Compute normal vectors V1, V2, ..., Vn to h1, h2, ..., hn.

3. Compute lines l1,l2,..., ln , determined by O(x0, y0, z0) and V1, V2, ..., Vn .

4. Compute points Q(Q1, Q2, ..., Qn) as the intersection of l1,l2,..., ln with the sphere.

5. Compute planes h'1, h'2, ..., h'n tangent to the sphere at points Q(Q1, Q2, ..., Qn) .

6. Compute the vertex K of the polyhedral region as the intersection of h'1, h'2, ..., h'n .

7. Compute the line l0 , determined by K(xk, yk, zk) and O(x0, y0, z0) .

8. Compute the center of the minimum circle Cmin containing Q(Q1, Q2, ...,Qn) .

9. Compute the largest inscribed circle Cmax by using the relation between the aperture angles of the cone defined by Cmax , O(x0, y0, z0) and the polar cone defined by Cmin , O(x0, y0, z0)



The following applet demonstrates inscribing the largest circle in the convex polygon. Since the parameters of drawing methods should be integer, there is a mistake of rounding in drawing this circle. The given convex polygon and its largest inscribed circle are red. The polar polygon and its minimum spanning circle are green. The vertex of the polyhedral intersection region is yellow. The sphere is rotated by some angle such that the polygons may be seen. That is why the largest inscribed and minimum spanning circles are transformed into the ellipses.


Your browser does not support Java.
The source code is available.


USEFUL LINKS

1. CS 507 HomePage

2. General Links - Computational Geometry