Volume in SQL
Date: Thu, 15 Jul 2004 17:07:55 -0700
Message-ID: <ubFJc.42$K9.634_at_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
where0=(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 beelimininated 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 Fri Jul 16 2004 - 02:07:55 CEST