rochaporto
commented
10 years ago Correct results are already achieved, but further optimizations are left for later.
For now it is 5 times slower than maxxc, which is not so serious - a long flight will take around 20 seconds to compute.
These further optimizations should improve the performance:
- Improved max calculation for candidates, counting intermediate vertices along the path
- Eager branching of candidates, when multiple rectangles share the same fix set
This document: https://github.com/rochaporto/ezgliding/blob/master/doc/palkovsky-optimization.pdf
has a good overview of a branch and bound strategy to perform both broken line and triangle optimization. It should give much more obvious code than the hard small optimizations over a brute force approach of things like maxcc or the other available open source optimizers.
Performance is said to be fraction of second, shouldn't be too different in JAVA.