Question

Create an average/mean line from points

parashari
Badge +1

I don't know if this is already answered somewhere already but couldn't find it.

This is in regards to my previous thread about aligning randomly distributed line geometry as per building footprints. Now, I could find GPS traces as point data to align my line geometry as per the points.

In the image below: The black line is the approximate required solution

I tried using NeighbourFinder with 3m distance and then MeasureSetter for putting weights. Ideally, I wanted that points towards the center are weighted more than the outer ones. I have attached some sample data for the same.

Could someone help me out with any ideas?

Thanks.

1 Attachment

11 replies

erik_jan
Rank
Userlevel 2
Badge +12

I would try using the HullReplacer to create a polygon, followed by the CenterlineReplacer.

Hope this gets you going in the right direction.

jdh
Rank
Badge +22

Erik's solution is reasonably simple and will give results, however outliers will have a considerable effect on the output.

Mathematically speaking what you want is LOESS (locally estimated scatterplot smoothing) or non-linear regression. In FME this is probably best achieved using the RCaller.

virtualcitymatt
Rank
Userlevel 4
Badge +26

I would also suggest to try a binning approach. Create a grid over the points, find out which grid elements have the most points. Calculate the average x, y for each bin and use the average x, y to replace bin.

 

 

Here you can take the bin which contains the most points for each row per column and for each column per row. To make the process a little better you could process this as sub-tiles.
parashari
Badge +1

I would try using the HullReplacer to create a polygon, followed by the CenterlineReplacer.

Hope this gets you going in the right direction.

Thanks @erik_jan for your suggestion. I used HullAccumulator and CenterLineReplacer (approximate) and got the below output. I'll now try smoothening the polygon (from HullAccumulator) or the line (from CenterLineReplacer).

Below is what I've got. Yellow is the input and red is the output.

Also, as mentioned in my previous thread, I will now shift the road geometry that overlaps with the building footprints.

Thanks!

parashari
Badge +1

Erik's solution is reasonably simple and will give results, however outliers will have a considerable effect on the output.

Mathematically speaking what you want is LOESS (locally estimated scatterplot smoothing) or non-linear regression. In FME this is probably best achieved using the RCaller.

@jdh I can assume that now from the below output, I might face issues related to:

- most importantly, smoothening the roads and reduce the number of vertices as you've mentioned. Generalizer should give me some good results.

- snapping the start and end vertex to further connecting roads, since you see the start and end vertex is going out from the road center, which is quite logical also.

- snapping the line in itself if it breaks by itself due to lack of points in between.

 

I will try understanding more RCaller and how it can smooth roads. Or should I smooth polygon first and take out the centerline in the end.

Thanks

M
Badge +2

@hellblazer do you have a sample of the original points you can share - or send to me directly mark @ safe.com

parashari
Badge +1

@hellblazer do you have a sample of the original points you can share - or send to me directly mark @ safe.com

@markatsafe I have sent you the mail.

Thanks.

M
Badge +2

Erik's solution is reasonably simple and will give results, however outliers will have a considerable effect on the output.

Mathematically speaking what you want is LOESS (locally estimated scatterplot smoothing) or non-linear regression. In FME this is probably best achieved using the RCaller.

@hellblazer @jdh LOESS is a function of x, and is great for scatter plots and time series where f(x) increases steadily but it doesn't seem to work very well for location data. There are similar non-parametric methods - i.e. Principal Curve method. There seems to be loads of different variants. I tried a couple of the R functions, principal_curve() from the princurve library, and also the lcp() from the LPCM library. The latter holds most promise but you'd need to play around with many of the parameters. I've attached a workspace with a couple of examples. lpcmprincipalcurveexample.fmw

kimo
Badge +1

I found a simple R script that uses inverse distance weighting to find the best line from a group of lines. I adapted it to run in FME using an RCaller. (you need to install R and set the path in Options) average_tracks_with_R.fmwt

# average tracks is an R script to make an "average" track of several GPS

 

# tracks by combining/merging them into a "line of best fit". Made by

 

# Michiel Faber <http://www.openstreetmap.org/user/Michiel%20Faber>

 

# This software is dedicated to the public domain through CC0:

 

# http://creativecommons.org/publicdomain/zero/1.0/

 

#

 

# See http://wiki.openstreetmap.org/wiki/average_tracks for usage instructions.

 

# Home: https://github.com/dittaeva/average-tracks

 

# version: 0.5

 

# date: 2014-01-02

 

 

# 15 Aug 2018 kimo

 

# skip loading csv records, done by FME

 

# load frame "tracks" has columns lat, lon, routeID
parashari
Badge +1

I found a simple R script that uses inverse distance weighting to find the best line from a group of lines. I adapted it to run in FME using an RCaller. (you need to install R and set the path in Options) average_tracks_with_R.fmwt

# average tracks is an R script to make an "average" track of several GPS

 

# tracks by combining/merging them into a "line of best fit". Made by

 

# Michiel Faber <http://www.openstreetmap.org/user/Michiel%20Faber>

 

# This software is dedicated to the public domain through CC0:

 

# http://creativecommons.org/publicdomain/zero/1.0/

 

#

 

# See http://wiki.openstreetmap.org/wiki/average_tracks for usage instructions.

 

# Home: https://github.com/dittaeva/average-tracks

 

# version: 0.5

 

# date: 2014-01-02

 

 

# 15 Aug 2018 kimo

 

# skip loading csv records, done by FME

 

# load frame "tracks" has columns lat, lon, routeID

Hi, @kimo Thanks a lot for your suggestion.

I am still working on your idea as we have millions of GPS lines which I am trying to work upon, which create thousands of csv files. I will get back to you on this as soon as I do this! Thanks.

M
Badge +2

Example workspace attached

Reply


Community Stats

28,670
Posts
109,365
Replies
36,531
Members
Terms & ConditionsCookie settings
A product of
Safe Software respectfully acknowledges that we live, learn and work on the traditional and unceded territories of the Kwantlen, Katzie, and Semiahmoo First Nations.