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.



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.

  • $\begingroup$ @ihf> thank you. but, it is not able to access to that paper.. $\endgroup$ – niro Jul 21 '11 at 18:53
  • $\begingroup$ @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. $\endgroup$ – davidlowryduda Jul 21 '11 at 21:01
  • $\begingroup$ @g_niro, or you could ask the author for a copy: cs.tufts.edu/~frisken/frisken.html $\endgroup$ – lhf Jul 21 '11 at 22:07
  • $\begingroup$ dear all..looking for some other methods..please $\endgroup$ – niro Jul 22 '11 at 7:28
  • $\begingroup$ @g_niro: I've added another reference. $\endgroup$ – lhf Aug 17 '11 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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