Scale-agnostic, differentiable, co-planarity measure

I am looking for an (almost everywhere) differentiable function f(p1, p2, p3, p4) that gi开发者_运维知识库ven four points will give me a scale-agnostic measure for co-planarity. It is zero if the four points lie on the same plane and positive otherwise. Scale-agnostic means that, when I uniformly scale all points the planarity measure will return the same.

I came up with something that is quite complex and not easy to optimize. Define u=p2-p1, v=p3-p1, w=p4-p1. Then the planarity measure is:

[(u x v) * w]² / (|u x v|² |w|²)

where x means cross product and '*' means dot product.

The numerator is simply (the square of) the volume of the tetrahedron defined by the four points, and the denominator is a normalizing factor that makes this measure become simply the cosine of an angle. Because angles do not changed under uniform scale, this function satisfies all my requirements.

Does anybody know of something simpler?

Alex.

Edit:

I eventually used an Augmented Lagrangian method to perform optimization, so I don't need it to be scale agnostic. Just using the constraint (u x v) * w = 0 is enough, as the optimization procedure finds the correct Lagrange multiplier to compensate for the scale.

Your methods seems ok, I'd do something like this for efficient implementation:

• Take u, v, w as you did
• Normalize them: various tricks exist to evaluate the inverse square root efficiently with whatever precision you want, like this jewel. Most modern processors have builtins for this operation.
• Take f = |det(u, v, w)| ( = (u x v) . w ). There are fast direct implementations for 3x3 matrices; see @batty's answer to this question.

This amounts to what you do without the squares. It is still homogeneous and almost everywhere differentiable. Take the square of the determinant if you want something differentiable everywhere.

EDIT: @phkahler implicitly suggested using the ratio of the radius of the inscribed sphere to the radius of the circumscribed sphere as a measure of planarity. This is a bounded differentiable function of the points, invariant by scaling. However, this is at least as difficult to compute as what you (and I) suggest. Especially computing the radius of the circumscribed sphere is very sensitive to roundoff errors.

A measure that should be symmetric with respect to point reorderings is:

((u x v).w)^2/(|u||v||w||u-v||u-w||v-w|)

which is proportional to the volume of the tetrahedron squared divided by all 6 edge lengths. It is not simpler than your formula or Alexandre C.'s, but it is not much more complicated. However, it does become unnecessarily singular when any two points coincide.

A better-behaved, order-insensitive formula is:

let a = u x v
    b = v x w
    c = w x u
(a.w)^2/(|a| + |b| + |c| + |a+b+c|)^3

which is something like the volume of the tetrahedron divided by the surface area, but raised to appropriate powers to make the whole thing scale-insensitive. This is also a bit more complex than your formula, but it works unless all 4 points are collinear.

How about

|(u x v) * w| / |u|^3

(and you can change |x| to (x)^2 if you think it's simpler).