Hi, I'm writing a program to solve a geometry problem.
My algorithm doesn't treat collinear point very well.
Is there any transformation I can apply to the points to get rid of the collinearity?
+6
A:
Then I think that noise might actually be the solution. As I wrote in the comment above
One way to remove colinearity is simply to add some noise to each point, i.e. (x, y, z) ↦ (x + 0.01*(random() - 0.5), y + 0.01*(random() - 0.5), z + 0.01(random() - 0.5)) if random() returns a random real number in [0, 1[.
Andreas Rejbrand
2010-05-30 12:22:26
You can always work in 4 dimensions and add the noise along the 4th axis. For some algorithms this will fix the problems with little perceptible change after projecting back to 3 dimensions. But with no clue as to what the original problem is, who knows if this is appropriate.
2010-05-31 14:21:44
A:
If you are working with a lot of point sets, adding noise to every set may solve the problem in one set, but create it in another.
If that is the case, you can test the colinearity before applying the noise.
The colinearity condition is:
x1 y1 1
det x2 y2 1 = 0
x3 y3 1
belisarius
2010-05-31 20:25:37
Computing determinants is slow. A better test is to form the two translation vectors v1 := (x3, y3) - (x2, y2) and v2 := (x2, y2) - (x1, y1) and test if they are parallell, i.e. if v1 = k v2.v1 and v2 are parallell if and only if (v1, v2) = |v1| |v2|.
Andreas Rejbrand
2010-05-31 20:55:39
@ Andreas Determinants are slow in the general case. Here you need only 5 sums and three multiplications.Your suggestion involves (I may be wrong) 4 sums one division and one multiplication ... not sooo different! :)
belisarius
2010-05-31 21:20:15
@belisarius: No, I realised that after five minutes, and then the comment is read-only. But I think my approach is slightly easier to implement, at least if the OP is not so familiary with determinants.
Andreas Rejbrand
2010-05-31 21:24:18
Yet another option is that equality holds in the triangle inequality applied to the two translation vectors if and only if the three points are colinear.
Andreas Rejbrand
2010-06-01 12:31:15
It seems that four sums, two multiplications and a comparison is the most economic (y2-y3) (x1-x3) = (y1-y3) (x2-x3)The geometrical interpretation is that the slopes of the two straight lines from one point to the others are equal
belisarius
2010-06-02 02:12:40