CGAL users discussion list

[Atul Thakur <>]

Yes.

Actually, as Bernd pointed out my 1st constraint is not right.

It should be replaced by n different constraints as
R^2 - sq_dist(Triangle(x_j1, x_j2, x_j3), P_center)>= 0

where, n is number of facets,
x_j1, x_j2, x_j3 are vertices of j'th triangle.

which makes it 4 variable and n+7 constraints and needs to be solved n times 
:(


-Atul


On Thu, Dec 3, 2009 at 4:25 PM, Stephen Sintay 
<>
 wrote:
> 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
>>>>
>>>
>>
>
>