Computation progress

[foxyseta]

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 Class from the System namespace.

[wo80]

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]

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]

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.

[foxyseta]

Thanks! Here's my call tree instead. It is pretty much the same for every test case of mine:

[wo80]

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.

[foxyseta]

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.