bpmn-layout-generators Review the "Manhattan" layout algorithm

Review the "Manhattan" layout algorithm

Open tbouffard opened this issue 5 years ago • 1 comments

This is the way we are building the graph under the hood: The Manhattan distance function computes the distance that would be traveled to get from one data point to the other if a grid-like path is followed.

resources

https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1039&context=ecetr
https://stackoverflow.com/questions/1285623/manhattan-layout-algorithm
https://en.wikipedia.org/wiki/Organizational_chart
http://www.improvedoutcomes.com/docs/WebSiteDocs/Clustering/Clustering_Parameters/Manhattan_Distance_Metric.htm

mxgraph java implementation

https://github.com/jgraph/mxgraph/tree/v4.2.2/java/src/com/mxgraph/layout

used by bpmn.io for autolayout (there are refs to this algorithm described in diagram-js)

https://github.com/bpmn-io/diagram-js/blob/develop/lib/layout/ManhattanLayout.js#L197
https://github.com/bpmn-io/bpmn-auto-layout/blob/fa13b219c470a46ea0d1044d04d19d9183c7ac40/lib/DiUtil.js#L48