Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Add Visvalingam-Whyatt line-simplification algorithm #84

Merged
merged 6 commits into from
Jan 16, 2017
Merged

Add Visvalingam-Whyatt line-simplification algorithm #84

merged 6 commits into from
Jan 16, 2017

Conversation

urschrei
Copy link
Member

This is an initial pass at the implementation of the Visvalingam-Whyatt line-simplification algorithm.

This implementation is partially based on a pre-v1.0 version written by @huonw, and uses his method of storing retained points in a "linked list", updating it as necessary. I'm not sure if there's a cleaner way of doing this, but I'm open to ideas.

I'd also like to test the output of this algorithm against a more complex LineString using PostGIS – there are several other extant implementations in various languages, but I don't completely trust them.

Another issue is the provision of the epsilon parameter; in this case, it refers to the minimum triangle area to retain, and it's somewhat unintuitive compared to rdp (although PostGIS provides the same API).

Other questions:

  • Should this trait live in the simplify.rs module, instead of its own?

@frewsxcv
Copy link
Member

Awesome, thanks for doing this! I'm a little busy, but I'll try to look at this sometime this weekend unless someone else wants to review this :)

urschrei and others added 2 commits January 12, 2017 15:31
@urschrei
Update algorithm to correctly implement user-defined epsilon
be82b8c 
WIP until I can verify against PostGIS
@urschrei
Add longer LineString for VW test
720c7ed 
The result matches the output of running ST_SimplifyVW on PostGIS
@urschrei
Copy link
Member Author

Hmm this is odd; the test passes on my machine (x86_64, OS X):

stable-x86_64-apple-darwin (default)
rustc 1.14.0 (e8a012324 2016-12-16)

I don't know where the extra point (Point(Coordinate { x: 28.770069, y: 54.27718 })) in position 240 has come from on Travis

@frewsxcv
Copy link
Member

FWIW, I can replicate the error Travis is getting on x86_64 macOS. rustc 1.16.0-nightly (1a2ed98d3 2017-01-13)

@urschrei
Copy link
Member Author

After cargo clean, I can reproduce it on stable and nightly on my local machine. I suspect that it's a precision issue in one of the num crates. I'll compare a few more LineStrings, but I'm not too concerned; the algorithm's simple enough that an implementation error would cause differences way beyond 1 point in 401.

@frewsxcv
Copy link
Member

Thanks!

@frewsxcv frewsxcv merged commit a32caea into georust:master Jan 16, 2017
@frewsxcv
Copy link
Member

Should this trait live in the simplify.rs module, instead of its own?

Regarding this question, I think what you have is fine for now. Might change in the future though.

@urschrei
Copy link
Member Author

🎊

@urschrei urschrei deleted the visvalingam branch January 18, 2017 19:19
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers
No reviews
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@urschrei @frewsxcv