search

JuliaPolyhedra / Polyhedra.jl

Polyhedral Computation Interface
Other
172 stars 27 forks source link

Remove redundancy of triangulation #329

Closed lxvm closed 7 months ago

lxvm commented 8 months ago

Hi,

This pr is attempting to fix #285 and #249 by removing redundant simplices produced by triangulation_indices. So far I have added 7 polyhedra to the tests and have checked whether their volume is calculated correctly. Of these, 5 volumes were previously calculated incorrectly, including several examples from the issues and the isocahedron, and two were correct, namely the 5-simplex and the dodecahedron.

The fix I have attempted so far is naively calling unique on the list of simplices, and with a bit more work I hope that I can correct the implementation itself. Since the implementation is somewhat different from the Cohen-Hickey algorithm I am still figuring this out.

blegat commented 7 months ago

Not sure why the tests are not running since I switched it to ready for review

blegat commented 7 months ago

Can you rebase on top of the master branch ?

lxvm commented 7 months ago

@blegat I rebased this pr onto master and fixed a missing test dependency

blegat commented 7 months ago

The tests don't work if you use the default library instead of CDDLib ?

blegat commented 7 months ago

Since the implementation is somewhat different from the Cohen-Hickey algorithm I am still figuring this out.

Yes I don't remember why I implemented like this. We could probably merge this PR with the new tests and fixed implementation using unique. Then, in a later PR, we could rewrite the implementation with Cohen-Hickey and see if we can remove the unique and the tests are still passing.

codecov[bot] commented 7 months ago

Codecov Report

All modified and coverable lines are covered by tests :white_check_mark:

Comparison is base (268c701) 88.95% compared to head (a867113) 88.95%.

Additional details and impacted files ```diff @@ Coverage Diff @@ ## master #329 +/- ## ======================================= Coverage 88.95% 88.95% ======================================= Files 37 37 Lines 3170 3170 ======================================= Hits 2820 2820 Misses 350 350 ```

:umbrella: View full report in Codecov by Sentry.
:loudspeaker: Have feedback on the report? Share it here.

lxvm commented 7 months ago

I updated the tests as you suggested and exchanged CDDLib for the default library in exact arithmetic.

I agree it would be great to merge this "patch" fix and revisit the algorithm. When I read the implementation, it is very similar to Cohen-Hickey in that it is recursive, however it does not perform certain manipulations such as elimination that I would expect from Cohen-Hickey. I think this is interesting and may be more efficient, i.e. fewer computations, but it would be useful to pinpoint where the redundancy originates from.

blegat commented 7 months ago

Yes, I don't remember exactly why I thought it would work but I could try to recollect my thoughts (good example of why comments are important ^^)