PostGIS  2.5.7dev-r@@SVN_REVISION@@

◆ 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
l1first line string
l2second 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 461 of file lwalgorithm.c.

462 {
463  uint32_t i = 0, j = 0;
464  const POINT2D *p1, *p2, *q1, *q2;
465  POINTARRAY *pa1 = NULL, *pa2 = NULL;
466  int cross_left = 0;
467  int cross_right = 0;
468  int first_cross = 0;
469  int this_cross = 0;
470 #if POSTGIS_DEBUG_LEVEL >= 4
471  char *geom_ewkt;
472 #endif
473 
474  pa1 = (POINTARRAY*)l1->points;
475  pa2 = (POINTARRAY*)l2->points;
476 
477  /* One-point lines can't intersect (and shouldn't exist). */
478  if ( pa1->npoints < 2 || pa2->npoints < 2 )
479  return LINE_NO_CROSS;
480 
481 #if POSTGIS_DEBUG_LEVEL >= 4
482  geom_ewkt = lwgeom_to_ewkt((LWGEOM*)l1);
483  LWDEBUGF(4, "l1 = %s", geom_ewkt);
484  lwfree(geom_ewkt);
485  geom_ewkt = lwgeom_to_ewkt((LWGEOM*)l2);
486  LWDEBUGF(4, "l2 = %s", geom_ewkt);
487  lwfree(geom_ewkt);
488 #endif
489 
490  /* Initialize first point of q */
491  q1 = getPoint2d_cp(pa2, 0);
492 
493  for ( i = 1; i < pa2->npoints; i++ )
494  {
495 
496  /* Update second point of q to next value */
497  q2 = getPoint2d_cp(pa2, i);
498 
499  /* Initialize first point of p */
500  p1 = getPoint2d_cp(pa1, 0);
501 
502  for ( j = 1; j < pa1->npoints; j++ )
503  {
504 
505  /* Update second point of p to next value */
506  p2 = getPoint2d_cp(pa1, j);
507 
508  this_cross = lw_segment_intersects(p1, p2, q1, q2);
509 
510  LWDEBUGF(4, "i=%d, j=%d (%.8g %.8g, %.8g %.8g)", this_cross, i, j, p1->x, p1->y, p2->x, p2->y);
511 
512  if ( this_cross == SEG_CROSS_LEFT )
513  {
514  LWDEBUG(4,"this_cross == SEG_CROSS_LEFT");
515  cross_left++;
516  if ( ! first_cross )
517  first_cross = SEG_CROSS_LEFT;
518  }
519 
520  if ( this_cross == SEG_CROSS_RIGHT )
521  {
522  LWDEBUG(4,"this_cross == SEG_CROSS_RIGHT");
523  cross_right++;
524  if ( ! first_cross )
525  first_cross = SEG_CROSS_LEFT;
526  }
527 
528  /*
529  ** Crossing at a co-linearity can be turned handled by extending
530  ** segment to next vertex and seeing if the end points straddle
531  ** the co-linear segment.
532  */
533  if ( this_cross == SEG_COLINEAR )
534  {
535  LWDEBUG(4,"this_cross == SEG_COLINEAR");
536  /* TODO: Add logic here and in segment_intersects()
537  continue;
538  */
539  }
540 
541  LWDEBUG(4,"this_cross == SEG_NO_INTERSECTION");
542 
543  /* Turn second point of p into first point */
544  p1 = p2;
545 
546  }
547 
548  /* Turn second point of q into first point */
549  q1 = q2;
550 
551  }
552 
553  LWDEBUGF(4, "first_cross=%d, cross_left=%d, cross_right=%d", first_cross, cross_left, cross_right);
554 
555  if ( !cross_left && !cross_right )
556  return LINE_NO_CROSS;
557 
558  if ( !cross_left && cross_right == 1 )
559  return LINE_CROSS_RIGHT;
560 
561  if ( !cross_right && cross_left == 1 )
562  return LINE_CROSS_LEFT;
563 
564  if ( cross_left - cross_right == 1 )
566 
567  if ( cross_left - cross_right == -1 )
569 
570  if ( cross_left - cross_right == 0 && first_cross == SEG_CROSS_LEFT )
572 
573  if ( cross_left - cross_right == 0 && first_cross == SEG_CROSS_RIGHT )
575 
576  return LINE_NO_CROSS;
577 
578 }
char * lwgeom_to_ewkt(const LWGEOM *lwgeom)
Return an alloced string.
Definition: lwgeom.c:556
void lwfree(void *mem)
Definition: lwutil.c:244
@ LINE_MULTICROSS_END_RIGHT
Definition: liblwgeom.h:1522
@ LINE_MULTICROSS_END_SAME_FIRST_LEFT
Definition: liblwgeom.h:1523
@ LINE_MULTICROSS_END_LEFT
Definition: liblwgeom.h:1521
@ LINE_CROSS_LEFT
Definition: liblwgeom.h:1519
@ LINE_MULTICROSS_END_SAME_FIRST_RIGHT
Definition: liblwgeom.h:1524
@ LINE_CROSS_RIGHT
Definition: liblwgeom.h:1520
@ LINE_NO_CROSS
Definition: liblwgeom.h:1518
const POINT2D * getPoint2d_cp(const POINTARRAY *pa, uint32_t n)
Returns a POINT2D pointer into the POINTARRAY serialized_ptlist, suitable for reading from.
Definition: lwgeom_api.c:374
@ SEG_COLINEAR
@ SEG_CROSS_RIGHT
@ SEG_CROSS_LEFT
int lw_segment_intersects(const POINT2D *p1, const POINT2D *p2, const POINT2D *q1, const POINT2D *q2)
returns the kind of CG_SEGMENT_INTERSECTION_TYPE behavior of lineseg 1 (constructed from p1 and p2) a...
Definition: lwalgorithm.c:372
#define LWDEBUG(level, msg)
Definition: lwgeom_log.h:83
#define LWDEBUGF(level, msg,...)
Definition: lwgeom_log.h:88
POINTARRAY * points
Definition: liblwgeom.h:425
double y
Definition: liblwgeom.h:331
double x
Definition: liblwgeom.h:331
uint32_t npoints
Definition: liblwgeom.h:374
unsigned int uint32_t
Definition: uthash.h:78

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, 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: