CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Dear Marc,

I think such a weight does not always exist.

Implementation wise, I would do the following:
a) locate the cell containing the point to be inserted
b) Use the power test (Power_side_of_oriented_power_sphere_3) with the 4 
points of the cell to check if the new point is hidden
c) if it is, go back to the definition of the power test and get the 
minimal weight so that the point is orthogonal to the power sphere of 
the cell (note that you'll have to resort to exact arithmetic if you 
want an exact value and then take approx(w).sup() if you want to go
back to the floating point world)
d) together with your minimal weight, call find_conflict(). If there
is a vertex that is surrounded by cells in conflict then the new point
will hide a previously inserted point. If not, you can get the upper
bound by considering the cells incident to the current region in
conflict (but not in that region) and use the definition of the power
test to get for each such cell the maximum value of the weight until the 
point is orthogonal to the power sphere of that cell.


You of course have to handle the case when the dimension is not 3 and 
when the point fall outside the convex hull (which simply mean that the
minimal weight is 0).

HTH,

Sebastien.

On 1/7/20 7:18 PM, Marc Alexa wrote:
> Dear all,
>
> I want to insert a point p into a regular triangulation. The point has a 
> fixed coordinate. I am interested in the interval of weights so that the 
> point itself appears in the triangulation and none of the existing points 
> disappears. The upper bound (the point appears) is easy: find the cell the 
> contains p. The cell defines a hyperplane in the lift, and the lift for p 
> needs to be below the hyperplane. What methods are available in CGAL that 
> would help me finding the lower bound? Moreover, is there an easy way to walk 
> through all triangulations in this interval, perhaps parameterized by the 
> weight?
>
> Thanks!
> -Marc