[elm-discuss] Linear algebra for 2d geometry?

['Rupert Smith' via Elm Discuss]

I need to implement some 2d geometry transformations, and would like to use
3x3 matrices for this. Does anyone have some experience or recommend one
library over another? I don't really need maximum performance at this
stage, the drawing I am rendering will be relatively static and not consist
of a huge number of parts. The output will be SVG.

There is elm-community/linear-algebra, but that only has 4x4 matrices and
is a native module, making it a little harder to add to and publish my own
additions. A 4x4 can always be used where a 3x3 can though.

There is eeue56/elm-flat-matrix, which sounds as though it will be fairly
efficient as a pure Elm implementation.

There is benansell/elm-geometric-transformation, which does what I need for
now. It hides the internal representation and I just had a peek at the
source and it is not a 3x3 matrix but 2x2 with transformation scalars held
separately. Might be nice to work more directly with matrices from the
point of view of being able to extend the work and I am pretty familiar
with linear algebra.

Any others or thoughts?

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
I need to implement some 2d geometry transformations, and would like to
use 3x3 matrices for this. Does anyone have some experience or recommend
one library over another? I don't really need maximum performance at this
stage, the drawing I am rendering will be relatively static and not consist
of a huge number of parts. The output will be SVG.

In the future I might need things algorithms like overlap/collision
detection, convex hull, and 2d graph layouts. I don't know if any of these
things have libraries but if they do, and are based on the same underlying
vector representation as the basic 2d linear algebra, that might help too.

[Matthieu Pizenberg]

I definitely recommend looking at https://github.com/opensolid/geometry
(with it's svg counterpart : https://github.com/opensolid/svg).
I've been using it a bit and it's awesome for what I understand you want.

I've been using eeue56/elm-flat-matrix also but for more "raster" drawings
than "vectorial" stuff. One issue though is that it is based on the elm
core array implementation, which is flawed
<https://github.com/elm-lang/core/issues/649>.

Post by 'Rupert Smith' via Elm Discuss

Post by 'Rupert Smith' via Elm Discuss
I need to implement some 2d geometry transformations, and would like to
use 3x3 matrices for this. Does anyone have some experience or recommend
one library over another? I don't really need maximum performance at this
stage, the drawing I am rendering will be relatively static and not consist
of a huge number of parts. The output will be SVG.

In the future I might need things algorithms like overlap/collision
detection, convex hull, and 2d graph layouts. I don't know if any of these
things have libraries but if they do, and are based on the same underlying
vector representation as the basic 2d linear algebra, that might help too.

['Rupert Smith' via Elm Discuss]

Post by Matthieu Pizenberg
I definitely recommend looking at https://github.com/opensolid/geometry
(with it's svg counterpart : https://github.com/opensolid/svg).
I've been using it a bit and it's awesome for what I understand you want.

Thanks.

I also notice that opensolid/svg is a small library. Would not be hard to
re-implement it over elm-community/typed-svg and remove all those
'toString's.

[Ian Mackenzie]

Post by 'Rupert Smith' via Elm Discuss
I also notice that opensolid/svg is a small library. Would not be hard to
re-implement it over elm-community/typed-svg and remove all those
'toString's.

True - although when I initially wrote opensolid/svg, typed-svg didn't
exist so that wasn't an option. I may switch to it at some point to clean
up the internal implementation code a bit, but it doesn't seem like a
pressing concern since I don't think it would change the external interface
at all. You could certainly already mix and match if you want, e.g.
construct SVG attributes using typed-svg that you can then pass to the
geometry construction functions in opensolid/svg.

['Rupert Smith' via Elm Discuss]

Post by Matthieu Pizenberg
I definitely recommend looking at https://github.com/opensolid/geometry
(with it's svg counterpart : https://github.com/opensolid/svg).
I've been using it a bit and it's awesome for what I understand you want.

This is nice and quite fully featured.

It seems a shame that it is not Matrix based though. For example suppose I
want to do a rotation of a shape, ultimately this comes down to mapping
this vector rotation function over all points defining the shape:

rotateBy : Float -> Vector2d -> Vector2d
rotateBy angle =
let
cosine =
cos angle

sine =
sin angle
in
\(Vector2d ( x, y )) ->
Vector2d ( x * cosine - y * sine, y * cosine + x * sine )

Which means calculating sin and cos again for the same input values for
each point.

If it was Matrix based, you'd calculate the rotation matrix once and then
do just the matrix multiplication part for each point. Due to the
properties of linear algebra, you can combine transformation matrices by
multiplying them all together to capture a more complex transformation in a
single operation.

So, nice library with lots of features, missed chance to work with a better
abstraction.

[Ian Mackenzie]

Post by 'Rupert Smith' via Elm Discuss

Post by Matthieu Pizenberg
I definitely recommend looking at https://github.com/opensolid/geometry
(with it's svg counterpart : https://github.com/opensolid/svg).
I've been using it a bit and it's awesome for what I understand you want.

This is nice and quite fully featured.

Thanks!

Post by 'Rupert Smith' via Elm Discuss
It seems a shame that it is not Matrix based though. For example suppose I
want to do a rotation of a shape, ultimately this comes down to mapping
rotateBy : Float -> Vector2d -> Vector2d
rotateBy angle =
let
cosine =
cos angle
sine =
sin angle
in
\(Vector2d ( x, y )) ->
Vector2d ( x * cosine - y * sine, y * cosine + x * sine )
Which means calculating sin and cos again for the same input values for
each point.

Actually, that implementation is designed specifically to avoid
recalculating sin and cos values. For example, calling Vector2d.rotateBy
someAngle will compute sin and cos values, then return a lambda that
captures those computed values so they don't have to be recomputed every
time the lambda is called. As a result, things like List.map (Vector2d.rotateBy
someAngle) myListOfVectors will only result in sin and cos values being
calculated once (I've tested this with Debug.log calls). (Also, fine point:
OpenSolid distinguishes between points and vectors, so the rotateBy
function above can only be applied to Vector2d values, not Point2d ones.)

Post by 'Rupert Smith' via Elm Discuss
If it was Matrix based, you'd calculate the rotation matrix once and then
do just the matrix multiplication part for each point. Due to the
properties of linear algebra, you can combine transformation matrices by
multiplying them all together to capture a more complex transformation in a
single operation.

The equivalent in OpenSolid is to apply a series of transformations to a
Frame2d
<http://package.elm-lang.org/packages/opensolid/geometry/latest/OpenSolid-Frame2d>
or Frame3d
<http://package.elm-lang.org/packages/opensolid/geometry/latest/OpenSolid-Frame3d>, then
use Point2d.placeIn frame
<http://package.elm-lang.org/packages/opensolid/geometry/latest/OpenSolid-Point2d#placeIn>
or Point3d.placeIn frame
<http://package.elm-lang.org/packages/opensolid/geometry/latest/OpenSolid-Point3d#placeIn> for
each point you care about. Building up a transformed frame by applying
multiple transformations to it is equivalent to building a combined
transformation matrix by multiplication, and calling placeIn is equivalent
to using the final transformation matrix to transform the point, but I
think every individual step is easier to reason about geometrically (you
can visualize moving and rotating frames around, and 'placing' a point
inside a given reference frame). I've explained all this in more detail in a
reply to a GitHub issue
<https://github.com/opensolid/geometry/issues/14#issuecomment-282021044>.

Post by 'Rupert Smith' via Elm Discuss
So, nice library with lots of features, missed chance to work with a
better abstraction.

Ouch =) I've done lots of work with matrix-based libraries, and I've
personally found matrices (and related stuff like quaternions) very
powerful and flexible but also confusion- and error-prone. The OpenSolid
libraries are my attempt to provide a better, more geometrically meaningful
abstraction that still allows you to get good performance.

For what it's worth, I'm just finishing up a small package to allow interop
between OpenSolid and elm-community/linear-algebra - so if you want to
you'll be able to transform OpenSolid points and vectors using a Mat4.

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
So, nice library with lots of features, missed chance to work with a

Post by 'Rupert Smith' via Elm Discuss
better abstraction.

Ouch =) I've done lots of work with matrix-based libraries, and I've
personally found matrices (and related stuff like quaternions) very
powerful and flexible but also confusion- and error-prone. The OpenSolid
libraries are my attempt to provide a better, more geometrically meaningful
abstraction that still allows you to get good performance.

Sorry, my bad and thanks for the explanation. I guess I was a little
fixated on the matrix approach, but with your explanation it is clear that
your approach is at least as good.

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss

Post by 'Rupert Smith' via Elm Discuss
So, nice library with lots of features, missed chance to work with a

Post by 'Rupert Smith' via Elm Discuss
better abstraction.

Ouch =) I've done lots of work with matrix-based libraries, and I've
personally found matrices (and related stuff like quaternions) very
powerful and flexible but also confusion- and error-prone. The OpenSolid
libraries are my attempt to provide a better, more geometrically meaningful
abstraction that still allows you to get good performance.

Sorry, my bad and thanks for the explanation. I guess I was a little
fixated on the matrix approach, but with your explanation it is clear that
your approach is at least as good.

There is potentially an advantage with matrices versus functions. A matrix
could be thought of as a function, in the sense that its values capture a
particular function that can be applied by multiplying by it. So you have
captured the function as a lambda. Lambdas are opaque though, and when
chained together to produce a new function, there is no way to guarantee
that they will combine in such a way that they reduce to the simplest or
most efficient representation; the compiler may do a good job though.

Suppose you have a complex chain of transformations like: scale, rotate,
translate (requires 3x3 matrix for 2d work), mirror. Represent this with
matrices M1, .., M4. The entire transformation can then be captured as a
single matrix Mt = M1 . M2 . M3 . M4. As lambdas, my assumption is the
compiler will not be smart enough to reduce it so neatly, and it will
always be applied as 4 separate operations.

I guess you already know this... :-)

[Ian Mackenzie]

You're exactly right - if you construct a function like the following, I
think it will almost certainly result in four separate transformations
every time it's called:

compositeTransformation1 : Point3d -> Point3d
compositeTransformation1 =
Point3d.scaleAbout Point3d.origin 5 >> Point3d.rotateAround Axis3d.z (degrees
90) >> Point3d.translateBy (Vector3d ( 1, 2, 3 )) >> Point3d.mirrorAcross
Plane3d.xy

In many cases that's fine (if you're only doing it for a handful of points,
for instance), but if you need a more efficient version you can do it using
frames:

transformedFrame : Frame3d
transformedFrame =
Frame3d.xyz |> Frame3d.rotateAround Axis3d.z (degrees 90) |> Frame3d.translateBy
(Vector3d ( 1, 2, 3 ) |> Frame3d.mirrorAcross Plane3d.xy

compositeTransformation2 : Point3d -> Point3d
compositeTransformation2 =
Point3d.scaleAbout Point3d.origin 5 >> Point3d.placeIn transformedFrame

You still need to apply the scaleAbout separately since you can't scale a
Frame3d, but at least scaling is a relatively cheap operation.

In general, yes, using matrices would likely be a bit more efficient, but
you can get pretty close using techniques like the above, and I think the
expressiveness/clarity/flexibility is better. Precision should also be
improved - even disregarding the fact that the linear-algebra package uses
single-precision floats internally (via Float32Array), specialized
transformation functions like scaleAbout can do things like subtract the
given center point, then scale, then re-add the given center point. This
has better numerical stability than the equivalent transformation matrix,
which will effectively scale everything about the origin and then apply a
(potentially large) translation to drag everything back to where it should
be. (Several of these tradeoffs are probably affected by my own goals - I
want opensolid/geometry to be a great general-purpose geometry library, but
I'm personally more focused on stuff like computer-aided design apps where
precision is critical than things like games that have much more strict
performance requirements.)

By the way, the interop package I mentioned earlier has now been published:
http://package.elm-lang.org/packages/opensolid/linear-algebra/latest.

Post by 'Rupert Smith' via Elm Discuss

Post by 'Rupert Smith' via Elm Discuss

Post by 'Rupert Smith' via Elm Discuss
So, nice library with lots of features, missed chance to work with a

Post by 'Rupert Smith' via Elm Discuss
better abstraction.

Ouch =) I've done lots of work with matrix-based libraries, and I've
personally found matrices (and related stuff like quaternions) very
powerful and flexible but also confusion- and error-prone. The OpenSolid
libraries are my attempt to provide a better, more geometrically meaningful
abstraction that still allows you to get good performance.

Sorry, my bad and thanks for the explanation. I guess I was a little
fixated on the matrix approach, but with your explanation it is clear that
your approach is at least as good.

There is potentially an advantage with matrices versus functions. A matrix
could be thought of as a function, in the sense that its values capture a
particular function that can be applied by multiplying by it. So you have
captured the function as a lambda. Lambdas are opaque though, and when
chained together to produce a new function, there is no way to guarantee
that they will combine in such a way that they reduce to the simplest or
most efficient representation; the compiler may do a good job though.
Suppose you have a complex chain of transformations like: scale, rotate,
translate (requires 3x3 matrix for 2d work), mirror. Represent this with
matrices M1, .., M4. The entire transformation can then be captured as a
single matrix Mt = M1 . M2 . M3 . M4. As lambdas, my assumption is the
compiler will not be smart enough to reduce it so neatly, and it will
always be applied as 4 separate operations.
I guess you already know this... :-)

['Rupert Smith' via Elm Discuss]

Post by Ian Mackenzie
In general, yes, using matrices would likely be a bit more efficient, but
you can get pretty close using techniques like the above, and I think the
expressiveness/clarity/flexibility is better.

Thanks for this explanation. Also, I did say in my OP that performance was
not such an important issue for me, as I am only rendering a relatively
static diagram that does not have a huge number of elements in it. I should
also concede that there is no guarantee that using 3x3 matrices would be
faster anyway, it depends on the implementation and the only real way to
know would be to set up a benchmark and measure and compare.

So I decided to go with OpenSolid as it is a very nice library and has a
lot of features.

I also cloned OpenSolid/svg and made a version that renders to
elm-community/typed-svg. Once I have finished converting the docs, tests
and examples you might like to clone it back again and publish it under
OpenSolid/typed-svg? I'll let you know once I get to that stage anyway.

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
I also cloned OpenSolid/svg and made a version that renders to
elm-community/typed-svg.

Fork is here: https://github.com/rupertlssmith/svg

[Ian Mackenzie]

Post by 'Rupert Smith' via Elm Discuss
Thanks for this explanation. Also, I did say in my OP that performance was
not such an important issue for me, as I am only rendering a relatively
static diagram that does not have a huge number of elements in it. I should
also concede that there is no guarantee that using 3x3 matrices would be
faster anyway, it depends on the implementation and the only real way to
know would be to set up a benchmark and measure and compare.
So I decided to go with OpenSolid as it is a very nice library and has a
lot of features.

Great! Let me know if you run into anything. There are definitely lots of
places where the implementation could be made more efficient - to start I
implemented everything in the cleanest/simplest way I could think of, but
over time I'm planning to go back and do some optimizations to avoid
unnecessary object allocations and function calls. I've already done this
in a few places, but if you do run into any performance bottlenecks let me
know so I know where to focus next. (Apologies for the late reply, I was at
a conference for the last couple of days...)

Post by 'Rupert Smith' via Elm Discuss
I also cloned OpenSolid/svg and made a version that renders to
elm-community/typed-svg. Once I have finished converting the docs, tests
and examples you might like to clone it back again and publish it under
OpenSolid/typed-svg? I'll let you know once I get to that stage anyway.

I confess I'm still not sure exactly why a separate typed-svg version is
necessary...since the TypedSvg.Core.Svg and TypedSvg.Core.Attribute are
still just aliases for VirtualDom.Node and VirtualDom.Property respectively
(instead of being new opaque types or something), you can already mix
typed-svg and opensolid/svg elements/attributes freely without any kind of
conversion or anything - see https://ellie-app.com/39pwNnwDzcqa1/2 for an
example. To me the only difference is that a typed-svg version of
opensolid/svg would depend on elm-community/typed-svg instead of
elm-lang/svg and the internal implementation would be slightly different -
but the exposed APIs would have exactly the same types. Am I missing
something?

['Rupert Smith' via Elm Discuss]

Post by 'Rupert Smith' via Elm Discuss
I also cloned OpenSolid/svg and made a version that renders to

Post by 'Rupert Smith' via Elm Discuss
elm-community/typed-svg. Once I have finished converting the docs, tests
and examples you might like to clone it back again and publish it under
OpenSolid/typed-svg? I'll let you know once I get to that stage anyway.

I confess I'm still not sure exactly why a separate typed-svg version is
necessary...since the TypedSvg.Core.Svg and TypedSvg.Core.Attribute are
still just aliases for VirtualDom.Node and VirtualDom.Property
respectively (instead of being new opaque types or something), you can
already mix typed-svg and opensolid/svg elements/attributes freely
without any kind of conversion or anything - see
https://ellie-app.com/39pwNnwDzcqa1/2 for an example.

Thanks for pointing that out. I swapped my code over to opensolid/svg and
it all compiled and runs fine. In which case, perhaps the thing to do might
be for me to create a little pull request adding a statement and short
example to the docs for opensolid/svg to explain that it also works with
typed-svg.

[Zinggi]

There is also my little library
<http://package.elm-lang.org/packages/Zinggi/elm-webgl-math/latest>, you
might find it useful.

Post by 'Rupert Smith' via Elm Discuss
I need to implement some 2d geometry transformations, and would like to
use 3x3 matrices for this. Does anyone have some experience or recommend
one library over another? I don't really need maximum performance at this
stage, the drawing I am rendering will be relatively static and not consist
of a huge number of parts. The output will be SVG.
There is elm-community/linear-algebra, but that only has 4x4 matrices and
is a native module, making it a little harder to add to and publish my own
additions. A 4x4 can always be used where a 3x3 can though.
There is eeue56/elm-flat-matrix, which sounds as though it will be fairly
efficient as a pure Elm implementation.
There is benansell/elm-geometric-transformation, which does what I need
for now. It hides the internal representation and I just had a peek at the
source and it is not a 3x3 matrix but 2x2 with transformation scalars held
separately. Might be nice to work more directly with matrices from the
point of view of being able to extend the work and I am pretty familiar
with linear algebra.
Any others or thoughts?