[PostGIS] #5772: LineCrossingDirection called on a single-segment linestring and another linestring with multiple intersections does not always evaluate crossing direction at the correct intersection

[PostGIS]

#5772: LineCrossingDirection called on a single-segment linestring and another
linestring with multiple intersections does not always evaluate crossing
direction at the correct intersection
---------------------+---------------------------
 Reporter:  fkcheng  |      Owner:  pramsey
     Type:  defect   |     Status:  new
 Priority:  low      |  Milestone:  PostGIS 3.4.3
Component:  postgis  |    Version:  3.4.x
 Keywords:           |
---------------------+---------------------------
 From what I understand of the docs in
 https://postgis.net/docs/ST_LineCrossingDirection.html,
 `ST_LineCrossingDirection(lineA, lineB)` evaluates the crossing direction
 at the first intersection we would find when traversing `lineB` from its
 start to end.

 However, this is not always the case if `lineB` is only a single segment.

 **Test Cases**

 Consider the a C-shaped `lineA` and single segment `lineB` that intersects
 it twice:

 {{{
 SELECT ST_LineCrossingDirection(lineA, lineB) As A_cross_B
 FROM (SELECT
  ST_GeomFromText('LINESTRING(-1 -1, 1 -1, 1 1, -1 1)') As lineA,
  ST_GeomFromText('LINESTRING(0 2, 0 -2)') As lineB
 ) As foo;
 --Returns 3
 }}}
 The lines look like:
 {{{
    B
  <-|--|
    |  |
 A--|--|
    v
 }}}
 Traversing `lineB` from start to end, the first intersection is the top
 one, where `lineA` crosses `lineB` from `lineB`'s left, so the query
 should return -3, not 3. We can accomplish this by splitting `lineB` into
 2 segments:

 {{{
 SELECT ST_LineCrossingDirection(lineA, lineB) As A_cross_B
 FROM (SELECT
  ST_GeomFromText('LINESTRING(-1 -1, 1 -1, 1 1, -1 1)') As lineA,
  ST_GeomFromText('LINESTRING(0 2, 0 0, 0 -2)') As lineB
 ) As foo;
 --Returns -3
 }}}

 Reversing the directions of `lineA` and `lineB` also gives an erroneous
 result:
 {{{
 SELECT ST_LineCrossingDirection(lineA_rev, lineB_rev) As A_rev_cross_B_rev
 FROM (SELECT
  ST_GeomFromText('LINESTRING(-1 1, 1 1, 1 -1, -1 -1)') As lineA_rev,
  ST_GeomFromText('LINESTRING(0 -2, 0 2)') As lineB_rev
 ) As foo;
 --Returns -3
 }}}
 Which looks like:
 {{{
     ^
  Ar-|--|
     |  |
  <--|--|
     Br
 }}}
 Traversing `lineB_rev` from its start to its end, the first intersection
 is the bottom one, where `lineA_rev` crosses from `lineB_rev`'s right, so
 we expect 3, not -3. This issue is also fixed by splitting `lineB_rev`
 into 2 segments:

 {{{
 SELECT ST_LineCrossingDirection(lineArev, lineBrev) As Arev_cross_Brev
 FROM (SELECT
  ST_GeomFromText('LINESTRING(-1 1, 1 1, 1 -1, -1 -1)') As lineArev,
  ST_GeomFromText('LINESTRING(0 -2, 0 0, 0 2)') As lineBrev
 ) As foo;
 --Returns 3
 }}}

 **Possible clues**

 Running an SQL query that returns all 8 permutations of reversed line
 directions and `LineCrossingDirection` argument order shows that the other
 6 permutations return the correct result, so my guess is that the wrong
 point is being used in the 2 erroneous cases.

 Query:
 {{{
 SELECT ST_LineCrossingDirection(lineA, lineB) As A_cross_B,
        ST_LineCrossingDirection(lineB, lineA) As B_cross_A,
        ST_LineCrossingDirection(lineA_rev, lineB) As A_rev_cross_B,
        ST_LineCrossingDirection(lineB, lineA_rev) As B_cross_A_rev,
        ST_LineCrossingDirection(lineA, lineB_rev) As A_cross_B_rev,
        ST_LineCrossingDirection(lineB_rev, lineA) As B_rev_cross_A,
        ST_LineCrossingDirection(lineA_rev, lineB_rev) As
 A_rev_cross_B_rev,
        ST_LineCrossingDirection(lineB_rev, lineA_rev) As B_rev_cross_A_rev
 FROM (SELECT
  ST_GeomFromText('LINESTRING(-1 -1, 1 -1, 1 1, -1 1)') As lineA,
  ST_GeomFromText('LINESTRING(0 2, 0 -2)') As lineB,
  ST_GeomFromText('LINESTRING(-1 1, 1 1, 1 -1, -1 -1)') As lineA_rev,
  ST_GeomFromText('LINESTRING(0 -2, 0 2)') As lineB_rev
 ) As foo;
 }}}
 Return values with visualizations:
 {{{#!td
 {{{
    B
  <-|--|
    |  |
 A--|--|
    v
 }}}
 A_cross_B: 3 (incorrect)

 B_cross_A: -3
 }}}
 {{{#!td
 {{{
    ^
  <-|--|
    |  |
 A--|--|
    Br
 }}}
 A_cross_B_rev: -3

 B_rev_cross_A: 3
 }}}
 |----------------
 {{{#!td
 {{{
    B
 Ar-|--|
    |  |
  <-|--|
    v
 }}}
 A_rev_cross_B: 3

 B_cross_A_rev: -3
 }}}
 {{{#!td
 {{{
    ^
 Ar-|--|
    |  |
  <-|--|
    Br
 }}}
 A_rev_cross_B_rev: -3 (incorrect)

 B_rev_cross_A_rev: 3
 }}}

 **Version information**

 `SELECT version()`

 `PostgreSQL 16.4 (Debian 16.4-1.pgdg110+1) on x86_64-pc-linux-gnu,
 compiled by gcc (Debian 10.2.1-6) 10.2.1 20210110, 64-bit`

 `SELECT postgis_full_version();`

 {{{
 POSTGIS="3.4.2 c19ce56" [EXTENSION]
 PGSQL="160"
 GEOS="3.9.0-CAPI-1.16.2"
 PROJ="7.2.1
 NETWORK_ENABLED=OFF
 URL_ENDPOINT=https://cdn.proj.org
 USER_WRITABLE_DIRECTORY=/var/lib/postgresql/.local/share/proj
 DATABASE_PATH=/usr/share/proj/proj.db"
 GDAL="GDAL 3.2.2, released 2021/03/05"
 LIBXML="2.9.10"
 LIBJSON="0.15"
 LIBPROTOBUF="1.3.3"
 WAGYU="0.5.0 (Internal)"
 RASTER
 }}}
-- 
Ticket URL: <https://trac.osgeo.org/postgis/ticket/5772>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.