Re: SQL challenge

"Jan Hidders" <jan.hidders_at_REMOVETHIS.pandora.be> wrote in message news:pan.2004.07.15.17.52.05.184333_at_REMOVETHIS.pandora.be...
> On Wed, 14 Jul 2004 18:35:49 -0700, Mikito Harakiri wrote:
> > 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?

That is p belongs to convex hull of p1 p2 p3 and p4 but does not coincide with the vertices of that hull. This definition spans the cases where tetrahedron is collapsed into planar or linear figure. (I'm not totally happy being forced to exclude vertices from tetrahedron interior, though).

Unlike problem where deciding if a point belongs to convex hull of arbitrary number of vertices involves formulas with summation sign, tetrahedron case has closed form expression.

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

All points on edge, except vertices, belong to interior. If the node p is at the edge of convex hull, then there exist points p1 and p2 such that p is inside collapsed tetrahedron (p1,p1,p2,p2). Received on Thu Jul 15 2004 - 20:45:51 CEST