Perf: minor change SemiVirtualIncrementalTin::remove about tinfour HOT 5 CLOSED

Same change is applicable to IncrementalTin too.

from tinfour.

Interesting idea. I will investigate.

I added some diagnostic code to the IncrementalTin class so that it would count how many cases where the nEar==3 would occur at the end of step 1. I then ran the "ExampleCrossValidation" test application from the example code provided with the Tinfour distribution. Cross validation involves systematically removing and then replacing each vertex in the triangulated mesh. So it was a quick way to test the proposed concept. I processed a subsection of the "Bear Mountain" lidar data sample that is described in the Tinfour documentation. For 9453 removals, the test resulted in a count of 29 nEar==3 cases.

Let me clarify the reasoning behind Martin's proposal. The nEar==3 case occurs when the vertex-to-be-removed connects to exactly 3 edges. When the vertex is removed, the remaining cavity is a triangle which happens to be Delaunay compliant (I think I have a proof for that). So if we counted the number of edges removed in Step 1 (as suggested), and it turned out to be 3, we could exit early. Counting the edges adds very little overhead to the process. So even though the nEar==3 case occurs infrequently, the proposed saving would be larger than the extra processing cost.

I will do some more tests to make sure that my numbers are correct. I also need to verify my assumption that the resulting triangular cavity would always be Delaunay.

from tinfour.

I'm sorry I have no statistics on my data. Can you wait till Friday?
I need to eliminate every piece of code and allocation that is not necessary. My data set is about 35k tiles each with ~100k vertices. About 60% of vertices are removed. This is extreme. I need to write better algorithms :-) This seems to me like simple change.

from tinfour.

No worries. This is a simple change, so I'd say go ahead and make it yourself for your own copy of the Tinfour code. I'll migrate it into the main Tinfour code base sometime over the next week or so. I will also collect performance stats, so you don't have to do so if it is not convenient at this tim.

I suspect that you will find that you see slightly stronger speed improvement in the semi-virtual implementation than in the standard.

Děkuji

Gary

from tinfour.

I performed performance testing with the new RepeatedDeleteTest application. The improvement was so small that I could not accurate measure it given to the noisy test environment on my Windows 7 computer (run times were too variable to demonstrate a statistically meaningful improvement). But the suggestion makes the code cleaner and more robust. So I decided to use it.

Thanks again for you suggestions and contributions to the Tinfour project.

from tinfour.