[postgis-users] Problem finding intersection of LineString and BOX3D?

[Dave Blasby]

Mark Cave-Ayland wrote:
> Thanks for your reply. I tried your new select statement but it doesn't work
> for lines at all :( It would be useful to get the cohen-sutherland algorithm
> working as it seems really fast - what's the easiest way to step through the
> routine while it tests a linestring?

Oops, forgot to convert the bounding box to a polygon - use the
envelope() function.

 SELECT name FROM linetesttab WHERE geom &&
setSRID('BOX3D(247531.5250251
  52556.353020652,247567.13124875 52591.959244305)'::BOX3D,
 find_srid('','linetesttab','geom') ) AND distance(geom,
  envelope(setSRID('BOX3D(247531.5250251 52556.353020652,247567.13124875
 52591.959244305)'::BOX3D, find_srid('', 'linetesttab', 'geom')))) =0

I havent looked at the C-S for a while, but there are references online
for
it.  

Basically, it works by subdividing space based 2 horizontal and 2
verticle lines that make up the box.  Codes are assigning
to the various sub-spaces:

 			|		|
//		1001	|   1000	|  1010
//			|		|
//            ----------+---------------+------------
// 			| (inside)	|
//		0001	|  		|  0010
//			|   0000	|
//            ----------+---------------+------------
// 			|		|
//		0101	|   0100	|  0110
//			|		|

You'll see that everything above the box starts with a "1---" and
everything to the left of the box looks like "---1".
These codes will help us to quickly determine if a line segment is
inside the box.

The algo (for lines) looks like:
	For each line segment (2 points) DO
		Compute codes for both points
		IF Code0 = 0000 or Code1=0000   THEN truly inside
		IF Code0 & Code1 != 0           THEN not truly inside
		IF otherwise have to do the hard math to see if the
		    line segment does pass through the box

If "Code0 & Code1 != 0" then the two points are on the same half-plane
and CANNOT intersect the box.


The problem with the code is probably in the function
lineseg_inside_box().

You should be able to find lots of references to the cohen-sutherland
algorithm online (or in any graphics textbook), and your simple test
case should find out whats wrong very quickly!!

dave