Transformation to get rid of collinear points

问题:

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?

回答1:

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[.

回答2:

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