[Haskell-cafe] Coplanarity or Colinearity [Was: low-cost matrix rank?]

[Mike Meyer]

Well, none of the suggested solutions for computing the rank of a matrix really suited my needs, as dragging in something like BLAS introduce more cost than just integrating the bed-and-breakfast library into my own library. So let me try a different track.

My real problem is that I've got a list of points in R3  and want to decide if they determine a plane, meaning they are coplanar but not colinear. Similarly, given a list of points in R2, I want to verify that they aren't colinear. Both of these can be done by converting the list of points to a matrix and finding the rank of the matrix, but I only use the rank function in the definitions of colinear and coplanar.

Maybe there's an easier way to tackle the underlying problems. Anyone got a suggestion for such?

[Ertugrul Söylemez]

> My real problem is that I've got a list of points in R3 and want to
> decide if they determine a plane, meaning they are coplanar but not
> colinear. Similarly, given a list of points in R2, I want to verify
> that they aren't colinear. Both of these can be done by converting the
> list of points to a matrix and finding the rank of the matrix, but I
> only use the rank function in the definitions of colinear and
> coplanar.
>
> Maybe there's an easier way to tackle the underlying problems. Anyone
> got a suggestion for such?

I have written an experimental [implementation] of a Gauss-Jordan solver
and matrix inverter. You might find some use for it. It does work and
is reasonably fast, though not as fast as hmatrix. One advantage is
that you can feed the points incrementally, and it will tell you
immediately when there is no solution. It will also quickly reject
redundant points, even in the presence of rounding errors.

Since I need it often enough I'm going to write a library for
Gauss-Jordan at some point.

[implementation]: http://hub.darcs.net/ertes-m/solvers/browse/Solver/Matrix.hs


Greets,
Ertugrul

[Carter Schonwald]

Yes, solving it directly is probably a better tact.  I believe There's quite a bit of research literature on this out there in the computational geometry literature.  

Have you looked at the CGal c++ lib to check if they have any specialized code for low dimensional geoemtry? CGal or something like it is very likely to have what you want. 

Perhaps more importantly: what are your precision needs?  Cause some of these questions have very real precision trade offs depending on your goals 

[Ertugrul Söylemez]

>> My real problem is that I've got a list of points in R3 and want to
>> decide if they determine a plane, meaning they are coplanar but not
>> colinear. Similarly, given a list of points in R2, I want to verify
>> that they aren't colinear. Both of these can be done by converting the
>> list of points to a matrix and finding the rank of the matrix, but I
>> only use the rank function in the definitions of colinear and
>> coplanar.
>>
>> Maybe there's an easier way to tackle the underlying problems. Anyone
>> got a suggestion for such?
>
> I have written an experimental [implementation] of a Gauss-Jordan solver
> and matrix inverter. You might find some use for it. It does work and
> is reasonably fast, though not as fast as hmatrix. One advantage is
> that you can feed the points incrementally, and it will tell you
> immediately when there is no solution. It will also quickly reject
> redundant points, even in the presence of rounding errors.

I should note: The `solve` function isn't yet written, but it also
doesn't do much. Once you have fed enough relations, the matrix will
already have been reduced to the identity, so you can simply extract the
solutions from the relations.


Greets,
Ertugrul

[Carter Schonwald]

 Shewchuk has a good number of writings in this topic  including this random one i found. page 9 appears to be the releavant one?

http://www.cs.berkeley.edu/~jrs/meshpapers/robnotes.pdf

_______________________________________________
Haskell-Cafe mailing list
Haskel...@haskell.org
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe

[Jerzy Karczmarczuk]

Many people help Mike Meyer:

My real problem is that I've got a list of points in R3  and want to decide if they determine a plane, meaning they are coplanar but not colinear. Similarly, given a list of points in R2, I want to verify that they aren't colinear. Both of these can be done by converting the list of points to a matrix and finding the rank of the matrix, but I only use the rank function in the definitions of colinear and coplanar.

Maybe there's an easier way to tackle the underlying problems. Anyone got a suggestion for such?

I didn't follow this discussion, so I might have missed some essential issues, I apologize then. But if THIS is the problem...

All these powerful universal libraries, with several hundreds of lines of code are important and useful, but if the problem is to find whether a list of pairs (x,y) is collinear or not, I presume that such program as below could do. I am ashamed showing something like that...

colin ((x,y):l) = all (\(c,d)->abs(px*d-py*c)<eps) q where
 ((px,py):q) = [(ax-x,ay-y) | (ax,ay) <- l]

[The iterated subtraction puts the first vector at the origin. eps is the precision; better avoid ==0]

For three dimensions and coplanarity, instead of separating one vector, we need two, in order to compute their skew product. Then, it suffices to verify that all its scalar products with the remaining, vanish; if not, they are not coplanar.

Jerzy Karczmarczuk

[Mike Meyer]

On Sat, Apr 25, 2015 at 10:49 AM, Jerzy Karczmarczuk <jerzy.kar...@unicaen.fr> wrote:

Many people help Mike Meyer:

And I do appreciate it. 

My real problem is that I've got a list of points in R3  and want to decide if they determine a plane, meaning they are coplanar but not colinear. Similarly, given a list of points in R2, I want to verify that they aren't colinear. Both of these can be done by converting the list of points to a matrix and finding the rank of the matrix, but I only use the rank function in the definitions of colinear and coplanar.

Maybe there's an easier way to tackle the underlying problems. Anyone got a suggestion for such?

I didn't follow this discussion, so I might have missed some essential issues, I apologize then. But if THIS is the problem...

All these powerful universal libraries, with several hundreds of lines of code are important and useful, but if the problem is to find whether a list of pairs (x,y) is collinear or not, I presume that such program as below could do. I am ashamed showing something like that...

colin ((x,y):l) = all (\(c,d)->abs(px*d-py*c)<eps) q where
 ((px,py):q) = [(ax-x,ay-y) | (ax,ay) <- l]

[The iterated subtraction puts the first vector at the origin. eps is the precision; better avoid ==0]

That's not far from what I wound up with, except I generalized it to work for both 2d and 3d vectors. And yeah, I clearly got off on the wrong foot when I turned up "test the rank of the matrix" for finding collinearity and coplanarity.

This pretty much solves my problem. Thanks to all who helped.

[Richard A. O'Keefe]

On 26/04/2015, at 1:53 am, Mike Meyer <m...@mired.org> wrote:
> My real problem is that I've got a list of points in R3 and want to decide if they determine a plane, meaning they are coplanar but not colinear. Similarly, given a list of points in R2, I want to verify that they aren't colinear. Both of these can be done by converting the list of points to a matrix and finding the rank of the matrix, but I only use the rank function in the definitions of colinear and coplanar.

To compute the rank of a matrix,
perform elementary row operations
until the matrix is left in echelon form;
the number of nonzero rows remaining in
the reduced matrix is the rank.

(http://www.cliffsnotes.com/math/algebra/linear-algebra/real-euclidean-vector-spaces/the-rank-of-a-matrix)

A matrix is in row echelon form when it
satisfies the following conditions:
* The first non-zero element in each row,
called the leading entry, is 1
* Each leading entry is in a column to
the right of the leading entry in the
previous row
* Rows with all zero elements, if any,
are below rows having a non-zero element.

(http://stattrek.com/matrix-algebra/echelon-transform.aspx)
Row echelon forms aren't unique, but for determining
the rank of a matrix, that doesn't matter.

Code working on a list of points left as an exercise for
the reader.