Re: SQL challenge

On Wed, 14 Jul 2004 18:35:49 -0700, Mikito Harakiri wrote:

> "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

>> > 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.

Could you be a bit more precise here? What if p1 p2 p3 and p4 are on a single line, what does it then exactly mean to be inside? I assume no node would be inside then, right? Or is a node on the edges of the tetrahedron also "inside". And the corner points, are these inside?

> 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
> from Points pa, Points pb
> where not exists (
> select 0 from Points p1, Points p2, Points p3, Points p4
> where Inside(pa, p1, p2, p3, p4)
> ) and not exists (
> select 0 from Points p1, Points p2, Points p3, Points p4
> where Inside(pb, p1, p2, p3, p4)
> ) and not exists (
> select 0 from Points p1, Points p2, Points p3, Points p4
> where Inside(Middle(pa,pb), p1, p2, p3, p4)
> and pa != p1 and pa != p2 and pa != p3 and pa != p4
> and pb != p1 and pb != p2 and pb != p3 and pb != p4
> )
>
> The first 2 predicates eliminate all interior points of the polyhedra. The
> last predicates makes sure we include only those segments that are edges.

What if there is a node in the middle of an edge of the convex hull? By which predicate is it removed? I'm not sure because I'm not clear on your definition of 'Inside'.

• Jan Hidders