CGAL users discussion list

[Stephen Sintay <>]

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