3 ms·

Thanks and I will add this to my todos!

by robhati 4mo ago

ffsm8 4mo ago
A few years ago I created a similar layout engine, it was extremely janky when I abandoned it because I first wanted to solve order/placing of the tiles but was unable to figure out a good algorithm for it Eg your example diagram has an optimal order in which there are no overlapping lines... But it's surprisingly hard to figure that out without doing n^m calculations... And I wanted to use it in a game, so a shitton of tiles. Dunno where I was going with this, just got reminded of that project after looking at this great implementation. It also reminded me of the xyflow lib
- johndough 4mo ago
  In academia, this is called "planar embedding" and can be computed in O(V) where V is the number of vertices of the graph. However, there are graphs that do not allow planar embeddings (e.g. K_5 or K_3,3, see https://en.wikipedia.org/wiki/Planar_graph https://en.wikipedia.org/wiki/Planar_graph). In this case, you'll probably want to look into heuristics that produce a low number of crossings and little distortion when new vertices are added.
- jeffreygoesto 4mo ago
  https://github.com/kieler/elkjs https://github.com/kieler/elkjs works well for auto layout.
- tharkun__ 4mo ago
  Not sure what you're seeing, but I see quite a few overlapping lines. One of them easily solvable if you move `addresses` down. It starts with the `orders->users` overlapping `orders->addresses`. Also, the `reviews` table overlaps the line from `order_items` to `products` and moving `order_items` down for example gets rid of that problem. Not saying the project isn't cool, but this layout isn't optimal as per your constraints.
  - ffsm8 4mo ago
    Ah, I was imprecise in my comment. I didn't mean that this implementation was doing the optimal ordering - I was just reminiscing about a similar project I worked on an why I abandoned it (I was unable to get the ordering done while keeping performance good enough with thousands of tiles

Thanks and I will add this to my todos!

by robhati 4mo ago

Thanks and I will add this to my todos!

ffsm8 4mo ago

A few years ago I created a similar layout engine, it was extremely janky when I abandoned it because I first wanted to solve order/placing of the tiles but was unable to figure out a good algorithm for it Eg your example diagram has an optimal order in which there are no overlapping lines... But it's surprisingly hard to figure that out without doing n^m calculations... And I wanted to use it in a game, so a shitton of tiles. Dunno where I was going with this, just got reminded of that project after looking at this great implementation. It also reminded me of the xyflow lib

johndough 4mo ago
In academia, this is called "planar embedding" and can be computed in O(V) where V is the number of vertices of the graph. However, there are graphs that do not allow planar embeddings (e.g. K_5 or K_3,3, see https://en.wikipedia.org/wiki/Planar_graph https://en.wikipedia.org/wiki/Planar_graph). In this case, you'll probably want to look into heuristics that produce a low number of crossings and little distortion when new vertices are added.
jeffreygoesto 4mo ago
https://github.com/kieler/elkjs https://github.com/kieler/elkjs works well for auto layout.
tharkun__ 4mo ago
Not sure what you're seeing, but I see quite a few overlapping lines. One of them easily solvable if you move `addresses` down. It starts with the `orders->users` overlapping `orders->addresses`. Also, the `reviews` table overlaps the line from `order_items` to `products` and moving `order_items` down for example gets rid of that problem. Not saying the project isn't cool, but this layout isn't optimal as per your constraints.
- ffsm8 4mo ago
  Ah, I was imprecise in my comment. I didn't mean that this implementation was doing the optimal ordering - I was just reminiscing about a similar project I worked on an why I abandoned it (I was unable to get the ordering done while keeping performance good enough with thousands of tiles