Opened 16 months ago

Last modified 14 months ago

#5563 new defect

Potential bug in the ST_Equals function.

Reported by: Wenjing Owned by: pramsey
Priority: critical Milestone: PostGIS GEOS
Component: postgis Version: 3.4.x
Keywords: Cc:

Description

Consider the following test case:

SELECT ST_Equals(Foo.a, Foo.b), ST_Distance(Foo.a, Foo.c)
    FROM (SELECT ST_GeomFromText('LINESTRING(2 0, 0 1)') As a,
    ST_GeomFromText('LINESTRING(2 0, 0.2 0.9, 0 1)') As b,
    ST_GeomFromText('POINT( 0.2 0.9)') As c) As Foo; -- expected: {t}, actual: {f}

The distance from point c ('POINT( 0.2 0.9)') to line a ('LINESTRING(2 0, 0 1)') is 0. Line b ('LINESTRING(2 0, 0.2 0.9, 0 1)') is plus.

Line a should equal line b because they have the same points set. { (x,y) | 2*x + y = 0 }

Actual behavior: PostGIS doesn’t consider LINE a to be equal to LINE b. The result of st_equals is false which means Postgis doesn’t consider they are the same line, although the distance between them calculated is 0.

The issue cannot be reproduced with integers only, indicating a potential floating-point issue. After all coordinate points are magnified ten times, the results are in line with expectations.

Additional Informationhttps://tarry-goal-613.notion.site/Potential-bug-in-the-ST_Equals-function-398b8876ee9842219cb872e7eb7bb546?pvs=4

Change History (4)

comment:1 by Wenjing, 16 months ago

Priority: mediumcritical

comment:2 by mdavis, 15 months ago

Ironically, this bug is due to the high-precision evaluation of the line-point orientation predicate in GEOS.

Not sure what a suitable fix is at the moment. Likely it will involve some sort of precision rounding, but that needs to be done carefully to ensure there are no other impacts.

See also https://github.com/libgeos/geos/issues/968

comment:3 by mdavis, 15 months ago

The issue is due to the inherent inaccuracy of finite-precision floating point arithmetic. There's a lot of arithmetic being carried out, so the likelihood of 2 transformed intersecting lines NOT intersecting in 3D is very high.

You can't rely on topological relationships being preserved through floating-point operations. This is the essence of the well-known issue of geometrical robustness failures. The solution is usually either to use exact arithmetic (often impractical) or use tolerance values (not a panacea, but very often works).

Version 0, edited 15 months ago by mdavis (next)

comment:4 by robe, 14 months ago

Milestone: PostGIS 3.4.1PostGIS GEOS
Note: See TracTickets for help on using tickets.