Flutterby™! : Algorithms in C++

Next unread comment / Catchup all unread comments User Account Info | Logout | XML/Pilot/etc versions | Long version (with comments) | Weblog archives | Site Map | | Browse Topics

Algorithms in C++

2007-02-09 19:01:28.162181+00 by ebradway 2 comments

I thought I'd ask this over here so I'd get a faster answer... I'm about to write C++ code to implement two very basic algorithms in C++. As a PhD student, I probably should just roll my own because I'll probably want to play with modifying them later. But for now, it might be nice to play with someone else's implementation. I am looking for 2D convex hull routine and a 2D Ramer-Douglas-Peucker (RDP) routine. I've done the basic search but would like personal recommendations because what I've seen out there either costs $$ or is implemented a little weird.

(An aside here, the Peucker in RDP is Tom Poiker and was my advisor's PhD advisor)

comments in ascending chronological order (reverse):

#Comment Re: made: 2007-02-10 04:29:32.429854+00 by: spc476

Wow, only one Google result for “2D Ramer-Douglas-Peuker routine” and a PDF at that! Must be pretty exotic (haven't read it yet).

#Comment Re: made: 2007-02-10 17:47:26.768239+00 by: ebradway

Try eliminating the Ramer (http://www.google.com/search?h...t&cd=1&q=Douglas-Peucker&spell=1)

And a "lit-review":

http://scholar.google.com/scho...as+Peucker&hl=en&lr=&btnG=Search

The issue is that the technique for polyline simplification was simultaneously developed by three different research groups. Ramer (a computer scientist) was working independent of Douglas and Peucker (geographers). Some people refer to the algorithm as Ramer-Douglas-Peucker and some people as just Douglas-Peucker. But it's far from exotic.

Here's one explanation with code:

http://www.codeproject.com/cpp/dphull.asp

and another:

http://www.cs.sunysb.edu/~algo...implement/DPsimp/implement.shtml