Re: SQL challenge

On Thu, 15 Jul 2004 13:20:49 -0700, Mikito Harakiri wrote:
>
> Thank you, Jan. Could you please post the "official" answer?

This is our current solution, which doesn't work when all points are on a line or in a plane. The relation with points is called R2R here.

SELECT R1.x AS x1, R1.y AS y1, R1.z AS z1,

       R2.x AS x2, R2.y AS y2, R2.z AS z2 FROM R3R R1,R3R R2
WHERE ( R1.x < R2.x

        OR (R1.x = R2.x AND R1.y < R2.y)
        OR (R1.x = R2.x AND R1.y = R2.y AND R1.z < R2.z) )

      FROM R3R R0
      WHERE (R2.x-R1.x)*(R0.y-R1.y)=(R0.x-R1.x)*(R2.y-R1.y)
        AND (R2.x-R1.x)*(R0.z-R1.z)=(R0.x-R1.x)*(R2.z-R1.z)
        AND (R2.y-R1.y)*(R0.z-R1.z)=(R0.y-R1.y)*(R2.z-R1.z)
        AND ( (R1.x-R0.x)*(R2.x-R0.x)>0
              OR (R1.y-R0.y)*(R2.y-R0.y)>0
              OR (R1.z-R0.z)*(R2.z-R0.z)>0 )

      FROM R3R R3, R3R R4
      WHERE 
       ( ((R1.y-R2.y)*(R1.z-R3.z)-(R1.z-R2.z)*(R1.y-R3.y))*(R4.x-R1.x) +
         ((R1.z-R2.z)*(R1.x-R3.x)-(R1.x-R2.x)*(R1.z-R3.z))*(R4.y-R1.y) +
         ((R1.x-R2.x)*(R1.y-R3.y)-(R1.y-R2.y)*(R1.x-R3.x))*(R4.z-R1.z) <>0
       )
       AND
        ( NOT EXISTS
            ( SELECT *
              FROM R3R R5
              WHERE
                ((R1.y-R2.y)*(R1.z-R3.z)-(R1.z-R2.z)*(R1.y-R3.y))*
                                                        (R5.x-R1.x) +
                ((R1.z-R2.z)*(R1.x-R3.x)-(R1.x-R2.x)*(R1.z-R3.z))*
                                                        (R5.y-R1.y) +
                ((R1.x-R2.x)*(R1.y-R3.y)-(R1.y-R2.y)*(R1.x-R3.x))*
                                                        (R5.z-R1.z)>0
            )
          OR
          NOT EXISTS
            ( SELECT *
              FROM R3R R5
              WHERE
                ((R1.y-R2.y)*(R1.z-R3.z)-(R1.z-R2.z)*(R1.y-R3.y))*
                                                        (R5.x-R1.x) +
                ((R1.z-R2.z)*(R1.x-R3.x)-(R1.x-R2.x)*(R1.z-R3.z))*
                                                        (R5.y-R1.y) +
                ((R1.x-R2.x)*(R1.y-R3.y)-(R1.y-R2.y)*(R1.x-R3.x))*
                                                        (R5.z-R1.z)<0
            )
        )
        AND
        ( NOT EXISTS
            ( SELECT *
              FROM R3R R5
              WHERE
                ((R1.y-R2.y)*(R1.z-R4.z)-(R1.z-R2.z)*(R1.y-R4.y))*
                                                        (R5.x-R1.x) +
                ((R1.z-R2.z)*(R1.x-R4.x)-(R1.x-R2.x)*(R1.z-R4.z))*
                                                        (R5.y-R1.y) +
                ((R1.x-R2.x)*(R1.y-R4.y)-(R1.y-R2.y)*(R1.x-R4.x))*
                                                        (R5.z-R1.z)>0
            )
          OR
          NOT EXISTS
            ( SELECT *
              FROM R3R R5
              WHERE
                ((R1.y-R2.y)*(R1.z-R4.z)-(R1.z-R2.z)*(R1.y-R4.y))*
                                                        (R5.x-R1.x) +
                ((R1.z-R2.z)*(R1.x-R4.x)-(R1.x-R2.x)*(R1.z-R4.z))*
                                                        (R5.y-R1.y) +
                ((R1.x-R2.x)*(R1.y-R4.y)-(R1.y-R2.y)*(R1.x-R4.x))*
                                                        (R5.z-R1.z)<0
            )
        )

The first NOT EXISTS eliminates edges that are "too short". The remaing conditions essentially test if there are two faces in the convex hull that are (1) not in the same plane and (2) of which the edge in question is an intersection. It's the (1) part that takes care of the edges inside a face.

> Interestingly, you didn't ask the "simplest" question about convex hull. The
> more basic question would be "Find H-polyhedron", or "Remove all the
> interior nodes". In a word, faces and vertices are fundamental to convex
> hull problem, and edges are not.

Agreed. The reason we didn't was simply because we thought that would make it too easy. (Some of the members of our group are rather good at these things. Much much better than I am.) If the point had been to demonstrate the close relationship between SQL and geometry then we might have.

> For example, matrix
> multiplication is just an elegant group-by statement.

The stage is yours. :-)

• Jan Hidders