Infinite loop

[Michael2109]

I've noticed when passing a certain polygon to the algorithm it ends up in an infinite loop. I've narrowed this down to a do while loop in delaunator.hpp.

delaunator.hpp

if (hbl == INVALID_INDEX) {
    std::size_t e = hull_start;
    do {
        if (hull_tri[e] == bl) {
            hull_tri[e] = a;
            break;
        }
        e = hull_next[e];
    } while (e != hull_start);
}

Infinite loop

std::vector<double> points = {39, 14, 38, 15, 37, 16, 37, 17, 37, 18, 38, 19, 38, 20, 38, 21, 38, 22, 39, 23, 39,
                              24, 40, 25, 41, 25, 42, 26, 43, 27, 44, 27, 45, 28, 46, 28, 47, 28, 48, 28, 49, 27,
                              49, 26, 49, 25, 49, 24, 49, 23, 49, 22, 48, 21, 48, 20, 48, 19, 47, 18, 46, 17, 46,
                              16, 45, 15, 44, 15, 43, 14, 42, 14, 41, 14, 40, 14
};
concavehull(points, 0);

Is this a problem with the coords I'm passing in or the code?

[liuhao123t]

i meet the same problem,do you finish it ?

[MichaelJHaywood]

@liuhao123t I can't remember exactly but will take a guess. I think these libraries often expect the last coord to be the same as the start coord?

[liuhao123t]

@MichaelJHaywood i try to delete the code of while loop, it will work on your case, but does not on other case

[liuhao123t]

@MichaelJHaywood i use this link to calculate concavehull

[Quietliz]

I've noticed when passing a certain polygon to the algorithm it ends up in an infinite loop. I've narrowed this down to a do while loop in delaunator.hpp.

delaunator.hpp

if (hbl == INVALID_INDEX) {
    std::size_t e = hull_start;
    do {
        if (hull_tri[e] == bl) {
            hull_tri[e] = a;
            break;
        }
        e = hull_next[e];
    } while (e != hull_start);
}

Infinite loop

std::vector<double> points = {39, 14, 38, 15, 37, 16, 37, 17, 37, 18, 38, 19, 38, 20, 38, 21, 38, 22, 39, 23, 39,
                              24, 40, 25, 41, 25, 42, 26, 43, 27, 44, 27, 45, 28, 46, 28, 47, 28, 48, 28, 49, 27,
                              49, 26, 49, 25, 49, 24, 49, 23, 49, 22, 48, 21, 48, 20, 48, 19, 47, 18, 46, 17, 46,
                              16, 45, 15, 44, 15, 43, 14, 42, 14, 41, 14, 40, 14
};
concavehull(points, 0);

Is this a problem with the coords I'm passing in or the code?

@Michael2109 @liuhao123t What's the reason for this?How did you resolve this? Thank you.

[MichaelJHaywood]

@Quietliz Have you tried making the last coord the same as the first coord? I can see yours ends on (40,14) instead of (39,14).

[senhorsolar]

Looks like it's a problem from https://github.com/delfrrr/delaunator-cpp which is what I used for the delaunay triangulation. I'm going to fix it based on a more recent fork of it.

[senhorsolar]

This fork seems to be more up to date https://github.com/abellgithub/delaunator-cpp and appears to solve the infinite loop problem. I'll go ahead and use this implementation instead and include some other optimizations.