0

I am looking for an (almost everywhere) differentiable function f(p1, p2, p3, p4) that given 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.

Alex Shtoff
  • 2,520
  • 1
  • 25
  • 53
  • This looks more a question for http://math.stackexchange.com/ – 6502 Feb 02 '11 at 14:54
  • 1
    @Alex Seems that your measure is the right one ... – Dr. belisarius Feb 02 '11 at 15:02
  • @6502 you are probably right, although I believe that there are enough programmers that write 3D graphics software (usually mesh editing/modelling) and can help me with this issue. – Alex Shtoff Feb 02 '11 at 15:03
  • Why don't you scale by the product of the (squared) norms ? And why do you square everything ? Are you sure you really want differentiability at the coplanar points ? With absolute values instead of squares, it is still homogeneous and almost everywhere differentiable. – Alexandre C. Feb 02 '11 at 16:30
  • I would suggest that the function should return the same result for any ordering of the input points. Might I suggest the volume of the tetrahedron divided by some function of the edge lengths? Also look at the measures used in tetrahedral mesh generation - they try to avoid planarity so they have measures. – phkahler Feb 02 '11 at 16:31
  • @phkahler: good point, I edited my answer. However I think it is harder to optimize, even if there are (numerically difficult wrt. roundoff error) closed form formulas for these measures. – Alexandre C. Feb 02 '11 at 16:35
  • Also (u, v, w) -> u * (v x w) is linear in each argument (it is the determinant of u, v, and w), so dividing by the product of the norms yields something invariant by scaling. – Alexandre C. Feb 02 '11 at 16:50

3 Answers3

2

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.

Community
  • 1
  • 1
Alexandre C.
  • 55,948
  • 11
  • 128
  • 197
1

How about

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

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

Beta
  • 96,650
  • 16
  • 149
  • 150
1

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.

comingstorm
  • 25,557
  • 3
  • 43
  • 67
  • I like the volume to area ratio, but how is |a+b+c| the area of the 4th side? – phkahler Feb 03 '11 at 14:00
  • The area of the 4th side is proportional to `|(u-v)x(v-w)|`. That expands to `|(u x v) - (u x w) - (v x v) + (v x w)|` which reduces to `|a - (-c) - 0 + b|` – comingstorm Feb 09 '11 at 02:28