Volume in SQL

From: Mikito Harakiri <mikharakiri_at_iahu.com>
Date: Thu, 15 Jul 2004 17:07:55 -0700
Message-ID: <ubFJc.42$K9.634@news.oracle.com>

Given a set of 3D points what is the volume of their convex hull?

http://www.math.niu.edu/~rusin/known-math/95/volume.poly gives basic idea how to calculate a volume if we know polyhedron triangulation.

We find triangulation with

select ... from points p1, points p2, points p3 where
 0=(select count(1) from points p where

 p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.y-
 p1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+
 p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.y-

 p.x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+  p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+  p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z  < 0)

Within nested subquery we see the familiar determinant expression that checks if halfspace defined by [oriented] triangle is empty.

However, the result would contain more triangles than it should, as for any triangle p1,p2,p3 we would get half of all permutations:

p1,p2,p3
p3,p1,p2
p2,p3,p1

(Since permutation sign corelates with the orientation of half-space, the
above determinant condition excluded all odd permutations)

We would also have duplications like this

p1,p1,p1
p1,p1,p2
p1,p1,p3

...

According to the http://www.math.niu.edu/~rusin/known-math/95/volume.poly recipe, the determinant of each tripple with duplicated nodes is 0, so we don't really have to worry about those "collapsed" triangles. Therefore, we just aggregate those determinants, which gives concise final answer

select

   sum(p1.x*p2.y*p3.z - p1.x*p3.y*p2.z + p2.x*p3.y*p1.z

• p2.x*p1.y*p3.z + p3.x*p1.y*p2.z - p3.x*p2.y*p1.z )/6/3 from points p1, points p2, points p3 where 0=(select count(1) from points p where p1.x*p.z*p3.y-p1.x*p.y*p3.z-p2.x*p.z*p3.y+p2.x*p.z*p1.yp 1.x*p.z*p2.y+p2.x*p.y*p3.z-p2.x*p.y*p1.z+p1.x*p.y*p2.z+ p3.x*p.z*p2.y-p3.x*p.z*p1.y-p.x*p2.z*p1.y-p.x*p1.z*p3.yp. x*p2.y*p3.z+p.x*p2.y*p1.z+ p.x*p1.y*p3.z-p3.x*p.y*p2.z+ p3.x*p.y*p1.z+p.x*p2.z*p3.y-p3.x*p2.y*p1.z+p3.x*p2.z*p1.y+ p1.x*p2.y*p3.z-p1.x*p2.z*p3.y+p2.x*p1.z*p3.y-p2.x*p1.y*p3.z < 0)

(We had to divide aggregate value by 3, since we count each triangle 3
times).

We test the solution for unit cube

insert into points values (0,0,0);
insert into points values (0,0,1);
insert into points values (0,1,0);
insert into points values (0,1,1);
insert into points values (1,0,0);
insert into points values (1,1,0);
insert into points values (1,0,1);
insert into points values (1/2,1/2,1/2);  // interior point that
                                                              // would be

elimininated by convex hull calc
insert into points values (1,1,1);

which, unfortunately, returns 2 instead of 1.

Obviously, when we calculated triangulation, each square facet has been covered with 4 triangles instead of 2. In general, triangulation is not deterministic, which looks like an enormous problem from SQL perspective. Received on Thu Jul 15 2004 - 19:07:55 CDT