I have some points in 3D which are in a single plane. I want to arrange them in clock wise or counter clockwise order.
The points can create a concave or convex polygon in a single plane.
Can any body give any suggestions?
views:
92answers:
2
+4
A:
Find the center of all the points, then calculate all the angles from the center to each point. Then sort by angle.
Ignacio Vazquez-Abrams
2010-05-06 06:11:00
But it will not work with points of concave polygon. I had tried it.
Himadri
2010-05-06 06:12:12
You never stated that you wanted the original vertex order to be maintained. And if you already have a vertex order then why do you need to arrange the points again?
Ignacio Vazquez-Abrams
2010-05-06 06:17:04
@lgnacio I do not have vertex in order. But they all create a polygon if we arrange them in order.
Himadri
2010-05-06 12:33:15
They'll create a polygon in *any* order. However, they may not necessarily create the polygon that you hope they will.
Ignacio Vazquez-Abrams
2010-05-06 12:39:38
@Ignacio Oh....Yes you are right.It didn't come in my mind. But it also didn't solve my problem. Anyway I should think some other solution for it. Thanks.
Himadri
2010-05-06 12:54:32
I believe this to be the solution to the question. Sorting by the atan2f(deltaY, deltaX) (that is, delta from the center of the points) seems to pretty much do the "clockwise ordering" step (if you sort in reverse, hehe).
dash-tom-bang
2010-05-07 02:05:21
@dash Can you please explain it more
Himadri
2010-05-07 04:59:14
Compute the center of the points. You need to do this because "clockwise" implies that there's a "center" that you're rotating around. For each point, compute the "delta" from this center point. Then each point gets a "score" which comes from atan2f(dY, dX). Sort by this score and you have your ordered list of points.
dash-tom-bang
2010-05-07 15:39:52
@dash No, I think I am lacking in explaining my question. But I think my problem can not be solved using points. So, now I am trying to get lines between two consecutive point of my resulting polygon. So, it will be some how easy to arrange lines in sequence.
Himadri
2010-05-08 05:01:50
A:
Ok, I nearly solve the problem. I got line segment instead of having points in 3d. So, Now I have to arrange line segment in sequence. Which becomes somehow easier for me. I am now able to arrange them in sequence.
Himadri
2010-05-10 07:15:25