sf handling polygon intersections

[Maschette]

Minimalish example for topology exception exploration:

library(sfheaders)
#n <- 20
#d <- tibble::tibble(x = runif(n, -50, 50), y = runif(n, 0, 100), line_id = rep(seq_len(n/2L), each = 2L))

d <- structure(list(x = c(-21.5621127514169, 40.2962636668235, -31.1925547663122, 
													-22.5405948469415, -23.0838318355381, 29.9605491571128, 11.478958860971, 
													-8.19494309835136, 42.4840283580124, 12.7380638383329, 40.4127392685041, 
													-45.2017169678584, 16.2871447857469, -3.90106798149645, 41.4583092322573, 
													31.2947675585747, -22.8197822580114, -10.0503325928003, -19.7022920008749, 
													-29.5000644400716), y = c(29.2453840607777, 34.4098202185705, 
																										98.7871219869703, 60.797041747719, 3.01325886975974, 11.2556441454217, 
																										99.8579441336915, 29.0021185064688, 19.0383932320401, 64.6716579562053, 
																										44.1835718695074, 23.8893277477473, 83.8549552252516, 62.2791656060144, 
																										0.788207678124309, 48.5741916345432, 73.8897712901235, 12.106719147414, 
																										42.6758473273367, 22.9514547623694), line_id = c(1L, 1L, 2L, 
																																																		 2L, 3L, 3L, 4L, 4L, 5L, 5L, 6L, 6L, 7L, 7L, 8L, 8L, 9L, 9L, 10L, 
																																																		 10L)), row.names = c(NA, -20L), class = c("tbl_df", "tbl", "data.frame"
																																																		 ))



x <- sf_linestring(d, x = "x", y = "y", linestring_id = "line_id")

library(sf)
b <- st_buffer(x[c(1, 4, 5, 6, 8), ], 1,endCapStyle ="FLAT"); plot(b, reset = FALSE)
i <- st_intersection(b)

[Maschette]

it is weird, if you run b without 8 i works. if you add 8 back in it fails with the error:

Error in CPL_nary_intersection(x) : 
  Evaluation error: TopologyException: found non-noded intersection between LINESTRING (31.116 34.6469, 32.3567 32.7435) and LINESTRING (-7.05113 31.4604, 33.1976 34.8206) at 31.115984892808036 34.646855583109961.

if you run it without 8, and then plot 8 over the top (black) and then plot the line segment and point the error says (red and green) they are not captured in 8.

plot(i["n.overlaps"], reset = F)
plot(b["8",], add=T, col=NA)
segments(-7.05113, 31.4604, 33.1976, 34.8206, col=2)
points(31.115984892808036, 34.646855583109961, col=3)

[mdsumner]

Ah nice, good summary

[Maschette]

here is the zoomed in version

[Maschette]

the really weird thing is if you remove 6 which is no where near this join it works fine, it does the same with 4 (or any of them).

[mdsumner]

That's interesting too, I just noticed though that rounding the input lines fixes it, so we might have a case of spurious precision (from our random numbers).

I.e.

library(sfheaders)
#n <- 20
#d <- tibble::tibble(x = runif(n, -50, 50), y = runif(n, 0, 100), line_id = rep(seq_len(n/2L), each = 2L))

d <- structure(list(x = c(-21.5621127514169, 40.2962636668235, -31.1925547663122, 
						  -22.5405948469415, -23.0838318355381, 29.9605491571128, 11.478958860971, 
						  -8.19494309835136, 42.4840283580124, 12.7380638383329, 40.4127392685041, 
						  -45.2017169678584, 16.2871447857469, -3.90106798149645, 41.4583092322573, 
						  31.2947675585747, -22.8197822580114, -10.0503325928003, -19.7022920008749, 
						  -29.5000644400716), y = c(29.2453840607777, 34.4098202185705, 
						  						  98.7871219869703, 60.797041747719, 3.01325886975974, 11.2556441454217, 
						  						  99.8579441336915, 29.0021185064688, 19.0383932320401, 64.6716579562053, 
						  						  44.1835718695074, 23.8893277477473, 83.8549552252516, 62.2791656060144, 
						  						  0.788207678124309, 48.5741916345432, 73.8897712901235, 12.106719147414, 
						  						  42.6758473273367, 22.9514547623694), line_id = c(1L, 1L, 2L, 
						  						  												 2L, 3L, 3L, 4L, 4L, 5L, 5L, 6L, 6L, 7L, 7L, 8L, 8L, 9L, 9L, 10L, 
						  						  												 10L)), row.names = c(NA, -20L), class = c("tbl_df", "tbl", "data.frame"
						  						  												 ))

d <- tibble::as_tibble(lapply(d, signif, digits = 6))

x <- sf_linestring(d, x = "x", y = "y", linestring_id = "line_id")

library(sf)
b <- st_buffer(x, 1,endCapStyle ="FLAT"); plot(b, reset = FALSE)
i <- st_intersection(b)

Probably this is enough

[mdsumner]

Ah, no. That's true for this data set but not in general

[mdsumner]

I can't get the original error now (－‸ლ)

[Maschette]

even if you start with round numbers in the data set you end up with a lot of decimal places after the buffer, should it be a rounding of the geometry?

[Maschette]

have you tried turning it off and on again?

[mdsumner]

ping @Maschette let's fix this fyi

[mdsumner]

The original example works now, my GEOS in windows is at 3.9.3 - that's where the improvement has come from (on linux I see 3.10.2 and the latest release is 3.11.1 so there's still room for better than what CRAN has rn

I'll try a big stress test

[mdsumner]

ah, nah - doesn't take much to ruin it

library(sfheaders)
n <- 200
d <- tibble::tibble(x = runif(n, -50, 50), y = runif(n, 0, 100), line_id = rep(seq_len(n/2L), each = 2L))

x <- sf_linestring(d, x = "x", y = "y", linestring_id = "line_id")

library(sf)
b <- st_buffer(x, 1,endCapStyle ="FLAT")
i <- st_intersection(b)
Error in CPL_nary_intersection(x) : GEOS exception

[mdsumner]

I tried with new geos but it's much the same

#geometries <- as_geos_geometry(wkb)
#tree <- geos_intersects_matrix(g, geos_strtree(g))
out <- geos_geometry()
prec <- min(sqrt(geos_area(geometries))/100)
## from polymer: #wkb <-c(as_wkb(A), as_wkb(B), as_wkb(C))
## prec = 0 gives a nearly degenerate polygon on the diagonal between triangle and rectangle in top left
## prec = 0.02 gives a ok result(10 polygon) but very inaccurate
## prec = 0.002 gets a geometrycollection with the two parts of the top left rectangle (multipolygon 9 when using 0.02)
for (i in seq_along(geometries)) {
	geom <- geometries[i]
	if (length(out) > 0) {
			treeinner <- geos_intersects_matrix(geom, geos_strtree(out))
			for (k in treeinner[[1]]) {
				
				inters <- geos_intersection_prec(out[k], geom, grid_size = prec)
				tryme <- try(wk::wk_polygon(inters), silent = TRUE)
				if (!inherits(tryme, "try-error")) {
					inters <- tryme
				} else {
					inters <- NULL
				}
				if ( length(inters) > 0 && !geos_is_empty(inters) && geos_is_valid(inters)) {
					
				geom <- geos_difference_prec(geom, inters, grid_size = prec)
			
				g <- geos_difference_prec(out[k], inters, grid_size = prec)
				out[k] <- g
				out <- c(out, inters)
				#print(k)
				}
			}


			
	}
	out <- c(out, geom)
}


p <- out[grepl("polygon", geos_type(out))]
p <- p[!geos_is_empty(p)]
# par(mfrow = n2mfrow(length(p)), mar  = rep(0, 4))
# lapply(p, \(.x){plot(geometries); plot(.x, add = TRUE, col = sample(hcl.colors(24), 1))})

[mdsumner]

I get it working more reliably with GEOS 3.11.1 and a very fine precision (like crazy something 0.000001 )
but still not perfect with just 100 lines, the triangle way is better still

(more soon)