Inserting a point into a regular triangulation so that it appears and no other vertex disappears

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Inserting a point into a regular triangulation so that it appears and no other vertex disappears

Marc Alexa
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



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


Reply | Threaded
Open this post in threaded view
|

Re: Inserting a point into a regular triangulation so that it appears and no other vertex disappears

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
>
>
>

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


Reply | Threaded
Open this post in threaded view
|

Re: Inserting a point into a regular triangulation so that it appears and no other vertex disappears

MaelRL
In reply to this post by Marc Alexa
Hello

Here is a translation of an answer by Jean-Daniel Boissonnat in private
correspondence:

 >Considering the usual lifting into R^{d+1} (R^4 here), let p1, ..., pn
be points in R^3 and P1, ..., Pn their lifted equivalent, i.e. Pi = (pi,
pi^2).
 >Let x be the new point, X=(x, x^2), and T the face of the convex hull
conv(P1, ..., Pn) whose projection onto R^3 contains x.

 >The 4th coordinate of the lifted point X (and thus its weight) must be
chosen such that X is below conv(P1, ..., Pn). To ensure that no point
disappears, the new convex hull conv(P1, ..., Pn, X) must have all
points as vertices,
 >in other words X must be above the planes of the faces of convex(P1,
..., Pn) that are adjacent to T.

 > This can be expressed with circumscribing balls in R^3.

As to get the triangulations that appear when moving within this range,
you can probably use a similar reasoning as the combinatorics will
change when an adjacent face is no longer on the convex hull.

There also used to be a package called Kinetic Data Structure in CGAL,
it could handle Regular_triangulation_3 but I am not sure if the kinetic
change had to be the position of a point with a fixed weight, or if you
could also change weights.

Best,
Mael

On 07/01/2020 19:18, 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
>
>
>

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


Reply | Threaded
Open this post in threaded view
|

Re: Inserting a point into a regular triangulation so that it appears and no other vertex disappears

Marc Alexa
Thanks a lot for the answers.

My understanding from the lifting picture is that the point first “appears” when it is connected to the vertices of the cell that contains it (assuming it is inserted inside the convex hull of the points). Then the motion in the lift downwards corresponds to the sequence of flips one would perform in the incremental flipping approaches (Edelsbrunner & Shah, Incremental topological flipping works for regular triangulations). This is nicely explained in the Triangulations book by De Loera, Rambau and Santos, Section 5.3.2. on Monotone paths in the secondary polytope.

So in terms of implementation it would probably suffice if the incremental flipping approach was implemented somewhere in CGAL. But I guess CGAL only uses Bowyer-Watson? Or is there some code somewhere for incremental flipping?

Thanks!-Marc





> On 9. Jan 2020, at 09:34, Mael <[hidden email]> wrote:
>
> Hello
>
> Here is a translation of an answer by Jean-Daniel Boissonnat in private correspondence:
>
> >Considering the usual lifting into R^{d+1} (R^4 here), let p1, ..., pn be points in R^3 and P1, ..., Pn their lifted equivalent, i.e. Pi = (pi, pi^2).
> >Let x be the new point, X=(x, x^2), and T the face of the convex hull conv(P1, ..., Pn) whose projection onto R^3 contains x.
>
> >The 4th coordinate of the lifted point X (and thus its weight) must be chosen such that X is below conv(P1, ..., Pn). To ensure that no point disappears, the new convex hull conv(P1, ..., Pn, X) must have all points as vertices,
> >in other words X must be above the planes of the faces of convex(P1, ..., Pn) that are adjacent to T.
>
> > This can be expressed with circumscribing balls in R^3.
>
> As to get the triangulations that appear when moving within this range, you can probably use a similar reasoning as the combinatorics will change when an adjacent face is no longer on the convex hull.
>
> There also used to be a package called Kinetic Data Structure in CGAL, it could handle Regular_triangulation_3 but I am not sure if the kinetic change had to be the position of a point with a fixed weight, or if you could also change weights.
>
> Best,
> Mael
>
> On 07/01/2020 19:18, 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
>>
>>
>>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://sympa.inria.fr/sympa/info/cgal-discuss
>
>


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


Reply | Threaded
Open this post in threaded view
|

Re: Inserting a point into a regular triangulation so that it appears and no other vertex disappears

MaelRL
Hello,

Although the main code indeed uses Bowyer-Watson, there is some code
about flipping in the packages Triangulation_3 and TDS_3. However, these
are mostly atomatic operations at the base triangulation level, and
there are no complete function doing an insertion in a (weighted)
Delaunay triangulation like there are in the package Triangulation_2.

Best,
Mael

On 14/01/2020 10:05, Marc Alexa wrote:

> Thanks a lot for the answers.
>
> My understanding from the lifting picture is that the point first “appears” when it is connected to the vertices of the cell that contains it (assuming it is inserted inside the convex hull of the points). Then the motion in the lift downwards corresponds to the sequence of flips one would perform in the incremental flipping approaches (Edelsbrunner & Shah, Incremental topological flipping works for regular triangulations). This is nicely explained in the Triangulations book by De Loera, Rambau and Santos, Section 5.3.2. on Monotone paths in the secondary polytope.
>
> So in terms of implementation it would probably suffice if the incremental flipping approach was implemented somewhere in CGAL. But I guess CGAL only uses Bowyer-Watson? Or is there some code somewhere for incremental flipping?
>
> Thanks!-Marc
>
>
>
>
>
>> On 9. Jan 2020, at 09:34, Mael <[hidden email]> wrote:
>>
>> Hello
>>
>> Here is a translation of an answer by Jean-Daniel Boissonnat in private correspondence:
>>
>>> Considering the usual lifting into R^{d+1} (R^4 here), let p1, ..., pn be points in R^3 and P1, ..., Pn their lifted equivalent, i.e. Pi = (pi, pi^2).
>>> Let x be the new point, X=(x, x^2), and T the face of the convex hull conv(P1, ..., Pn) whose projection onto R^3 contains x.
>>> The 4th coordinate of the lifted point X (and thus its weight) must be chosen such that X is below conv(P1, ..., Pn). To ensure that no point disappears, the new convex hull conv(P1, ..., Pn, X) must have all points as vertices,
>>> in other words X must be above the planes of the faces of convex(P1, ..., Pn) that are adjacent to T.
>>> This can be expressed with circumscribing balls in R^3.
>> As to get the triangulations that appear when moving within this range, you can probably use a similar reasoning as the combinatorics will change when an adjacent face is no longer on the convex hull.
>>
>> There also used to be a package called Kinetic Data Structure in CGAL, it could handle Regular_triangulation_3 but I am not sure if the kinetic change had to be the position of a point with a fixed weight, or if you could also change weights.
>>
>> Best,
>> Mael
>>
>> On 07/01/2020 19:18, 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
>>>
>>>
>>>
>> --
>> You are currently subscribed to cgal-discuss.
>> To unsubscribe or access the archives, go to
>> https://sympa.inria.fr/sympa/info/cgal-discuss
>>
>>
>

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