Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have set of point clouds, representing boundaries of different closed polygons. These polygons contains 3d points. But they also can be considered as a 2d case once boundary points are projected to the xy plane. Though these boundaries are irregular, it can be fitted into small, straight line segments. I am trying to do this fitting by least square method. But, before that, I want to identify the turning points or the corresponding point sets for each straight line segment which I am going to fit. So, I am looking for a good, fast method. I know that the dougles-peuker algorithm could be used to reduce the points along the boundary and then to identify the turning points. But, I feel it would not be giving me major turning spots like 20, 45, 90, degrees... turnings of the boundary.

  1. if anyone can point out a robust method to find major turning points along the boundary it is highly grateful.
  2. also, please tell me, how can i combine dougles-peuker algorithm and least square fitting to get straight line segments together with available turns (if any) like
    20,45,90,..degrees in between consecutive line segments.
  3. may be, one can give me some other methods or if can give me some related papers which is able to detect turning points of the point boundaries.
  4. actually i am looking for point generalization algorithm which is able to keep turning points.


share|cite|improve this question

For 2d curves, check out Efficient Curve Fitting.

See also An Algorithm for Automatically Fitting Digitized Curves by Schneider, in Graphics Gems. The code is available.

share|cite|improve this answer
@ihf> thank you. but, it is not able to access to that paper.. – niro Jul 21 '11 at 18:53
@g_niro: deceptively, maybe, his name is lhf (LHF) instead of ihf (IHF). Secondly, you can find the check-out page for that paper here - it does cost 15 dollars though. – mixedmath Jul 21 '11 at 21:01
@g_niro, or you could ask the author for a copy: – lhf Jul 21 '11 at 22:07
dear all..looking for some other methods..please – niro Jul 22 '11 at 7:28
@g_niro: I've added another reference. – lhf Aug 17 '11 at 0:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.