Stack Overflow
Stack Overflow

Questions tagged [douglas-peucker]

An algorithm for reducing the number of points in a curve that is approximated by a series of points

The Douglas-Peucker algorithm is also known under the following names: the Ramer–Douglas–Peucker algorithm, the iterative end-point fit algorithm or the split-and-merge algorithm.

Links

20 questions
5
votes
1 answer

Simplify-Java (by hgoebl) Issue With Reduced Points List Always Size 2

I am trying to implement the reduction algorithim from https://github.com/hgoebl/simplify-java I have looked through his test code and tried to come up with what I think is the right logic. I am taking a list of Location objects, converting them to…
Aggressor
  • 13,323
  • 24
  • 103
  • 182
4
votes
1 answer

Line that triggers Worst-Case for Douglas-Peucker Algorithm?

The Douglas-Peucker line simplification algorithm has a worst-case time complexity of O(n²). However, for a line to actually trigger this worst-case, two things have to go "wrong" at once: the threshold must be set so low that most vertices are…
Dreamer
  • 1,139
  • 9
  • 18
3
votes
2 answers

How to reduce 10k data points and show them on smaller display? Arduino

I‘m working on a visual data logger for my DMM, it writes every measurement to RS232 inteface. There I connect a Teensy 3.6 and collect the data points. For each point I have the timestamp and the measured value. I will collect 10.000 readings. I…
user3819388
  • 31
  • 2
3
votes
2 answers

Graph Simplification Algorithm Advice Needed

I have a need to take a 2D graph of n points and reduce it the r points (where r is a specific number less than n). For example, I may have two datasets with slightly different number of total points, say 1021 and 1001 and I'd like to force both…
Rich Sadowsky
  • 966
  • 1
  • 12
  • 22
3
votes
1 answer

Incremental line simplification

There's a lot of information on the internet regarding ordinary line simplification, https://www.jasondavies.com/simplify/ https://bost.ocks.org/mike/simplify/ http://geomalgorithms.com/a16-_decimate-1.html http://mourner.github.io/simplify-js/ i.e.…
Lu4
  • 14,873
  • 15
  • 79
  • 132
3
votes
1 answer

How to reduce set of points?

I have a ordered list of points (lat,long) on a route. I have a ordered list of stops (lat,long). Let's say I have 1000 points and 20 stops. I would like to reduce the 1000 points to something like 100 depending upon which points are more relevant…
gizgok
  • 7,303
  • 21
  • 79
  • 124
2
votes
1 answer

Find corners/edges on a shape (minimum vertices that can define that shape)

I'm trying to get the corners of the following shape: By corners I mean this (red dots): The minimum quantity of points that can define this shape. And I have implemented the following: public Shape Optimize() { // If the vertices…
z3nth10n
  • 2,341
  • 2
  • 25
  • 49
2
votes
1 answer

Ramer-Douglas-Peucker Algorithm with GPS

I have GPS data which can be close to the north/south pole and can move thousands of kilometers. If I build a distance matrix for example with: from geographiclib.geodesic import Geodesic p1_lat, p1_lon = 43.374880, -78.119956 p2_lat, p2_lon =…
Neabfi
  • 4,411
  • 3
  • 32
  • 42
2
votes
1 answer

How to Minimize the saved points from drawn points using free-flow drawing tool

Currently I'm using "Douglas Peucker" algorithm. My problem is that when I'm drawing,the previously drawn lines are also changing which of course not realistic. Is there other alternative algorithm to minimize the saved points but not altering the…
ajbee
  • 3,511
  • 3
  • 29
  • 56
2
votes
2 answers

Simplification of adjacent polygons

I'm working on converting some maps/regions of an old coordinate system to a simpler (less detailed) model for representing on the web (using jVectorMap). I have sucessfully used the Douglas Peucker-algorithm (from code found here:…
David W.
  • 1,074
  • 4
  • 10
  • 22
1
vote
0 answers

Image Processing: Quantifying roughness of a shape compared to a smooth shape

I am trying to find the roughness of shapes in an image. I have found the contours and used simplification.cutil.simplify_coords_vwp(contour,1000) to calculate a polygon that I want to use as the "smooth" shape (this is similar to the more commonly…
Cameron Greenwalt
  • 47
  • 8
1
vote
1 answer

Golang simplifying polyline data

I am pulling huge geojson datasets with golang, and I am wondering if there is anything like simplify.js for golang, that would reduce the number of points in a polyline while retaining its shape? https://mourner.github.io/simplify-js/
Leff
  • 1,968
  • 24
  • 97
  • 201
1
vote
1 answer

Drawing points along path spirally

Well, I'm trying to optimize what I did here (Smoothing noises with different amplitudes (Part 2)). By this reason, I did a new implementation from scratch (https://youtu.be/o7pVEXhh3TI) to draw the path: private void Start() { …
z3nth10n
  • 2,341
  • 2
  • 25
  • 49
1
vote
1 answer

Douglas-Peucker - Shortest arc from a point to a circle, on the surface of a sphere

I have seen many examples in various programming languages that are using the Douglas-Peucker polyline simplification algorithm to produce a GPolyline to be used on Google Maps. The algorithm, when expressed for polylines on a plan, involves the…
Maurice Perry
  • 32,610
  • 9
  • 70
  • 97
0
votes
1 answer

Android: How to get the string of points from the line being drawn?

This is actually our Thesis, we are required to use the Ramer-Douglas-Peucker Algorithm in simplifying lines, can anyboy help me how to implement this in an Android App. I just want to know how to get the string of points from the line I've…
user1081908
  • 31
  • 1
  • 2
  • 7
1
2