Deadlock in `itk::VoronoiDiagram2DGenerator<double>::ConstructDiagram()`

[ILoveGoulash]

Description

This simple example with these specific values deadlocks.

Steps to Reproduce

#include <itkVoronoiDiagram2DGenerator.h>

int main()
{
    using VoronoiDiagramType         = itk::VoronoiDiagram2D<double>;
    using VoronoiGeneratorType       = itk::VoronoiDiagram2DGenerator<double>;
    using PointType                  = VoronoiDiagramType::PointType;
    VoronoiGeneratorType::Pointer vg = VoronoiGeneratorType::New();
    vg->SetOrigin(PointType {{-1.61569, -1.76726}});
    vg->SetBoundary(PointType {{1.60174, 1.76345}});
    vg->AddOneSeed(PointType {{-1.39649, 0.322212}});
    vg->AddOneSeed(PointType {{-1.30128, 0.231786}});
    vg->AddOneSeed(PointType {{-1.21509, 0.0515039}});
    vg->AddOneSeed(PointType {{-1.22364, -0.030281}});
    vg->AddOneSeed(PointType {{-1.22125, -0.120815}});
    vg->AddOneSeed(PointType {{-1.25159, -0.23593}});
    vg->Update();
}

Expected behavior

No deadlock.

Actual behavior

Deadlock.

Reproducibility

Every time.

Versions

ITK 5.1.2; reproducing on a recent version would be possible but very painful, as I'm in a restricted work environment.

Environment

Tested on MacOS Ventura (Apple clang 15) and Windows 11 (MSVC 2019).

[github-actions]

Thank you for contributing an issue! 🙏

Welcome to the ITK community! 🤗👋☀️

We are glad you are here and appreciate your contribution. Please keep in mind our community participation guidelines. 📜
Also, please check existing open issues and consider discussion on the ITK Discourse. 📖

This is an automatic message. Allow for time for the ITK community to be able to read the issue and comment on it.

[seanm]

I just tried to repro this with master, built with TSan (thread sanitizer) and it doesn't detect any deadlock (in the threading sense).

Debugging it quickly, it seems to be in an infinite loop. while (!(rawEdges[i].empty())) seems to be running forever because near the bottom of that loop the last else keeps adding more items rawEdges[i].push_back(curr);

[ILoveGoulash]

Hello, we fixed it locally by reverting this modification that was clearly done without much thoughts given and adding

-    while (!(rawEdges[i].empty()))
+    while (!(rawEdges[i].empty()) && (maxStop > 0))

[dzenanz]

Could you propose a PR with this change?

[ILoveGoulash]

Here it is. The example in the OP is fixed by this in our case.