Re: SQL challenge
Date: Wed, 14 Jul 2004 18:35:49 -0700
Message-ID: <TnlJc.35$P_2.169_at_news.oracle.com>
"Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message
news:pan.2004.07.13.19.21.51.416635_at_REMOVETHIS.pandora.be...
> > Is there an elegant SQL statement? If you say yes, then, I would think
hard
> > finding it:-)
>
> Yes, there is. We (some people in my research group) found it ourselves,
> but we had to make the assumption that not all points are in a single
> plane. Without that assumption things seem to get ugly.
Consider tetrahedron defined by 4 vertices p1, p2, p3, p4. Then, for any
point p it is easily decidable if p belongs to tetrahedron interior or not.
Let's call this predicate as
Inside(p, p1, p2, p3, p4)
This predicate is expected to work in the "extreme" cases when p1=p2 (or
even when p1=p2=p3). Finding closed form expression for Inside(p, p1, p2,
p3, p4) is left as an exercise to the reader.
Lets also introduce a convenience function
R^3 x R^3 -> R^3
Middle(pa,pb)
which returns a point half way between pa and pb.
Then, the query you are after is
select pa.x, pa.y, pa.z,
pb.x, pb.y, pb.z
select 0 from Points p1, Points p2, Points p3, Points p4
where Inside(pa, p1, p2, p3, p4)
select 0 from Points p1, Points p2, Points p3, Points p4
where Inside(pb, p1, p2, p3, p4)
select 0 from Points p1, Points p2, Points p3, Points p4
from Points pa, Points pb
where not exists (
) and not exists (
) and not exists (
The first 2 predicates eliminate all interior points of the polyhedra. The last predicates makes sure we include only those segments that are edges. Received on Thu Jul 15 2004 - 03:35:49 CEST