Skip to content

Instantly share code, notes, and snippets.

@mdsumner
Last active August 9, 2017 01:36
Show Gist options
  • Save mdsumner/4e9ebb4ed9fa03682e58128afa66a16c to your computer and use it in GitHub Desktop.
Save mdsumner/4e9ebb4ed9fa03682e58128afa66a16c to your computer and use it in GitHub Desktop.
Topology-edit a.k.a "shared edit" of simple features (we only see the points update until the object is re-composed)
#' NOTE: improved work-in-progress here MDSumner 2017-08-02
#' https://github.com/mdsumner/gibble/blob/master/inst/examples/gibble_rebuild.R
#' function to illustrate topological editing of simple features
#'
#' Note that this uses the sc and scsf packages which have a much
#' grander goal than de-duplicating vertices and re-composing simple
#' features. The logic used can be trivially isolated into a small set
#' of functions for use in mapedit, or perhaps a separate package.
#'
#' Limited to pure edit of the points with no live redraw.
#' @param x simple features object, supported by scsf/sc::PATH
#' @param map mapview object
topoedit.sf <- function(x, map = NULL) {
##devtools::install_github("mdsumner/sc")
##devtools::install_github("mdsumner/scsf")
require(scsf)
require(sc)
## build the topological version
## all we really get are shared vertices for now
prim <- sc::PATH(x)
## create point-versions we can identify
sf_points <- sf::st_as_sf(prim$vertex, coords = c("x_", "y_"), crs = st_crs(x))
if (is.null(map)) map <- mapview::mapview()
map <- map + mapview::mapview(x) + mapview(sf_points)
edited <- editFeatures(sf_points, map = map)
prim$vertex <- edited %>% dplyr::select(vertex_) %>% dplyr::bind_cols(sc_coord(edited))
scsf::sf(prim)
}
#mapview() + mapview(minimal_mesh)
a <- topoedit.sf(minimal_mesh)
## a more involved example
north_carolina <- read_sf(system.file("shape/nc.shp", package="sf"))
## pick one and its neighbours
library(dplyr)
set.seed(1)
path <- sc::PATH(north_carolina)
sample_feature <- path$object %>% sample_n(1) %>% select(object_, FIPS)
## this is very convoluted, just used to pick the neighbours (by vertex)
## of our one selected feature, but also shows the simple relation
## between the PATH tables that link a single de-duplicated vertex pool
neighbours <- sample_feature %>%
inner_join(path$path) %>% inner_join(path$path_link_vertex) %>%
distinct(vertex_) %>% inner_join(path$path_link_vertex) %>%
distinct(path_) %>% inner_join(path$path) %>%
distinct(object_) %>% inner_join(path$object) %>%
select(FIPS) %>% inner_join(north_carolina) %>% sf::st_as_sf()
neighbours$sample <- neighbours$FIPS == sample_feature$FIPS
plot(neighbours[c("sample")])
plot(north_carolina, add = TRUE, colour = NA)
## here we only can edit points, and that's all we can see happening
## but the result is used to rebuild the features with those updates
## to the de-duplicated vertex pool
b <- topoedit.sf(neighbours)
plot(b["sample"])
plot(neighbours, add = TRUE, col = NA, lwd = 4)
@mdsumner
Copy link
Author

mdsumner commented Jul 31, 2017

[discussion topic] shared edit, topology edit

This is a fundamental feature for map editing with many levels of capability, and is not a straightforward topic to distil in short form. But, there are many good and easy aspects to it, and some that require a lot of investigation and development so I'd like to encourage wide exploration as well as respecting the caution required for mapedit to define project scope and timelines.

Shared edit of vertices

"Shared edit" means that when a vertex lies on a segment that is geometrically identical to a segment of a neighbouring feature (i.e. any segment on a shared boundary) then the edge itself is moved and any feature with that segment is modified accordingly. It's actually completely contrary to the simple features standard, and is only able to be implemented by determining the actual topology (the shared edges and vertices) and working with that, either by upfront decomposition or real-time analysis (or something in between). Like almost all other topology in R

That complicated description is easier to understand by doing or seeing:
https://www.youtube.com/watch?v=rWVRIoIG3gc

At its simplest it's easy, de-duplicate the vertices, let the user move those and put the original object back together. There's an example of doing that here, it uses non-CRAN code but it's also rather trivial and easy to isolate for inclusion in mapedit or in a specific package to just do the task, which is:

  • de-duplicating and identifying unique vertices
  • maintaining that identity and unique status during editing
  • re-building the original object.

The missing feature from the example above is the "live feedback", and it's not clear to me how that can be propagated down to the leaflet vis engine and brought back up. I think that's the hard part for this simplest case of "topo-editing". That example will work for the basic sf types and could be applied to others.

Addition and removal of vertices

The task becomes more complicated if the vertex pool requires vertices to be added or removed, as then the relation of each vertex to the edge/s they are part of must also be identified, and a removal involves "merging an edge" while and addition "splits an edge". I'd suggest this is out of scope, at least at first.

Numerical precision issues

The really difficult part is numeric precision, since so much vector data that is clearly intended to be precise is actually only nearly so with very slight inaccuracies in coordinates that were intended to be equal. The existing topology tools in R (spdep, rgeos, some of sf) apply an overall "precision" which is intended as a kind of rounding, it essentially sets the threshold for what is "the same". There's more than one way to do this though and users have very little control over what it means currently. I'd suggest this is also out of scope, since it's got some scary implications and is really the responsibility of the data owner. R could have a family of tools to apply these thresholds and normalizations in different places, and that is not a task for mapedit in my opinion, but it will need to have a policy about it at least.

This is really CAD

CAD is the premiere "drawing environment", and we live in this weird fragmented world where graphics, GIS, design drawing and physcial modelling are separated, mostly into artificial camps defined by the early market dominance of a few key companies who work hard to maintain their mind-share.

The really key editing tools came to Manifold GIS within discussions about COGO, and in their slow but ruthless way they have modernized the ideas put into the editing for 7.0 and 8.0 into their Radian database engine, and it's clear that this is on a reproducible workflow framework with tight integration with their back-end.

COGO: https://en.wikipedia.org/wiki/COGO

Also explained well by Manifold:

http://www.georeference.org/doc/shared_edit.htm

http://www.georeference.org/doc/editing_objects.htm

There's discussion for QGIS here, though I'd expect there's probably much better support now: https://docs.qgis.org/2.2/en/docs/user_manual/working_with_vector/editing_geometry_attributes.html#topological-editing

There's an early example here of a connection to igraph:
https://gist.github.com/timelyportfolio/94c44959cf73e96a12ee2e194aaaaf2a

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