How The FMTM Splitter Algorithm Works

[spwoodcock]

Overview

A modular approach is used, with the output from one step being the input for the next step.

Module 1: Splitting On Linear Features

• Dividing up the features into areas based on prominent linear features.
• This would mean dividing by major roads, rivers, railways, to avoid having to traverse these when mapping in a single task area.

Important

The goal of this step is to both improve the mapping efficiency by not having to traverse features, and to arguably improve safety by not having to cross roads or railways.

Module 2: Clustering

• K-means is used as the clustering algorithm. The process is as follows:
  • Randomly choose a centroid for each cluster, using the 'k' parameters, i.e. the number of centroids to assign.
  • Assign each point in the dataset to a nearest centroid.
  • For every cluster, the algorithm recomputes the centroid by taking the average of all points in the cluster, reducing the total intra-cluster variance in relation to the previous step.
  • Since the centroid was updated, each point is re-assigned to the nearest centroid.
  • Repeats the calculation of the centroids in an interative process, until either:
    1. The sum of distances between the data points and their corresponding centroid is minimized.
    2. A maximum number of iterations is reached.
    3. No changes in centroids value are produced.

k-means-algorithm.mp4

Important

The goal of this step is to have clusters that mean a minimised walking distance for the enumerator in the field.

Module 3: Generation of Boundaries

• Taking the centroids from the k-means clustering, we currently generate voronoi polygons:

• This is an approximate way to split an area up into polygons based on centroids.
• An alternative approach being considered is using concave hulls

Important

The goal of this step is to provide usable task boundary (polygons) that enclose the geometries to be mapped.

Module 4: Updating Boundaries

Sometimes the generated boundaries are not perfect for many reasons.

Not Enough Geometries Enclosed In Polygon

• The user specified an average number of buildings they wish to be present in the final task area.
• Sometimes we get a split area that may have far fewer buildings than we desire, due to many reasons, such as a linear feature splitting a small cluster of buildings off from the main group.
• Merge least feature count polygons with neighbouring polygons #58

Other

See the various issues on the repo that are being solved!

[spwoodcock]

@ivangayton @Sujanadh please update if this is wrong anywhere / missing anything!
I wrote it quickly 😅