Arrangement merge_edge assigns incorrect direction

[Yvee1]

Issue Details

The arrangement modification function merge_edge may invalidate the arrangement. In particular, the merged edge may have incorrect direction (that is, the direction returned by direction() does not match the actual edge direction).

Source Code

This is a minimal example with two straight edges that are merged into one with an incorrect direction.

#include <CGAL/Exact_predicates_exact_constructions_kernel.h>
#include <CGAL/Arrangement_2.h>
#include <CGAL/Arr_segment_traits_2.h>

int main() {
    using K = CGAL::Epeck;
    using Traits = CGAL::Arr_segment_traits_2<K>;
    using Arrangement = CGAL::Arrangement_2<Traits>;
    Arrangement arr;
    K::Segment_2 seg1({0, 1}, {1, 0});
    K::Segment_2 seg2({0.1, -1}, {1, 0});
    CGAL::insert(arr, seg1);
    auto eh = CGAL::insert_non_intersecting_curve(arr, seg2);
    if (eh->source()->point() != seg2.source()) {
        eh = eh->twin();
    }

    std::cout << arr.is_valid() << std::endl;
    K::Segment_2 seg3(seg2.source(), seg1.source());
    auto ehn = eh->next();
    std::cout << eh->source()->point() << " -> " << eh->target()->point() << " " << eh->direction() << std::endl;
    std::cout << ehn->source()->point() << " -> " << ehn->target()->point() << " " << ehn->direction()<< std::endl;
    auto merged = arr.merge_edge(eh, eh->next(), seg3);
    std::cout << merged->source()->point() << " -> " << merged->target()->point() << " " << merged->direction() << std::endl;
    std::cout << arr.is_valid() << std::endl;
    return 0;
}

Environment

• CGAL version: 5.6

[efifogel]

I confirm that there is an issue. The problem is with the spec. in the manual. A precondition that requires that two halfedges have the same direction is missing.

[Yvee1]

Thanks for the quick reply. Is there a reason why merge_edge is not provided for halfedges with different direction? I don't immediately see an issue with such a function, but I presume there is some complication that prohibits such a more general function?

[efifogel]

Yes. It is because this function does not apply geometric operations. It is purely combinatorial. (It does not use the traits.) Handling the directions would require a geometric operation, which is expensive. We could add a new function, say, replace_edge(). Its performance would probably be between merge_edge() and the equivalent sequence of remove, remove, and insert.

[Yvee1]

I think it would be useful to have a merge_edge() method that works on halfedges of different direction too. For example, when simplifying an arrangement, it's natural to want to merge edges to reduce the complexity of the arrangement, and then the x-direction of the halfedges that you merge will not necessarily be the same. It seems most natural to me to let merge_edge provide this functionality as well. I'm not familiar with all the bookkeeping that the arrangement does internally, but to me it seem the only addition needed to make this work for halfedges of different direction is to compare the x-coordinates of the endpoints of the new edge, and then set its direction accordingly. This relatively expensive geometric comparison need only be performed after the 'same-direction check' fails. If the problem is that the one 'same-direction' check may be superfluous in case it is already known that the edges have the same direction then passing it as an argument seems most sensible to me (more than creating a new function entirely to avoid this one operation).

[efifogel]

Hi Steven, You are not wrong, but there are other things that need to be taken into account. The most common use of merge_edge() is to replace 2 edges associated with 2 x-monotone curves, c1 and c2, with a new edge associated with the x-monotone curve c, which is the union of c1 and c2. The geometric traits classes support the Is_mergeable_2 and Merge_2 functors that can construct c from c1 and c2, when possible. As a matter of fact, there is an overloaded merge_edge(0 that does not even accept the new curve, but rather constructs it using the traits. In the code of merge_edge(), there is no trace of the traits, and thus super fast. It turns out that the code does a bit more, that is, c does not have to be the union of c1 and c2; so we dropped this requirement, but forgot to add several other (weaker) requirements: 1. The directions must be identical, 2. holes are not relocated from one face to another, and 3. the x-monotone curve c and all other existing curves in the arrangement (except for c1 and c2) must be interior disjoint pairwise. Observe that requirement (3) immediately holds if c is indeed the union of c1 and c2. Also, there is a basic requirement (which should be explicitly stated as well in the manual...): The degree of the common vertex must be 2. (This vertex is removed as part of the operations.) So now there is room for several functions with different combinations of requirements... I guess that we can introduce a function called replace_edge(), which does exactly what you say and does not have requirement (1) above. Best, Efi ____ _ ____ _ /_____/_) o /__________ __ // (____ ( ( ( (_/ (_/-(-'_(/ _/

…

On Mon, 16 Dec 2024 at 11:57, Steven van den Broek ***@***.***> wrote: I think it would be useful to have a merge_edge() method that works on halfedges of different direction too. For example, when simplifying an arrangement, it's natural to want to merge edges to reduce the complexity of the arrangement, and then the x-direction of the halfedges that you merge will not necessarily be the same. It seems most natural to me to let merge_edge provide this functionality as well. I'm not familiar with all the bookkeeping that the arrangement does internally, but to me it seem the only addition needed to make this work for halfedges of different direction is to compare the x-coordinates of the endpoints of the new edge, and then set its direction accordingly. This relatively expensive geometric comparison need only be performed after the 'same-direction check' fails. If the problem is that the one 'same-direction' check may be superfluous in case it is already known that the edges have the same direction then passing it as an argument seems most sensible to me (more than creating a new function entirely to avoid this one operation). — Reply to this email directly, view it on GitHub <#8659 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ABVBNOFFLYYSYCTZXOICRDL2F2PZXAVCNFSM6AAAAABTTVUSJ6VHI2DSMVQWIX3LMV43OSLTON2WKQ3PNVWWK3TUHMZDKNBVGEZDGMZTGI> . You are receiving this because you commented.Message ID: ***@***.***>

[Yvee1]

Makes sense, thank you for the explanation!