I have a shapefile of a set of points that I want to space out. I DO NOT want to do this using line interpolation as I run the risk of placing a point where there wasn't one before.

I can load this into Postgis or QGIS and would like to make sure that no point is closer than 100 metres to its neighbour.

I guess I need to calculate the KNN value for each point to its neighbours as a starting point but am not sure what strategy to use to remove points to achieve the desired result.

The graphic shows a sample of the data, I am trying to overlay it onto the map to show cycle routes as points on top of the road network. At the moment the points are too dense and as such are obscuring the road below. Snapping to roads IS NOT an option as the tracks cover all sorts of different tracks/roads/bridleways etc..

enter image description here

  • Could you please edit this question to define "space out"? I suspect a graphic would not be inappropriate.
    – Vince
    Jan 26 '15 at 20:14
  • What Vince said, but because you mentioned line interpolation, do you want to thin out the vertices that make up a line or are the points scattered?
    – mkennedy
    Jan 26 '15 at 20:34
  • No closer than 100 meters, but is there an upper limit, eg, no further than 500 meters. And do you want the best possible spacing, ie, maximum number of points along a line, meeting your criteria, or just any spacing fitting some rule. Jan 27 '15 at 5:51
  • John - the ideal would be that they are 100m spaced, so the upper limit would be as close to 100m as possible. Jan 27 '15 at 9:01
  • With your clarifications, and as now stated, it's quite an interesting question. I think I have come up with an approximate solution, but I am too tired to post now. Will do tomorrow, if someone else doesn't come up with something similar/better in the meantime. Jan 27 '15 at 22:40

Some ideas....

I figure you have multiple versions of the same track when it is traversed more than once.

It seems to me that you don't want to treat the data as seats of points, but as individual gps tracks - point sequences.

You can then apply various filters to the tracks, and compare them, etc. While you mention that you don't want to "generate" points by interpolating along a line, why can you not do the interpolation to get your 100m spacing, then select the "real" point closest to each interpolated vertex to get the required subset?

Given these selected points will come from a variety of gps tracks, it is unlikely that their attribute data will enable you to define a sequence in SQL to form a line, so you can use a script with Postgis to iterate along each line in 100m intervals, locate the closest real point, save this with new attribute data defining the sequence, or perhaps building the new linestring as you go...


  • Brent. I understand your thinking but it still requires deriving linestrings from the point data which I had hoped to avoid as I think it will cause issues when points are joined out of sequence regardless of the fact that only original points will be remapped. Surely the same could be achieved by calculating a KNN and then iteratively removing points? Jan 28 '15 at 9:34

I have solved this quite simply, it is not elegant but works:-

CREATE OR REPLACE FUNCTION ng_research.point_spacer(record ng_research.ncn_uk_input)  RETURNS bool AS 
    IF (SELECT id FROM ng_research.ncn_uk_output WHERE ST_DWithin(wkb_geometry, record.wkb_geometry, 100) LIMIT 1) IS NULL THEN

        INSERT INTO ng_research.ncn_uk_output(id,name,wkb_geometry) VALUES (record.id,record.name,record.wkb_geometry);
        RETURN true;
    END IF;

    RETURN false;


The points can then be spaced out by:-

SELECT ng_research.point_spacer(A.*) FROM ng_research.ncn_uk_input A
  • My idea, for what it was worth, was to generate a grid, using generate_series twice, and then use st_dwithin to find the closest point in your paths to each of these grids points. You might have to play around with the grid spacing, as a diagonal path would have two centroids about 142 meters apart, while a horizontal/vertical path would be roughly 100 meters, but I think it would work. Jan 29 '15 at 22:03

first a general consideration : if your data is in fact ordered set of points (points sequence), you should definitively use it because it gives a lot of information!

In genereal, you could try several types of methods :

  • matching : directly map the GPS points to road network (will probably work great if you remove points in intersection area). Basic : Knn + closest. Advanced : graph matching, labeling (integer problem)
  • detection : from all the points, (basic) detect segments (Hough Transform + clustering)
  • reconstruction : (basic) construct polyline by linking point to the closest point iteratively (won't work in intersection), then simplify.
  • optimisation : (advanced) cutting your road network into pieces, modeling each pieces as a spline (for instance), find the best parameter of each spline for a given criteria regarding a distance to your points. (advanced) Creating a weighted graph where all points close enough are linked with their distance, adding to the graph the intersection. For each road, find the optimal cut in the graph for a measure (length, centraloty of chosen nodes ..)

I recently used a simple geometric method based on straight skeleton to fuse set of points into line (with a kind of fuzzy definition of points).

Input is points with an estimated precision (for your data, maybe 10 meters)

The successiv steps are

  • buffer of each points with precision (represent the area where the point could be)
  • union of all (represent the area where the lines could be)
  • break into independent area (if any)
  • remove too small area ( a line should be long enough (uses area for instance))
  • straight skeleton on each area
  • keeping only the center line of straight skeleton
  • simplifying

I can share the code if you need it (will need some cleaning).

Cheers, Rémi-C

  • Thanks Remi but these points do not always come close to an identifiable road line string. For example some of them traverse paths that are missing in openstreetmap. Others follow tracks UNDER roads (motorways/dual carriageways). Jan 28 '15 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.