We help IT Professionals succeed at work.

# Curve point reduction algorithm?

on
Hi Experts,

I need to draw a geographic map displaying a pipeline network from a known GPS coordinates in real-time. Unfortunately, amount of available GPS points is huge (~150'000) which slows down screen refresh rate below 5 /sec.

As you can see from the attached screenshot, most of the lines are almost straight, so despite that  they build from a thousands of points, considerable drawing chords reduction could be achieved without a noticeable image quality degradation.

Q. Can you direct me to some known algorithm of point reduction that would work here?

regards,
odissey1
piprline-map.png
Comment
Watch Question

## View Solutions Only

Top Expert 2007

Commented:
How is the data organized when you receive it?

Jim

Commented:
Hi JimBrandley

Each line is a progression of a sequential GPS points (consider simple points [X,Y], though azimuth angles are used typically), taken by a pipeline personnel. Basically, a field guy walks along the pipe and takes [X,Y] point each 10-100ft, whenever he considers appropriate. The result is an ASCII file like
BEGIN LINE
X1, Y1
X2, Y2
...
END LINE
BEGIN LINE
...
END LINE
...

As a result Each BEGIN/END section contains 100-1000 points, even though they all might be sitting on a VISUALLY straight line, which could be described by just 2 points.

odissey1
Top Expert 2007

Commented:
Then the hard work is already done. Capture the first point after a BEGIN LINE, then read the remaining points into one point variable until you reach the END LINE. The last one was not overritten. Now, you have two points that define a line and each endpoint of the line segment. Render that line segment, and go get the next one.

Jim

Commented:
Hi JimBrandley,

Simply taking first-last point wont work, the lines may have curves as well!

The algorithms of such kind are used in cartography for e.g. shoreline smoothing and generally called 'Polyline Reduction' (for example Douglas-Peucker iteration algorithm).

Currently, this is a boundary of my knowledge on the subject.
Any directions are welcome.

odissey1

Top Expert 2007

Commented:
Got it. I thought it was too simple. I was initially afraid you needed to pick line segments out of a grid of pixels.

Next question: Many of these poly-lines cross. What did the recorder in the field do when reaching an intersection? I'm wondering if each BEGIN / END delimited block includes any branches or discontinuities. For example,
Start recording
At branch, record right branch
Resume recording initial branch.

Etc.

Jim
Top Expert 2007
Commented:
Here's a description of the Douglas-Peucker algorithm, and two variations, with C++ code for the final one. Note that the authors are using vector arithmetic instead of transcendental functions to solve for distances. This should perform pretty well.

http://geometryalgorithms.com/Archive/algorithm_0205/algorithm_0205.htm

I noticed you posted in both C# and Delphi zones. C# isn't that far removed from C++. I have not used Delphi, but have been told it's similar to Pascal. I could help translating the C++ to C# if you need it, but you would need someone else to help with Delphi translation.

I think this algorithm will work fine if the branches are included, providing the branches are simple linear pieces. Otherwise there will be undesirable connections back to the main trunk.

Jim

Commented:
Hi JimBrandley,

I googled to same page also (http://geometryalgorithms.com).
C++ algorithm given looks pretty clear, I should be able to translate it to Delphi myself.
Thank you for directions anyway (points allocated).

The BEGIN-END sections are (mostly) straight lines and have no branch points or returns. Sometimes though they have almost 90 degree turns.

odissey1
Top Expert 2007

Commented:
The turns will not be a problem.

Jim
CERTIFIED EXPERT
Top Expert 2014
Commented:
What kind of drawing statements/objects are you using?

===================
This might be a simpler approach.  Suspend screen updating while you draw ALL the segments.  This should address your performance problem.  Also, make sure you are double-buffering your canvas drawing.
Example:
http://www.efg2.com/Lab/Library/Delphi/Graphics/GaryWillilams_EnhBitmap.TXT

A more sane approach might be to add the OpenGL library and not do direct drawing.

=================
I've done some point (redundancy) reduction by comparing the prior XY pair with the current XY pair.  My application is graphing data with a large range of sequences into a canvas with a much smaller range of width and height pixels.  This may not be applicable to this problem.  Thought I'd mention it just in case.

=================
You might want to convert these lines into polylines defined with an array of TPoints.  That way, you are only performing one drawing operation per curve rather than once per from/to pairs.

Look at the Canvas.PolyLine() method.

=================
You face two obstacles trying to reduce the pairs into line segments.
a. To what resolution do you need to calculate your straight lines?  This is affected by the size of your canvas and the accuracy of your XY data.
b. How many points (line segments) can you afford to lose before your user notices it?

relevant EE question:
http://www.experts-exchange.com/Q_20807000.html
CERTIFIED EXPERT
Top Expert 2014

Commented:
After posting my comment, it occured to me that the collection of curves and points is already similar to a vector format.  You might be able to create an WMF/EMF file from your curves, read the file into your program (TMetafile) and then blt the curves onto your canvas in one operation.

Consider third party components that might make the meta file handling easier.

Marco Cantu has a chapter on Using Metafiles:
http://www.marcocantu.com/delphipowerbook/GraphicsinDelphi_md6.pdf

Commented:
To aikimark,
thank you for comments, I will look into links and try some (need time). Currently the lines are drawn using TeeChart Pro 7 (FastLine series). This may be not the fastest way to draw but it works OK (CPU load ~7%) when points amount <5000.  I expect major speed-up from points reduction due to specific nature of those lines. As pipelines are mostly straight, so point reduction could be of the factor of 100 -1000. More imporant, this procedure could be performed just once (on map uploading).

>I've done some point (redundancy) reduction by comparing the prior XY pair with the current XY pair.
This is already implemented in TFastLine algorithm drawing. I add some extra filtering of that kind depending on the linepen width, which reduces amount of points from 144k downto 40k.

>a. To what resolution do you need to calculate your straight lines?
>b. How many points (line segments) can you afford to lose before your user notices it?
-This is a real-time plot on  the pilot's display in the helicopter. So resolution and accuracy is not really important.

regards,
odissey1

CERTIFIED EXPERT
Top Expert 2014

Commented:
@odissey1

"This may be not the fastest way to draw but it works OK...when points amount <5000"

Well that means it doesn't work for this problem without some tinkering.

It would have been very useful to know that you are using charting to do your drawing.  I would have IMMEDIATELY said to drop the use of the TeeChart Pro component.

==========
"This is a real-time plot on  the pilot's display in the helicopter. So resolution and accuracy is not really important"
* preprocess ALL the mapping data and incorporate the pipeline layer onto all your maps.
* when pipeline data changes, replace the layer.
* store the images (and layers) in compressed format.  I/O is your biggest performance bottleneck.
* break the segments into some reasonable number of sections.  Compute the linear approximation of that section.  If the variance/stdDev is within your tolerance, then replace the section's data with the two end points of the section.  For curvy/bendy sections, you may choose to recurse the sectioning process or just render the entire section's points.  You might be able to use the TeeChart to do this linear fitting for each section.
Hint: Look at the TrendStyle help.
CERTIFIED EXPERT
Top Expert 2014

Commented:
* compare the line segment connecting the two section end points with the linear approximation line for all the points in the section.
* look at different splining algorithms.
* render each section with a color that indicates the accuracy of the pipeline drawing against its constituent data points.

Commented:
Hi all,

I found implementation of the Douglas-Peucker algorithm (got from www.efg2.com):
http://www.simdesign.nl/Components/DouglasPeucker.html

Thank you for input,
odissey1

Commented:
To aikimark,

> I would have IMMEDIATELY said to drop the use of the TeeChart Pro component.
- I am not a great fan of TeeChart. Some years ago I submitted Steema about 20 bug reports (some bugs are still there..). Anyway, with TeeChart I am able to update screen ~10 times faster than a custom-coded mapping component, which we ordered a while ago. The mapping unit is <10%  of a project, and I don't want to get buried there. Once you start adding zoom, scroll, custom drawing, annotations, axes, it all becomes a great ordeal.

I consider graphics32 as an alternative tool for the next step. Do you have any comments on that?

> store the images (and layers) in compressed format.
- the map should head forward, which means it rotates simultaneously with helicoper so all lines need to be redrawn on every compass update (otherwise I could use a stored bitmap).

odissey1
CERTIFIED EXPERT
Top Expert 2014

Commented:
If you render entire quadrants worth of pipelines ahead of time, you only need to rotate the affected quadrant(s).  I'm not sure about the power of Graphics32, but I have heard very positive stories about OpenGL.

I wouldn't even worry about reducing the points, since you should be drawing them ahead of the time where they will be rendered in the helicopter.

One of the grand old men of Delphi, Robert Vivrette of UNDU fame, showed our Delphi user group an application he wrote for PG&E.  His application had to show streets, houses, poles, transformers, substations, and gas lines.  He even had to show this information from different altitudes with continuous zoom levels.  The secret was to have the images ready to render.  That is why I said to start with pipeline curves/lines that have already been drawn.

Commented:
Another possibillty is to evaluate the distance between the point you are about to render and the previous rendered point.  If the distance is small, then simply do not render the new point.  if it is large then join it to the last rendered point.
"Small" and "large" here are dependent on the scale you are rendering at.
This has the effect of removing the myriad of small points that don't contribute much (individually) to the final rendered output.

Commented:
odissey1:
the implementation of the Douglas-Peucker algorithm in Delphi
http://www.simdesign.nl/Components/DouglasPeucker.html
Thank you for input,
odissey1