CGAL users discussion list

[Adam Getchell <>]

Ah. By "rebalance" I mean adjusting the coordinates of the vertices of the three simplices produced by the facet flip in such a way as to satisfy the Delaunay condition.

Naively, perhaps by decreasing the 12 edge length and increasing the edge links of the former facet 345, so that T.is_valid() again passes.

On Mon, Feb 9, 2015 at 11:37 PM, Sebastien Loriot (GeometryFactory) <> wrote:

On 02/10/2015 08:34 AM, Adam Getchell wrote:

Is there a way to rebalance a Delaunay triangulation after a flip() on a
facet?

what do you mean?

Sebastien.

On Fri, Feb 6, 2015 at 12:23 PM, Adam Getchell <
<mailto:adam.getchell@gmail.com>> wrote:

    Sebastien,

    Thank you!

    In hindsight, it makes sense that the facet flip results in an edge
    which violates the Delaunay condition.

    Regards,

    Adam

    On Wed, Feb 4, 2015 at 11:32 PM, Sebastien Loriot (GeometryFactory)
    < <mailto:>> wrote:

        If you flip some edges in a Delaunay triangulation, the is_valid
        will tell you that the triangulation is no longer Delaunay.
        Use the dt.tds().is_valid() instead.

        Sebastien.


        On 02/05/2015 07:23 AM, Adam Getchell wrote:

            I've also done tests on flips of (2,2) simplices, with the
            same results
            (triangulation validity violated), except that they don't
            also violate
            my time foliation. The code currently on GitHub reflects the
            flips on
            (2,2) simplices.

            On Wed, Feb 4, 2015 at 10:07 PM, Adam Getchell
            < <mailto:adam.getchell@gmail.com>
            <mailto:adam.getchell@gmail.__com
            <mailto:adam.getchell@gmail.com>>> wrote:

                 Hello all,

                 For the following code:

                 void make_23_move(Delaunay* D3,
            std::vector<Cell_handle>* three_one,
                                       std::vector<Cell_handle>* two_two) {
                    // Pick a random (2,2)
                    unsigned choice =
            generate_random_unsigned(__three_one->size());
                    std::cout << "We're picking (3,1) vector " << choice
            << std::endl;
                    Cell_handle to_be_moved = (*three_one)[choice];
                    for (size_t i = 0; i < 4; i++) {
                      if (D3->flip(to_be_moved, i)) {
                        // Delaunay::flip_flippable(to___be_moved,0)
                        std::cout << "Facet " << i << " was flippable."
            << std::endl;
                        break;
                      } else {
                        std::cout << "Facet " << i << " was not
            flippable." << std::endl;
                      }
                    }
                 }

                 From:
            https://github.com/acgetchell/__CDT-plusplus/blob/master/src/__S3ErgodicMoves.h
            <https://github.com/acgetchell/CDT-plusplus/blob/master/src/S3ErgodicMoves.h>

                 Invoked in the test:

                 TEST_F(S3ErgodicMoves, MakeA23Move) {
                    unsigned number_of_vertices_before =
            T.number_of_vertices();
                    unsigned N3_31_before = three_one.size();
                    unsigned N3_22_before = two_two.size();
                    unsigned N3_13_before = one_three.size();
                    std::cout << "Number of (2,2) simplices before = "
            << N3_22_before
                              << std::endl;
                    make_23_move(&T, &three_one, &two_two);

                    // Now look at changes
                    reclassify_3_simplices(&T, &three_one, &two_two,
            &one_three);
                    unsigned N3_31_after = three_one.size();
                    unsigned N3_22_after = two_two.size();
                    unsigned N3_13_after = one_three.size();

                    EXPECT_TRUE(T.is_valid())
                    << "Triangulation is invalid.";

                 From:
            https://github.com/acgetchell/__CDT-plusplus/blob/master/__unittests/S3ErgodicMovesTest.__cpp

            <https://github.com/acgetchell/CDT-plusplus/blob/master/unittests/S3ErgodicMovesTest.cpp>

                 I've run these tests a couple dozen times, and every
            time there is a
                 flippable edge the triangulation is invalidated, e.g.:

                 Repeating all tests (iteration 9) . . .


                 Note: Google Test filter = S3ErgodicMoves.MakeA23Move

                 [==========] Running 1 test from 1 test case.

                 [----------] Global test environment set-up.

                 [----------] 1 test from S3ErgodicMoves

                 [ RUN      ] S3ErgodicMoves.MakeA23Move

                 Generating universe ...

                 Pass #1

                 Fixing foliation....

                 Pass #2

                 Fixing foliation....

                 Pass #3

                 Fixing foliation....

                 Pass #4

                 Fixing foliation....

                 Pass #5

                 Fixing foliation....

                 Classifying simplices....

                 Valid foliation: true

                 Delaunay triangulation has 95251 cells.

                 There are 29713 (3,1) simplices and 35628 (2,2)
            simplices and 29910
                 (1,3) simplices.

                 Number of (2,2) simplices before = 35628

                 Random number is 27858

                 We're picking (3,1) vector 27858

                 Facet 0 was flippable.

                 Classifying simplices....

                 ../unittests/__S3ErgodicMovesTest.cpp:82: Failure

                 Value of: T.is_valid()

                    Actual: false

                 Expected: true

                 Triangulation is invalid.

                 [  FAILED  ] S3ErgodicMoves.MakeA23Move (2229 ms)

                 [----------] 1 test from S3ErgodicMoves (2229 ms total)


                 [----------] Global test environment tear-down

                 [==========] 1 test from 1 test case ran. (2229 ms total)

                 [  PASSED  ] 0 tests.

                 [  FAILED  ] 1 test, listed below:

                 [  FAILED  ] S3ErgodicMoves.MakeA23Move


                   1 FAILED TEST



                 --
                 Adam Getchell
            about.me/adamgetchell <http://about.me/adamgetchell>
            <http://about.me/adamgetchell>
                 "Invincibility is in oneself, vulnerability in the
            opponent." -- Sun Tzu




            --
            Adam Getchell
            about.me/adamgetchell <http://about.me/adamgetchell>
            <http://about.me/adamgetchell>
            "Invincibility is in oneself, vulnerability in the
            opponent." -- Sun Tzu



        --
        You are currently subscribed to cgal-discuss.
        To unsubscribe or access the archives, go to

        https://sympa.inria.fr/sympa/__info/cgal-discuss
        <https://sympa.inria.fr/sympa/info/cgal-discuss>





    --
    Adam Getchell
    about.me/adamgetchell <http://about.me/adamgetchell>
    "Invincibility is in oneself, vulnerability in the opponent." -- Sun Tzu




--
Adam Getchell
about.me/adamgetchell <http://about.me/adamgetchell>
"Invincibility is in oneself, vulnerability in the opponent." -- Sun Tzu

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

--

Adam Getchell

about.me/adamgetchell

"Invincibility is in oneself, vulnerability in the opponent." -- Sun Tzu