Speuler: SEmantics-preserving Euler diagrams
Used tools:
Running the application:
- Install dependencies by calling npm install.
- Build the application by calling npm run build.
- Open the resulting index.html in the browser.
Description:
Speuler is an algorithm meant to visualize sets as Euler diagrams while making sure that they are
well-matched (every set intersection is represented in the diagram and no extra intersections
occur) and
well-formed (no more than two curves intersect at a given point).
This is achieved as follows:
- Get every distinct area where sets intersect and turn it into a node for dual graph.
- Sort the nodes by rank(number of sets intersecting in this node).
- Connect those nodes together so that
- Connections occur only between nodes that differ exactly by one set intersecting in them.
- The graph is planar.
- The amount of monotone faces(faces consisting of 4 edges with alternating
colors, which in this case represent the sets, whose borders go through these
edges) is maximized.
This is achieved by only considering nodes in neighbouring ranks, calculating adjacency matrixes for them,
sorting them by the length of their consecutive ones sequences, and connecting them in this
order, while also removing crossing edges.
- Generate a layout for the graph by first laying out the rank with the largest number of nodes in a circular
manner at uniform intervals. All other nodes are then layed out in circles around them similar to the layout
of radial trees.
- Generate the curves for sets by connecting midpoints of edges of same colors and gate
nodes(points lying
between every two nodes of the same rank) in a sequence and drawing a Catmull-Rom spline using those points
as control points.
Links: