Re: SQL challenge

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Thu, 15 Jul 2004 17:51:37 GMT
Message-ID: <pan.2004.07.15.17.52.05.184333@REMOVETHIS.pandora.be>

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

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

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

Received on Thu Jul 15 2004 - 12:51:37 CDT