locationtech/jts

IsValid method returns true on Polygon that has non-noded self-intersection

Closed this issue · 2 comments

james-willis commented

In the Sedona repo, a user reported that they had a geometry for which ST_IsValid was returning true, but an intersection method would throw a non-noded intersection error. See the case from @atiannicelli in this thread: apache/sedona#1612

I have created a minimal reproducible example of a case where I believe isValid is incorrectly returning true below.

val p = loadWKT("POLYGON ((-5.985979 54.9372974, -5.9857103 54.9374386, -5.9856866 54.9374228, -5.985751 54.9373909, -5.9856392 54.9373165, -5.9855676 54.937352, -5.9856475 54.9374051, -5.9855813 54.9374457, -5.9854978 54.9374129, -5.9854129 54.9374842, -5.9854322 54.9375123, -5.9856833 54.9376109, -5.9857849 54.9375256, -5.9857909 54.9375201, -5.9857555 54.9374875, -5.9859626 54.9373794, -5.9859873 54.9373949, -5.9860307 54.9373721, -5.9860036 54.9373551, -5.9860402 54.9373359, -5.985979 54.9372974), (-5.9856469 54.9374719, -5.9855813 54.9374457, -5.98564744638696 54.93747161301757, -5.9856492 54.9374723, -5.9857264 54.9375026, -5.9856469 54.9374719))")

p.isValid() // true
hasSelfIntersections(p) // true

definitions of hasSelfIntersections:

def hasSelfIntersections(geom: Geometry) = {
    // I only wrote this to consider Polygons and only their external ring
    // Probably works for Linestrings too
    val geometryFactory = new GeometryFactory()
    
    val coords = geom.getCoordinates()
    val segments = (0 until coords.length - 1).map { i =>
      val startPoint = coords(i)
      val endPoint = coords(i + 1)
      geometryFactory.createLineString(Array(startPoint, endPoint))
    }
    
    val intersections = for {
      i <- segments.indices
      j <- i + 1 until segments.size // Avoid checking a segment against itself
      if (segments(i).intersects(segments(j)))
    } yield (segments(i).intersection(segments(j)))
    
    
    // All intersections are points
    val intersectionsArePoints = intersections.filter(x => x.getGeometryType != "Point").length == 0
    // All of those points are the coordinates in the geometry (ie NOT non-noded self-intersections)
    val intersectionsAreGeomCoords = intersections.map(x => x.getCoordinate).toSet.diff(coords.toSet).size == 0

    !(intersectionsArePoints && intersectionsAreGeomCoords)
}
dr-jts commented

The supplied Polygon looks valid to me. It has a very narrow hole, but that doesn't make it invalid.

image

Not sure why your function hasSelfIntersections indicates that self-intersections are found. It's not in Java, so I can't run it.

  • 👍1
james-willis commented

I found a bug in my hasSelfIntersection code. I will close this issue and open one with a higher level Issue I am having with intersecting 2 geometries in JTS.

  • 👍1