Algorithm - OverQuantum/path_ortho GitHub Wiki

path_ortho use following orthogonalization algorithm

1. Path is checked for closure - if first node is equal to last one then path is considered as closed and result also will be closed path.
2. Vectors of path are multiplied by their lengths (lengths becomes cubes, this increases effects of longer vectors).
3. Vectors are rotated with step of 90 degrees to fit into two ranges:
   • from 0 to +90 degrees,
   • from -45 to +45 degrees.
4. In both groups vectors are summed, results are two versions of base vector. These vectors are normalized.
5. For both vectors calculated square error for approximation the path. Vector of path (not multiplied) is projected to base vector and orthogonal vector. Smallest of two projections is squared and summed into square error.
6. Base vector having smallest square error is declared as main base vector and used in further calculations.
7. All vectors of path are divided by direction into "along" and "ortho" to base vector - based on which projection is bigger, to base vector or to orthogonal vector. Direction of vectors is saved into flags array.
8. For vector group - consequent vectors having same direction ("along" or "ortho") - calculated C-parameter of equation Ax+By=C, which defines line approximation of polyline constructed from vectors. (A,B) is vector perpendicular to line, chosen from base vector or orthogonal vector, depending from vector group direction.
   • If path is not closed, missing C-parameter of first and last node is calculated by single node
9. Node coordinates of new path are calculated from two C-parameters of consequent vector groups.
10. Vectors of new path are checked for length. In case of vectors with length below collapse-limit, these vectors are removed from path:
    • Direction flags of whole group of vectors of source path, which makes this small vector, is adjusted to be same as on previous group,
    • New path rebuilded by starting from calculation of C-parameters.

The only parameter of algorithm is collapse-limit.

Most of calculations use very simple mathematics. Most complex function is square root, which used only for normalization of two versions of base vector.


This orthogonalization algorithm by OverQuantum is licensed under a Creative Commons Attribution 3.0 Unported License (CC BY 3.0).
Copyright © 2013 OverQuantum