CGAL users discussion list

[Stephen Sintay <>]

Now that I think about this a little more, I think what you are looking for is the medial axis or skeleton of the polygon. 

The location of the center of all the spheres that satisfy your condition will trace the medial axis or skeleton of the polygon.

On Thu, Dec 3, 2009 at 11:32 AM, Stephen Sintay <> wrote:

Actually "farthest" from will not work...

On Thu, Dec 3, 2009 at 11:30 AM, Stephen Sintay <> wrote:

Can this problem be formulated in another way?

Given two triangular patches, find the largest sphere that is tangent to both.

The solution to this should be a simple as finding a point/line in each patch that is farthest from the other patch. This should be a simple matter of testing the nodes.  

I might try the following:
For each patch, p_i{
  compute the normal n_i
  For each patch p_j
  if( i!=j){
    compute the normal n_j
    if (n_i dot n_j >1 ){
       compute the largest sphere
       compute if any portion of sphere is external to polygon
       If(no external sphere portions){
           if( R_i < R_ij )
             save sphere R_ij as largest for p_i
       } end internal
    } end dot
   } end i!=j
 } end p_j
} end p_i

On Thu, Dec 3, 2009 at 1:09 AM, Bernd Gaertner <> wrote:

Atul Thakur wrote:

A polyhedron (non-convex with triangles as its bounding facets) is
given. For a given facet determine the maximum sized sphere that is
tangential to the facet and contained completely inside the
polyhedron.

[snip]

3. Solve following optimization problem:

Maximize R

S.T.
nR^2 - Sum[(x_j - P_center) dot(x_j - P_center) ] >= 0 (as all points
x_j lying on the polyhedron surface lie outside or on the sphere)
0<alpha, beta, gamma<1
R>0

This optimization problem is no good. A sphere can be penetrating a facet even if it does not has any of the points inside. And by summing up constraints, you will have them satisfied only "on average" but not individually.

Best,
Bernd.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss