Hi guys,
How to link four points to a convex polygon? I mean how to identify the order of these four points.
Thanks.
Zhong
+3
A:
Take the center point (i.e. average of x and y coords), then calculate x/y values for y<centery, then for y>=centery. would be fastest I guess.
(that is, if I understood the question in the first place...)
mvds
2010-08-06 23:53:41
YES! I agree. Beautiful solution. The following is my understanding:Assuming we have four two dimensional points (a_x, a_y), (b_x, b_y) (d_x, d_y), (e_x, e_y). We can calculate the center point, saying (c_x, c_y).
FihopZz
2010-08-07 15:21:42
Find the y values for y > c_y, saying 4 and 2, and the y values for y < c_y, saying 1 and 3. Find the x values for x > c_x, saying 1 and 4, and the x values for x < c_x, saying 2 and 3.
FihopZz
2010-08-07 15:30:06
As for how to link these four points to a convex polygon, Firstly, link 4 and 2, and then we should decide point 2's next point, it's 3(because the x values of 2 and 3 are less than c_x). Next, 3 and 1. At Last, 1 and 4.
FihopZz
2010-08-07 15:33:38
I guess someone may ask what if coordinate values of two points have the same c_y value or c_x value, for example a diamond. Yes, it can be fixed.
FihopZz
2010-08-07 15:36:51
Well that's not what I meant, I really meant to divide x by y, so you can order them by angle. (no need for the inverse tan(), just compare x/y values)
mvds
2010-08-07 15:41:36
Is it necessary to normalize all points' coordinates according to the center point before divide x by y?
FihopZz
2010-08-07 16:51:52
no, normalization is not needed (but you do need to take the coord relative to the center, yes)
mvds
2010-08-07 20:45:19
YES, Thank you very much. I will think about is it necessary to do atan2 operation. If it's not necessary, it will save time. Thanks again.
FihopZz
2010-08-07 21:23:33
+2
A:
Sort them vertically, connect 2 top most to each other and two lowest to each other.
Sort horizontally and then connect 2 leftmost to each other and two rightmost to each other.
EDIT: anyways, SO's cool related section on the right suggests an answered duplicate: http://stackoverflow.com/questions/242404/sort-four-points-in-clockwise-order
MK
2010-08-06 23:58:47
ok, take two topmost, then select leftmost from different pairs.diamond shape is disambiguated by saying that if there are two points on the same vertical level the leftmost wins.I suspect mvds' solution is better but I don't fully understand it.
MK
2010-08-07 00:26:04
I'm just looking for the angle, but skipping the tan-1() step, since tan is an increasing function in the range of interest.
mvds
2010-08-07 15:42:36
A:
brainjam
2010-08-07 16:33:37
Perfect~. You answered my question. Is it necessary to normalize all points' coordinates according to the center point before divide x by y?
FihopZz
2010-08-07 16:54:59
There is no divide operation involved. And there is no need to normalize coordinates for atan2().
brainjam
2010-08-07 18:03:53
Here, normalizing coordinates means computing these four points' new coordinates relative to the center. My bad English. :).
FihopZz
2010-08-07 18:13:13
You definitely want to be normalizing then. If (cx,cy) is the center point, and (px,py) is one of the points, you will be calling `atan2(py-cy,px-cx)`.
brainjam
2010-08-07 19:12:09
there is no need for the atan step, it's just wasting cpu cycles and demonstrates you don't know what you are doing.
mvds
2010-08-07 20:42:27
regarding "elegant", I guess it depends on your definition of elegant. If this needs to happen in a loop, on a phone, 1000 times a second, doing the whole atan is *far* from elegant.
mvds
2010-08-07 20:44:08
@mvds: I've removed the sentence comparing this answer with other answers. You're right, "elegance" is in the eye of the beholder, and will vary according to usage and context.
brainjam
2010-08-07 21:46:34
@brainjam: I fear this kind of "elegance" makes that my brand new computer struggles harder than the one I had in 2000 to make a simple excel scatter plot. This kind of elegance belongs in mathematical analysis, not programming.
mvds
2010-08-07 22:29:13
@mvds, I don't agree. If atan2 is expensive and you're doing several thousand per second, then by all means don't use it. In fact, even x/y is an expensive operation on the iPhone, because it makes it switch from Thumb to ARM mode. If x and y are integers, you shouldn't be dividing, you should be using other tricks. On the other hand, if you're doing a few atan2's as part of a larger image processing algorithm, no big deal. FihopZz can decide whether 'elegance' lies in the simplicity and expressiveness of the code, or in the number of quads that can be sorted per second.
brainjam
2010-08-08 02:49:32
@brainjam: but then the atan2 is buried deep within your library, used only "a few times". Then somebody else comes along and finds a reason to call your function 1000 times/sec on an iphone (see the current developments and questions popping up here as well regarding OCR libraries on (i)phones). So, just put a line in the code `// we should be doing atan2() here but it's faster to skip that step` and everyone is happy.
mvds
2010-08-08 13:03:23
@mvds: http://en.wikipedia.org/wiki/Program_optimization#When_to_optimize
brainjam
2010-08-08 13:44:47
@brainjam: this is not about optimizing. If you add a useless function (in this case atan2()) with no real added value, you cannot call it optimizing to remove that, but rather bug-fixing. atan2 will only convert from one representation of angles (dy/dx + semiplane) to another (radians) at the cost of cycles. For comparison, the way the angle is represented doesn't matter.
mvds
2010-08-08 13:57:49
@brainjam: that's the motivation for `atan2()` over `atan()` + quadrant handling, yes. But I'm saying not to do any atan at all. For the value in radians gives no benefit over the dy/dx value, whereas the cost of atan is relatively high.
mvds
2010-08-08 15:40:11