Untitled

-- Given a relation R1, with three attributes X, Y and Z, each with a
-- 'number'-domain. R1 represents different points in the 3-dimensional
-- Euclidean space. Express in SQL a query that gives the Convex Hull of
-- the points of R1. Each point of the Convex Hull must be
-- non-redundant.
SELECT *
FROM R1 E1
WHERE
---------------------
-- Case of 1 point --
--v10----------------
(
( SELECT COUNT(*)
FROM R1
)
= 1
)
--^10--
OR
--------------------
-- Case of 1 line --
--v20---------------
(
--v21-- Not one point
(
( SELECT COUNT(*)
FROM R1
)
<> 1
)
--^21--
AND
--v22-- All points on one line
(
NOT EXISTS
( SELECT *
FROM R1 E2, R1 E3
WHERE
------- E1,E2,E3 are not on one line
(
(
------- Projection on X,Y not on one line
(((E1.X-E3.X)*(E2.Y-E3.Y))-((E2.X-E3.X)*(E1.Y-E3.Y))) <> 0
)
OR
(
------- Projection on X,Z not on one line
(((E1.X-E3.X)*(E2.Z-E3.Z))-((E2.X-E3.X)*(E1.Z-E3.Z))) <> 0
)
OR
(
------- Projection on Y,Z not on one line
(((E1.Y-E3.Y)*(E2.Z-E3.Z))-((E2.Y-E3.Y)*(E1.Z-E3.Z))) <> 0
)
)
)
)
--^22--
AND
--v23-- All points on the same side of E1
(
NOT EXISTS
( SELECT *
FROM R1 E2, R1 E3
WHERE
------- E2 and E3 are on a different side of E1
((E1.X-E2.X)*(E1.X-E3.X) < 0)
OR
((E1.Y-E2.Y)*(E1.Y-E3.Y) < 0)
OR
((E1.Z-E2.Z)*(E1.Z-E3.Z) < 0)
)
)
--^23--
)
--^20--
OR
---------------------
-- Case of 1 plane --
--v30----------------
(
--v31-- Not one point
(
( SELECT COUNT(*)
FROM R1
)
<> 1
)
--^31--
AND
--v32-- Not all points on one line
(
EXISTS
( SELECT *
FROM R1 E2, R1 E3
WHERE
------- E1,E2,E3 are not on one line
(
(
------- Projection on X,Y not on one line
(((E1.X-E3.X)*(E2.Y-E3.Y))-((E2.X-E3.X)*(E1.Y-E3.Y))) <> 0
)
OR
(
------- Projection on X,Z not on one line
(((E1.X-E3.X)*(E2.Z-E3.Z))-((E2.X-E3.X)*(E1.Z-E3.Z))) <> 0
)
OR
(
------- Projection on Y,Z not on one line
(((E1.Y-E3.Y)*(E2.Z-E3.Z))-((E2.Y-E3.Y)*(E1.Z-E3.Z))) <> 0
)
)
)
)
--^32--
AND
--v33-- All points in one plane
(
NOT EXISTS
( SELECT *
FROM R1 E2, R1 E3, R1 E4
WHERE
------- E1,E2,E3,E4 are not in one plane
(
(E2.X-E1.X)*((E3.Y-E1.Y)*(E4.Z-E1.Z)-
(E4.Y-E1.Y)*(E3.Z-E1.Z))
-
(E2.Y-E1.Y)*((E3.X-E1.X)*(E4.Z-E1.Z)-
(E3.Z-E1.Z)*(E4.X-E1.X))
+
(E2.Z-E1.Z)*((E3.X-E1.X)*(E4.Y-E1.Y)-
(E3.Y-E1.Y)*(E4.X-E1.X)) <> 0
)
)
)
--^33--
AND
--v34--
(
------- there exist two points P1,P2 with:
------- E1,P1,P2 are pairwise different
------- all points lie on the same side of the line E1,P1
------- all points lie on the same side of the line E1,P2
------- E1,P1,P2 are not on one line
EXISTS
(
SELECT *
FROM R1 P1,R1 P2
WHERE
------- P1,P2 different
((P1.X<>P2.X) OR (P1.Y<>P2.Y) OR (P1.Z<>P2.Z))
AND
------- E1,P1 different
((E1.X<>P1.X) OR (E1.Y<>P1.Y) OR (E1.Z<>P1.Z))
AND
------- E1,P2 different
((E1.X<>P2.X) OR (E1.Y<>P2.Y) OR (E1.Z<>P2.Z))
AND
NOT EXISTS
(
SELECT *
FROM R1 Q1,R1 Q2
WHERE
------- Q1,Q2 on a different side of the line E1,P1
( ((E1.X-Q1.X)*(P1.Y-Q1.Y)-(P1.X-Q1.X)*(E1.Y-Q1.Y))*
((E1.X-Q2.X)*(P1.Y-Q2.Y)-(P1.X-Q2.X)*(E1.Y-Q2.Y)) < 0
OR
((E1.X-Q1.X)*(P1.Z-Q1.Z)-(P1.X-Q1.X)*(E1.Z-Q1.Z))*
((E1.X-Q2.X)*(P1.Z-Q2.Z)-(P1.X-Q2.X)*(E1.Z-Q2.Z)) < 0
OR
((E1.Y-Q1.Y)*(P1.Z-Q1.Z)-(P1.Y-Q1.Y)*(E1.Z-Q1.Z))*
((E1.Y-Q2.Y)*(P1.Z-Q2.Z)-(P1.Y-Q2.Y)*(E1.Z-Q2.Z)) < 0
)
)
AND
NOT EXISTS
(
SELECT *
FROM R1 Q1,R1 Q2
WHERE
------- Q1,Q2 on a different side of the line E1,P2
( ((E1.X-Q1.X)*(P2.Y-Q1.Y)-(P2.X-Q1.X)*(E1.Y-Q1.Y))*
((E1.X-Q2.X)*(P2.Y-Q2.Y)-(P2.X-Q2.X)*(E1.Y-Q2.Y)) < 0
OR
((E1.X-Q1.X)*(P2.Z-Q1.Z)-(P2.X-Q1.X)*(E1.Z-Q1.Z))*
((E1.X-Q2.X)*(P2.Z-Q2.Z)-(P2.X-Q2.X)*(E1.Z-Q2.Z)) < 0
OR
((E1.Y-Q1.Y)*(P2.Z-Q1.Z)-(P2.Y-Q1.Y)*(E1.Z-Q1.Z))*
((E1.Y-Q2.Y)*(P2.Z-Q2.Z)-(P2.Y-Q2.Y)*(E1.Z-Q2.Z)) < 0
)
)
AND
--v35-- E1,P1,P2 not on a line
(
(
(((E1.X-P2.X)*(P1.Y-P2.Y))-((P1.X-P2.X)*(E1.Y-P2.Y))) <> 0
)
OR
(
(((E1.X-P2.X)*(P1.Z-P2.Z))-((P1.X-P2.X)*(E1.Z-P2.Z))) <> 0
)
OR
(
(((E1.Y-P2.Y)*(P1.Z-P2.Z))-((P1.Y-P2.Y)*(E1.Z-P2.Z))) <> 0
)
)
--^35--
)
)
--^34--
)
--^30--
OR
------------------
-- General case --
--v40-------------
(
--v41-- Not one point
(
( SELECT COUNT(*)
FROM R1
)
<> 1
)
--^41--
AND
--v42-- Not all points on one line
(
EXISTS
( SELECT *
FROM R1 E2, R1 E3
WHERE
------- E1,E2,E3 are not on one line
(
(
------- Projection on X,Y not on one line
(((E1.X-E3.X)*(E2.Y-E3.Y))-((E2.X-E3.X)*(E1.Y-E3.Y))) <> 0
)
OR
(
------- Projection on X,Z not on one line
(((E1.X-E3.X)*(E2.Z-E3.Z))-((E2.X-E3.X)*(E1.Z-E3.Z))) <> 0
)
OR
(
------- Projection on Y,Z not on one line
(((E1.Y-E3.Y)*(E2.Z-E3.Z))-((E2.Y-E3.Y)*(E1.Z-E3.Z))) <> 0
)
)
)
)
--^42--
AND
--v43-- Not all points in one plane
(
EXISTS
( SELECT *
FROM R1 E2, R1 E3, R1 E4
WHERE
(
(E2.X-E1.X)*((E3.Y-E1.Y)*(E4.Z-E1.Z)-
(E4.Y-E1.Y)*(E3.Z-E1.Z))
-
(E2.Y-E1.Y)*((E3.X-E1.X)*(E4.Z-E1.Z)-
(E3.Z-E1.Z)*(E4.X-E1.X))
+
(E2.Z-E1.Z)*((E3.X-E1.X)*(E4.Y-E1.Y)-
(E3.Y-E1.Y)*(E4.X-E1.X)) <> 0
)
)
)
--^43--
AND
( EXISTS
( SELECT *
------- select a point E2 different from E1 such that no point P is
--v44-- on 1 line with E1 and E2 and outside [E1,E2]
FROM R1 E2
WHERE
------- E2 different from E1
( (E1.X<>E2.X) OR (E1.Y<>E2.Y) OR (E1.Z<>E2.Z) )
AND
--v45-- no point P that is on 1 line with E1 and E2 is outside [E1,E2]
( NOT EXISTS
( SELECT *
FROM R1 P
WHERE
(
(
------- E1,E2,P that is on 1 line
(
------- Projection on X,Y on one line
(((E1.X-P.X)*(E2.Y-P.Y))-
((E2.X-P.X)*(E1.Y-P.Y))) = 0
)
AND
(
------- Projection on X,Z on one line
(((E1.X-P.X)*(E2.Z-P.Z))-
((E2.X-P.X)*(E1.Z-P.Z))) = 0
)
AND
(
------- Projection on Y,Z on one line
(((E1.Y-P.Y)*(E2.Z-P.Z))-
((E2.Y-P.Y)*(E1.Z-P.Z))) = 0
)
)
AND
------- P is outside [E1,E2]
(
((P.X-E1.X)*(P.X-E2.X) > 0)
OR
((P.Y-E1.Y)*(P.Y-E2.Y) > 0)
OR
((P.Z-E1.Z)*(P.Z-E2.Z) > 0)
)
)
)
)
--^45--
AND
------- there exist two points P1, P2 with:
------- E1,E2,P1 are not on 1 line
------- all points lie on the same side of the plane E1,E2,P1
------- E1,E2,P2 are not on one line
------- all points lie on the same side of the plane E1,E2,P2
--v46-- E1,E2,P1,P2 are not in one plane
( EXISTS
(
------- there exist two points P1, P2 with:
SELECT *
FROM R1 P1, R1 P2
WHERE
--v47-- E1,E2,P1 are not on 1 line
(
(
------- Projection on X,Y on one line
(((E1.X-P1.X)*(E2.Y-P1.Y))-
((E2.X-P1.X)*(E1.Y-P1.Y))) <> 0
)
OR
(
------- Projection on X,Z on one line
(((E1.X-P1.X)*(E2.Z-P1.Z))-
((E2.X-P1.X)*(E1.Z-P1.Z))) <> 0
)
OR
(
------- Projection on Y,Z on one line
(((E1.Y-P1.Y)*(E2.Z-P1.Z))-
((E2.Y-P1.Y)*(E1.Z-P1.Z))) <> 0
)
)
--^47--
AND
--v48-- all points lie on the same side of the plane E1,E2,P1
(
NOT EXISTS
--v49--
(
SELECT *
FROM R1 Q1, R1 Q2
WHERE
--v50-- Q1 and Q2 lie on different sides of the plane E1,E2,P1
(
--v51--
(
(E1.X-Q1.X)*
((E2.Y-Q1.Y)*(P1.Z-Q1.Z)-
(P1.Y-Q1.Y)*(E2.Z-Q1.Z))
-
(E1.Y-Q1.Y)*
((E2.X-Q1.X)*(P1.Z-Q1.Z)-
(E2.Z-Q1.Z)*(P1.X-Q1.X))
+
(E1.Z-Q1.Z)*
((E2.X-Q1.X)*(P1.Y-Q1.Y)-
(E2.Y-Q1.Y)*(P1.X-Q1.X))
) *
--^51--
--v52--
(
(E1.X-Q2.X)*
((E2.Y-Q2.Y)*(P1.Z-Q2.Z)-
(P1.Y-Q2.Y)*(E2.Z-Q2.Z))
-
(E1.Y-Q2.Y)*
((E2.X-Q2.X)*(P1.Z-Q2.Z)-
(E2.Z-Q2.Z)*(P1.X-Q2.X))
+
(E1.Z-Q2.Z)*
((E2.X-Q2.X)*(P1.Y-Q2.Y)-
(E2.Y-Q2.Y)*(P1.X-Q2.X))
)
--^52--
< 0
)
--^50--
)
--^49--
)
--^48--
AND
--v53-- E1,E2,P2 are not on 1 line
(
(
------- Projection on X,Y on one line
(((E1.X-P2.X)*(E2.Y-P2.Y))-
((E2.X-P2.X)*(E1.Y-P2.Y))) <> 0
)
OR
(
------- Projection on X,Z on one line
(((E1.X-P2.X)*(E2.Z-P2.Z))-
((E2.X-P2.X)*(E1.Z-P2.Z))) <> 0
)
OR
(
------- Projection on Y,Z on one line
(((E1.Y-P2.Y)*(E2.Z-P2.Z))-
((E2.Y-P2.Y)*(E1.Z-P2.Z))) <> 0
)
)
--^53--
AND
--v54-- all points lie on the same side of the plane E1,E2,P2
(
NOT EXISTS
--v55--
(
SELECT *
FROM R1 Q1, R1 Q2
WHERE
--v56-- Q1 and Q2 lie on different sides of the plane E1,E2,P2
(
--v57--
(
(E1.X-Q1.X)*
((E2.Y-Q1.Y)*(P2.Z-Q1.Z)-
(P2.Y-Q1.Y)*(E2.Z-Q1.Z))
-
(E1.Y-Q1.Y)*
((E2.X-Q1.X)*(P2.Z-Q1.Z)-
(E2.Z-Q1.Z)*(P2.X-Q1.X))
+
(E1.Z-Q1.Z)*
((E2.X-Q1.X)*(P2.Y-Q1.Y)-
(E2.Y-Q1.Y)*(P2.X-Q1.X))
) *
--^57--
--v58--
(
(E1.X-Q2.X)*
((E2.Y-Q2.Y)*(P2.Z-Q2.Z)-
(P2.Y-Q2.Y)*(E2.Z-Q2.Z))
-
(E1.Y-Q2.Y)*
((E2.X-Q2.X)*(P2.Z-Q2.Z)-
(E2.Z-Q2.Z)*(P2.X-Q2.X))
+
(E1.Z-Q2.Z)*
((E2.X-Q2.X)*(P2.Y-Q2.Y)-
(E2.Y-Q2.Y)*(P2.X-Q2.X))
)
--^58--
< 0
)
--^56--
)
--^55--
)
--^54--
AND
--v59-- E1,E2,P1,P2 are not in one plane
(
(
(E2.X-E1.X)*
((P1.Y-E1.Y)*(P2.Z-E1.Z)-
(P2.Y-E1.Y)*(P1.Z-E1.Z))
-
(E2.Y-E1.Y)*
((P1.X-E1.X)*(P2.Z-E1.Z)-
(P1.Z-E1.Z)*(P2.X-E1.X))
+
(E2.Z-E1.Z)*
((P1.X-E1.X)*(P2.Y-E1.Y)-
(P1.Y-E1.Y)*(P2.X-E1.X))
)
<> 0
)
--^59--
)
)
--^46--
)
)
--^44--
)
--^40--
;