New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

speed up boundary_matrix using spatial queries #74

Closed
jeffreyhanson opened this Issue Apr 5, 2018 · 4 comments

Comments

Projects
None yet
2 participants
@jeffreyhanson
Copy link
Contributor

jeffreyhanson commented Apr 5, 2018

The boundary_matrix function calculates the shared boundary length between different planning units. These calculations assume that the vertices in each planning unit are correctly aligned (see #30). To ensure this assumption is met, this function has a pre-processing step which compares every single edge of planning unit to every vertex in every other planning unit to insert missing vertices. This is not terribly efficient. One idea for speeding this process up would be to use GEOS STR Tree's to only compare every single edge of a given planning unit to every single vertex in only the neighbouring planning units. This could potentially speed up this function a lot, but would rely on some experimental functions in rgeos (i.e. rgeos::gUnarySTRtreeQuery).

@ricschuster

This comment has been minimized.

Copy link
Member

ricschuster commented Apr 5, 2018

rgeos::gUnarySTRtreeQuery sounds very useful. Maybe add a flag to the boundary_matrix function that allows the user to take advantage of rgeos::gUnarySTRtreeQuery, with the caveat in the documentation that the function is experimental?

@jeffreyhanson

This comment has been minimized.

Copy link
Contributor

jeffreyhanson commented Apr 26, 2018

Yeah, that's a very good point regarding the experimental nature of the function, and I think that's a great idea including the flag and noting it in the docs.

@jeffreyhanson

This comment has been minimized.

Copy link
Contributor

jeffreyhanson commented Apr 27, 2018

It looks like the STR tree speeds up the processing quite a lot. Here's a simple benchmark using the Tasmania planning unit data.

# load package
library(prioritizr)

# load example planning unit data
data(tas_pu, package = "prioritizrdata")

# make boundary matrix using standard functionality
system.time(m1 <- boundary_matrix(tas_pu))
#>  user  system elapsed 
#>  4.125   0.027   4.153

# make boundary matrix using STR queries
system.time(m2 <- boundary_matrix(tas_pu, TRUE))
#>  user  system elapsed 
#>  0.264   0.000   0.264 

# verify that solutions are same
all(m1 == m2)
#> [1] TRUE
@jeffreyhanson

This comment has been minimized.

Copy link
Contributor

jeffreyhanson commented Apr 27, 2018

Hmm, it looks like there's a bug that only manifests sometimes and not all times causing the builds to fail. I'll see if I can track it down tomorrow.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment