https://medium.com/@ivan.ishubin/how-i-used-linear-algebra-to-build-an-interactive-diagramming-editor-and-why-matrix-math-is-d5bd552f2e8d Open in app Sign up Sign in [ ] Write Sign up Sign in [1] How I Used Linear Algebra to Build an Interactive Diagramming Editor -- and Why Matrix Math is Awesome Ivan Shubin ITNEXT Ivan Shubin * Follow Published in ITNEXT * 11 min read * 16 hours ago -- 1 Listen Share Ah, matrices. One of those core linear algebra concepts we all encountered in school. Despite their significance, I never had the chance to work with them during my career, which led me to forget just how powerful and versatile they can be. For me, that moment came while working on Schemio, my interactive diagramming editor. This article dives into how I used matrices to solve some tricky problems, and it's for everyone who's curious about the math behind it. Starting Simple: The Early Days of Schemio When I first began building Schemio, it was straightforward: you could create shapes, move them, resize them, and even rotate them. Each shape was a simple area defined by position (x, y), size (width, height), and rotation angle. Easy enough. The data structure representing the diagram looked something like this: const diagram = { name: "The title of a diagram", // all objects in the diagram were represented by a flat array items: [{ id: "2563", name: "Rect 1", shape: "rect", area: { // position in the world coordinates x: 0, y: 0, // width (w) and height (h) w: 100, h: 40, // rotation angle in degrees r: 0 } }, { id: "wer23", name: "Ellipse 1", shape: "ellipse", area: { // position in the world coordinates x: 100, y: 40, // width (w) and height (h) w: 40, h: 40, // rotation angle in degrees r: 45 } }] }; But things got interesting when I wanted to add an item hierarchy -- allowing users to attach shapes to one another and create complex interactions. Many vector graphics editors support grouping, where moving one object automatically moves the others in the group. But I wanted more. I envisioned a mix of a diagramming editor and a game engine, with rich animations and custom behaviors. So, I introduced item hierarchy (by adding "childItems" array to every object), crossed my fingers, and went for it. Here's a snippet of what the item structure initially looked like in code: const item = { id: "123", name: "Rect", shape: "rect", area: { x: 100, y: 400, w: 80, y: 40, r: 0, }, childItems: [{ id: "462", name: "Ellipse", shape: "ellipse", area: { x: 10, y: 0, w: 30, y: 10, r: 45, }, childItems: [{ // yet another item attached to ellipse }] }] }; The Problem with Hierarchies Picture this: you've got a rectangle in your diagram. You attach another shape to it, then another to that one. Now rotate the rectangle. If you're rendering with SVG, it's easy -- just nest SVG elements, and the browser handles the rest. But Schemio isn't just about rendering. You might attach connectors, mount or unmount objects to each other, or perform custom interactions. For all this, you need to be able to translate between local and world coordinates. My first approach? Naive and clunky. I iterated through the parent chain of objects, applying transformations with a simple formula. Later, I optimized it by caching parent transforms, which worked fine for a while. But soon, I hit two big limitations: scaling and pivot points. Enter Scaling and Pivot Points Scaling adds the ability to adjust an object's dimensions dynamically, and the pivot point defines the center of rotation. The ability to apply scale was a game-changer for Schemio, enabling dynamic loading of external diagrams. Demo of external diagrams loaded inside of each other Without too much thinking I added 4 extra properties to the objects area. Here's the updated area structure: const item = { id: "123", name: "Rect", shape: "rect", area: { x: 100, y: 400, w: 80, y: 40, r: 0, /* px an py represent the pivot point which is relative to its width and size so that, when user resizes the shape, the pivot point also adjusts with it */ px: 0.5, py: 0.5, /* sx and sy are the scaling factors along the x and y axes */ sx: 1, sy: 1 }, childItems: [{ // yet another item attached to ellipse }] }; But with these new requirements, managing transformations became messy. That's when I remembered: matrices to the rescue! In 2D (and 3D) graphics, every transformation -- translation, rotation, scaling -- can be expressed using matrices. For example, a point in space is a 3x1 matrix. To transform it, you multiply it by a 3x3 transformation matrix. Let me walk you through some basics. Matrix Transformations 101 Start with the identity matrix, which represents no transformation: Next, a translation matrix, for shifting positions: Want to rotate? Use a rotation matrix: And for resizing, there's the scaling matrix: Combining these is where the magic happens. For instance, to translate and rotate an object, you multiply the translation and rotation matrices. Scaling and pivot-point adjustments follow a similar pattern. Since all the transformation matrices are 3x3, a 2D point needs to be represented as a 3x1 matrix. When you multiply a 3x3 transformation matrix by a 3x1 point matrix, you get another 3x1 matrix -- that's your transformed point. And that's basically how all these transformations work! Here's the full transformation formula for an object: Where does the parent object transformation matrix come from, you might ask? Well it's actually just a multiplication of all of the matrices. So, if we iterate through a chain of items in a hiearchy, we can put it in a simple formula, like this one: In the formula above Ai is current object transformation matrix, while A(i-1) is the the transformation matrix of its parent. Let's expand all the matrices and write out the full formula for transforming a local point to a world point Notice how we first translate the item along with its pivot point, apply the rotation and scaling, and only then translate it back? This is crucial to make the object appear as though it's rotating around the chosen pivot point. Showcase of rotating object around its pivot point If we didn't account for the pivot point, the rotation would look like it's happening around the top-left corner instead. Not ideal, right? Another key detail of the affine transformation formula is that pivot compensation happens after the scaling matrix. This ensures that when you scale an object, it looks like the scaling is happening around the pivot point, keeping it steady in place as you adjust it. Showcase of scaling object with its pivot point at the center World Coordinates vs. Local Coordinates As you can see, we've already achieved some pretty cool results just by applying simple matrix multiplications. But that's not where the real challenge ends. When I was building Schemio, the tricky part wasn't just applying these transformations -- it was figuring out how to map between world coordinates and an object's local coordinates, and vice versa. This kind of mapping is crucial for things like attaching connectors or pinpointing exactly where a user clicked on a transformed object relative to its local top-left corner. We already know how to go from local coordinates to world coordinates, so now let's flip it around and tackle the opposite: converting a world point back to an object's local coordinates. To do that, we'll start with our local-to-world formula: In the formula above, everything except the local point is already known, so we can simplify and group the matrices like this: Here, matrix A represents the entire transformation of an object, including its own transformations and those of all its parent objects. Now, in linear algebra, you can't divide matrices -- but there's a workaround. You can use the inverse of a matrix. If we find the inverse of matrix A, it's denoted as A-1. I won't dive into the details of calculating a matrix inverse since you can look that up in any linear algebra textbook, but once we have A-1, we can multiply both sides of the equation by it from the left: Here's the cool thing about matrix inverses: multiplying a matrix by its inverse gives you the identity matrix, which simplifies everything. This means the formula becomes: And there you have it! That's the formula for converting world points into local coordinates. Matrices make these kinds of transformations much more structured and manageable. Without them, deriving the formula would be unnecessarily complicated and messy. Mounting and Unmounting Objects: The Challenges of Hierarchical Transformations One of the trickier problems I faced while developing the item hierarchy feature in Schemio was handling the mounting and unmounting of objects. There are two ways to do this: You can drag an object on the scene and drop it onto another object. Or, you can rearrange the hierarchy in the Item Selector panel. At first glance, this looks simple enough. Just update the item hierarchy, and you're done, right? Well, not quite. The real challenge is recalculating the new position and rotation for the dragged object. Why? Because every object's position is defined relative to its parent. If you simply change the hierarchy without accounting for the transformation differences, it would look something like this: Notice how the "Rounded Rect" object awkwardly jumps up and down when it's dropped onto another object? Not exactly ideal, is it? So, how can we properly adjust its position and rotation to avoid this? Step 1: Memorize the Dragged Object's Top-Left Position The first thing we need is the world position of the dragged object's top-left corner before it moves. Let's call thistopLeftWorldPoint: const topLeftWorldPoint = worldPointOnItem(0, 0, item); The worldPointOnItem function is actually implemented using the matrix formula we derived earlier. Step 2: Adjust the Object's Rotation Next, we need to adjust the rotation of the dragged object as it moves between parents. Imagine you're transferring an item from one parent to another. First, calculate the world rotation angle of the current parent. Since an object's rotation is defined relative to its parent, we convert this local rotation to a global rotation using a function called worldAngleOfItem. function worldAngleOfItem(item, transformMatrix) { // calculating the world point of top left corner const p0 = worldPointOnItem(0, 0, item, transformMatrix); // calculating the world point of top right corner const p1 = worldPointOnItem(item.area.w, 0, item, transformMatrix); // calculating the angle between the X axis // and the world vector the top edge of the object return fullAngleForVector(p1.x - p0.x, p1.y - p0.y) * 180 / Math.PI; } function fullAngleForVector(x, y) { const dSquared = x * x + y * y; // safety check since we need to normalize the vector // and devide its x and y components by its length if (!tooSmall(dSquared)) { const d = Math.sqrt(dSquared); return fullAngleForNormalizedVector(x/d, y/d); } return 0; } function fullAngleForNormalizedVector(x, y) { if (y >= 0) { return Math.acos(x); } else { return -Math.acos(x); } } The idea is simple: find the vector representing the item's local X-axis and map it to the world coordinates. The angle between this vector and the world X-axis gives us the world rotation angle. Repeat this for the new parent and adjust the dragged object's rotation accordingly: item.area.r += previousParentWorldAngle - newParentWorldAngle; Step 3: Preserve the Object's Position Now, we need to ensure the dragged object stays in the same spot in the world after being moved to a new parent. To do this, I implemented a function called findTranslationMatchingWorldPoint. This function calculates the necessary translation so that the specified local point aligns with the desired world point. const newLocalPoint = myMath.findTranslationMatchingWorldPoint( Wx, Wy, // world point x and y Lx, Ly, // local point on the object (x and y) item.area, // the area object of the object parentTransformMatrix // transformation matrix of its parent ); // Once we have the new translation point, // we just need to update the x and y in the object area. // This way, when we drag any object into other object and // change its position in the item hieararchy, // it will state on the spot on the screen if (newLocalPoint) { item.area.x = newLocalPoint.x; item.area.y = newLocalPoint.y; } How Does It Work? To figure this out, let's revisit the formula for calculating a world point from a local point: Here: * Pw (world point) and PL (local point) are known, as they're function arguments. * The only unknown is At, the translation matrix for the object. Combine all the known matrices into a single matrix A: Since we don't have to adjust the pivot or scaling of the object, all we need is the new At. To help to isolate it, we use the matrix inversion trick again: Let's rename the inverse of the parent transform matrix to make things a bit clearer: Now, here's the catch -- we can't pull the same inversion trick for matrix A because it's a 3x1 matrix, and only square matrices can be inverted. So, let's expand the expression instead: After multiplying all the matrices on both sides, we end up with this: From that, we can focus on just the relevant parts: And finally, we arrive at our complete formula: With these calculations in place, the dragged object seamlessly transitions to its new parent without any weird jumps or distortions. This approach not only preserves the object's position but also ensures its rotation aligns perfectly with the new hierarchy. It's a great example of how understanding and applying mathematical concepts -- like matrix inversions and transformations -- can make complex operations like this possible! Wrapping Up I hope you enjoyed this article and got a taste of the math challenges I tackled while building Schemio. If you're curious about the project and want to dig deeper into how it's implemented, feel free to check out the source code on GitHub: https://github.com/ ishubin/schemio. Want to try it out for yourself? Head over to https://schem.io and start designing your own interactive diagrams or app prototypes. And if you're curious about more math challenges behind Schemio, there's plenty more to explore! From Bezier curves and differential calculus to quadtrees for performance optimization, I'll be sharing more insights soon. Stay tuned! Vector Diagrams Programming Mathematics Matrix -- -- 1 ITNEXT ITNEXT Follow Published in ITNEXT 65K Followers *Last published 1 hour ago ITNEXT is a platform for IT developers & software engineers to share knowledge, connect, collaborate, learn and experience next-gen technologies. Follow Ivan Shubin Ivan Shubin Follow Written by Ivan Shubin 18 Followers *1 Following Follow Responses (1) See all responses Help Status About Careers Press Blog Privacy Terms Text to speech Teams