Oracle FAQ Your Portal to the Oracle Knowledge Grid
 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US

Home -> Community -> Usenet -> comp.databases.theory -> Re: SQL challenge

# Re: SQL challenge

From: Jan Hidders <jan.hidders_at_REMOVETHIS.pandora.be>
Date: Thu, 15 Jul 2004 21:34:01 GMT
Message-Id: <pan.2004.07.15.21.34.32.322571@REMOVETHIS.pandora.be>

On Thu, 15 Jul 2004 13:20:49 -0700, Mikito Harakiri wrote:
>

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) )
```
AND
NOT EXISTS
( SELECT *
```      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 )
```
)
AND
EXISTS
( SELECT *
```      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
Received on Thu Jul 15 2004 - 16:34:01 CDT

Original text of this message

 HOME | ASK QUESTION | ADD INFO | SEARCH | E-MAIL US