Triangle.NET icon indicating copy to clipboard operation
Triangle.NET copied to clipboard

Computation progress

Open foxyseta opened this issue 2 years ago • 6 comments

On large sets of data, some procedures in Triangle.NET may turn out to be reasonably efficient, but not immediate. For example, I'm working with GenericMesher.Triangulate at the moment. Could its implementation be enriched so as to inform its calling code about progress in the computation? Perhaps one idiomatic way to achieve this would be making use of the Progress<T> Class from the System namespace.

foxyseta avatar Aug 22 '22 12:08 foxyseta

I'm open to suggestions. Have you done any benchmarks to find the hot spots in the code? I guess, the triangulation will be dominating the running time, but I never did a separate benchmark of the segment insertion and Delaunay refinement code.

wo80 avatar Aug 22 '22 19:08 wo80

Did a quick benchmark on a collection of poly files:

  Triangulation time: 0.494 seconds
     |     Sort time: 0.093 seconds
     | Delaunay time: 0.383 seconds
 Seg. Insertion time: 0.000 seconds
     Refinement time: 0.022 seconds

So reporting from the ITriangulator should be enough. I did a test with Dwyer. The progress could be reported at the end of DivconqRecurse:

void DivconqRecurse(int left, int right, int axis,
                    ref Otri farleft, ref Otri farright)
{
    // ...
    
        // Merge the two triangulations into one.
        MergeHulls(ref farleft, ref innerleft, ref innerright, ref farright, axis);

        // NEW PROGRESS REPORTING CODE

        // Initializing the step size should be done at the beginning
        // of the Triangulate method.
        if (progressCounter == 0)
        {
            // The constant 2.5 is a guess for Dwyer.
            progressStep = sortarray.Length / 2.5 / PROGRESS_MAX;
        }

        progressCounter++;

        if (progressCounter >= progressCurrent)
        {
            progressCurrent += progressStep;

            Console.CursorLeft = 0;

            // Report progress as percent range [0..100]
            Console.Write("{0:0.0 %} ", progressCurrent / progressStep / PROGRESS_MAX);
        }
    }
}

// https://www.codeproject.com/Tips/1130088/Reporting-Progress-the-Right-Way
const int PROGRESS_MAX = 1000;

double progressStep, progressCurrent = 0.0;
int progressCounter = 0;

The above code should be encapsulated in a ProgressReporter class, which uses IProgress<double>. The progress reporter implementation should be private, the user could provide the IProgress<double> by a property in the Configuration class.

EDIT

For the Dwyer code it's hard to predict the exact number of steps, since we don't know, how often the vertices == 2 or vertices == 3 branch is taken. A conservative choice to initialize progressStep would be 2, which would mean progress will not reach 100% in most cases. The number 2.5 worked fine for me for a test case with 5.000.000 random points but will most likely overshoot in other cases.

wo80 avatar Aug 23 '22 08:08 wo80

Took a second look at the benchmark - seems I measured only the triangulation time:

  Triangulation time: 0,501 seconds
     >     Sort time: 0,093 seconds
     > Delaunay time: 0,392 seconds
 Seg. Insertion time: 0,219 seconds
     Refinement time: 0,473 seconds

So it seems the progress reporting should also take the segment insertion and Delaunay refinement into account.

wo80 avatar Aug 23 '22 15:08 wo80

Thanks! Here's my call tree instead. It is pretty much the same for every test case of mine: 2022-08-24_16-41-24

foxyseta avatar Aug 24 '22 14:08 foxyseta

Ok, so here most of the time is spent for refinement. Since the refinement process is dynamic - meaning that the list of bad quality triangles isn't fixed and new triangles might be added to the queue dynamically - it will be hard to come up with a good approach to report process reliably. One way would be to just report the number of remaining triangles in the queue, which obviously isn't suitable for being displayed in a progress bar or the like.

I currently don't have the time (and motivation) to implement this. To get started, just add an IProgress property to the Configuration class and see if it's working. This way, no method signatures have to be changed.

wo80 avatar Aug 24 '22 16:08 wo80

Sorry for the late reply, and once again, thank you so much for all of your valuable insights and considerations. I just thought this was something at least worth mentioning for some real-world applications. As far as I am concerned, this issue may be closed now.

foxyseta avatar Aug 29 '22 08:08 foxyseta