lwline_crossing_direction()

int lwline_crossing_direction	(	const LWLINE *	l1,
		const LWLINE *	l2
	)

Given two lines, characterize how (and if) they cross each other.

Given two lines, characterize how (and if) they cross each other.

Parameters

l1	first line string
l2	second line string

Returns

a CG_LINE_CROSS_TYPE LINE_NO_CROSS = 0 LINE_CROSS_LEFT = -1 LINE_CROSS_RIGHT = 1 LINE_MULTICROSS_END_LEFT = -2 LINE_MULTICROSS_END_RIGHT = 2 LINE_MULTICROSS_END_SAME_FIRST_LEFT = -3 LINE_MULTICROSS_END_SAME_FIRST_RIGHT = 3

Definition at line 470 of file lwalgorithm.c.

{
        uint32_t i = 0, j = 0;
        const POINT2D *p1, *p2, *q1, *q2;
        POINTARRAY *pa1 = NULL, *pa2 = NULL;
        int cross_left = 0;
        int cross_right = 0;
        int first_cross = 0;
        int this_cross = 0;
#if POSTGIS_DEBUG_LEVEL >= 4
        char *geom_ewkt;
#endif
 
        pa1 = (POINTARRAY*)l1->points;
        pa2 = (POINTARRAY*)l2->points;
 
        /* One-point lines can't intersect (and shouldn't exist). */
        if ( pa1->npoints < 2 || pa2->npoints < 2 )
                return LINE_NO_CROSS;
 
        /* Zero length lines don't have a side. */
        if ( ptarray_length_2d(pa1) == 0 || ptarray_length_2d(pa2) == 0 )
                return LINE_NO_CROSS;
 
 
#if POSTGIS_DEBUG_LEVEL >= 4
        geom_ewkt = lwgeom_to_ewkt((LWGEOM*)l1);
        LWDEBUGF(4, "l1 = %s", geom_ewkt);
        lwfree(geom_ewkt);
        geom_ewkt = lwgeom_to_ewkt((LWGEOM*)l2);
        LWDEBUGF(4, "l2 = %s", geom_ewkt);
        lwfree(geom_ewkt);
#endif
 
        /* Initialize first point of q */
        q1 = getPoint2d_cp(pa2, 0);
 
        for ( i = 1; i < pa2->npoints; i++ )
        {
 
                /* Update second point of q to next value */
                q2 = getPoint2d_cp(pa2, i);
 
                /* Initialize first point of p */
                p1 = getPoint2d_cp(pa1, 0);
 
                for ( j = 1; j < pa1->npoints; j++ )
                {
 
                        /* Update second point of p to next value */
                        p2 = getPoint2d_cp(pa1, j);
 
                        this_cross = lw_segment_intersects(p1, p2, q1, q2);
 
                        LWDEBUGF(4, "i=%d, j=%d (%.8g %.8g, %.8g %.8g)", this_cross, i, j, p1->x, p1->y, p2->x, p2->y);
 
                        if ( this_cross == SEG_CROSS_LEFT )
                        {
                                LWDEBUG(4,"this_cross == SEG_CROSS_LEFT");
                                cross_left++;
                                if ( ! first_cross )
                                        first_cross = SEG_CROSS_LEFT;
                        }
 
                        if ( this_cross == SEG_CROSS_RIGHT )
                        {
                                LWDEBUG(4,"this_cross == SEG_CROSS_RIGHT");
                                cross_right++;
                                if ( ! first_cross )
                                        first_cross = SEG_CROSS_RIGHT;
                        }
 
                        /*
                        ** Crossing at a co-linearity can be turned handled by extending
                        ** segment to next vertex and seeing if the end points straddle
                        ** the co-linear segment.
                        */
                        if ( this_cross == SEG_COLINEAR )
                        {
                                LWDEBUG(4,"this_cross == SEG_COLINEAR");
                                /* TODO: Add logic here and in segment_intersects()
                                continue;
                                */
                        }
 
                        LWDEBUG(4,"this_cross == SEG_NO_INTERSECTION");
 
                        /* Turn second point of p into first point */
                        p1 = p2;
 
                }
 
                /* Turn second point of q into first point */
                q1 = q2;
 
        }
 
        LWDEBUGF(4, "first_cross=%d, cross_left=%d, cross_right=%d", first_cross, cross_left, cross_right);
 
        if ( !cross_left && !cross_right )
                return LINE_NO_CROSS;
 
        if ( !cross_left && cross_right == 1 )
                return LINE_CROSS_RIGHT;
 
        if ( !cross_right && cross_left == 1 )
                return LINE_CROSS_LEFT;
 
        if ( cross_left - cross_right == 1 )
                return LINE_MULTICROSS_END_LEFT;
 
        if ( cross_left - cross_right == -1 )
                return LINE_MULTICROSS_END_RIGHT;
 
        if ( cross_left - cross_right == 0 && first_cross == SEG_CROSS_LEFT )
                return LINE_MULTICROSS_END_SAME_FIRST_LEFT;
 
        if ( cross_left - cross_right == 0 && first_cross == SEG_CROSS_RIGHT )
                return LINE_MULTICROSS_END_SAME_FIRST_RIGHT;
 
        return LINE_NO_CROSS;
 
}

References getPoint2d_cp(), LINE_CROSS_LEFT, LINE_CROSS_RIGHT, LINE_MULTICROSS_END_LEFT, LINE_MULTICROSS_END_RIGHT, LINE_MULTICROSS_END_SAME_FIRST_LEFT, LINE_MULTICROSS_END_SAME_FIRST_RIGHT, LINE_NO_CROSS, lw_segment_intersects(), LWDEBUG, LWDEBUGF, lwfree(), lwgeom_to_ewkt(), POINTARRAY::npoints, LWLINE::points, ptarray_length_2d(), SEG_COLINEAR, SEG_CROSS_LEFT, SEG_CROSS_RIGHT, POINT2D::x, and POINT2D::y.

Referenced by ST_LineCrossingDirection(), test_lwline_crossing_bugs(), test_lwline_crossing_long_lines(), and test_lwline_crossing_short_lines().

Here is the call graph for this function:

Here is the caller graph for this function: