CGAL users discussion list

[Stefan Salewski <>]

On Fri, 2014-01-03 at 01:15 -0800, isscandar wrote:
> Hello Stefan, 
> it seems to me a problem like "connect the dots"
> http://en.wikipedia.org/wiki/Connect_the_dots and a Google search for
> "connect the dots algorithm" actually gives a lot of results.
> 

Well, my problem is that I have an unordered set of points.
There are no numbers that guide me from one point to the next.
(To be correct, for some subsets of the points, there may indeed exist
numbered sequences. The points build groups, in electronic design
automation they are called footprints or land patterns, and often they
are ordered. But that is not really guaranteed, and it can occur that
two footprints are spaced very closely together, so that they build a
line of double length -- you don't need to understand this remark, only
for the case that some EDA concerned people are reading this post.) 

> I do not know a particular algorithm for your task, I can just suggest an
> algorithm that maybe you need in order to extract a segment (i.e. its
> endpoints) from a set o quasi-collinear points: the Ramer–Douglas–Peucker
> algorithm
> http://en.wikipedia.org/wiki/Ramer%E2%80%93Douglas%E2%80%93Peucker_algorithm
> 

That is interesting, I was not aware of that algorithm. But it seems
that I need again an ordered sequence of points, which I do not have
initially.

Best regards,

Stefan Salewski