3

How to link four points to a convex polygon? I mean how to identify the order of these four points.

Thanks.

Zhong

Fihop
  • 3,127
  • 9
  • 42
  • 65

3 Answers3

3

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
  • 45,755
  • 8
  • 102
  • 111
  • 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). – Fihop Aug 07 '10 at 15:21
  • 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. – Fihop Aug 07 '10 at 15:30
  • 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. – Fihop Aug 07 '10 at 15:33
  • 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. – Fihop Aug 07 '10 at 15:36
  • 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 Aug 07 '10 at 15:41
  • Is it necessary to normalize all points' coordinates according to the center point before divide x by y? – Fihop Aug 07 '10 at 16:51
  • no, normalization is not needed (but you do need to take the coord relative to the center, yes) – mvds Aug 07 '10 at 20:45
  • 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. – Fihop Aug 07 '10 at 21:23
2

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: Sort Four Points in Clockwise Order

Community
  • 1
  • 1
MK.
  • 33,605
  • 18
  • 74
  • 111
  • what if two leftmost are the same as the two topmost – Maciej Hehl Aug 07 '10 at 00:15
  • this indeed fails on a basic diamond shape – mvds Aug 07 '10 at 00:16
  • 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. Aug 07 '10 at 00:26
  • 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 Aug 07 '10 at 15:42
1

The atan2() method is handy for this, and is found in most languages.

atan2(y,x) and converts rectangular coordinates (x,y) to the angle theta from the polar coordinates (r,theta).

Given 4 points, find their average. Then calculate the four (x,y) vectors obtained by subtracting the average from each of the four points.

For each of these (x,y) vectors, calculate the angle θ = atan2(y,x). θ will be between -π/2 and π/2.

Sort the θ's. This will give you the order of the points, in clockwise order.

This only works for convex quadrilaterals.

brainjam
  • 18,863
  • 8
  • 57
  • 82
  • Perfect~. You answered my question. Is it necessary to normalize all points' coordinates according to the center point before divide x by y? – Fihop Aug 07 '10 at 16:54
  • There is no divide operation involved. And there is no need to normalize coordinates for atan2(). – brainjam Aug 07 '10 at 18:03
  • Here, normalizing coordinates means computing these four points' new coordinates relative to the center. My bad English. :). – Fihop Aug 07 '10 at 18: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 Aug 07 '10 at 19:12
  • 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 Aug 07 '10 at 20:42
  • 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 Aug 07 '10 at 20:44
  • @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 Aug 07 '10 at 21:46
  • @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 Aug 07 '10 at 22:29
  • @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 Aug 08 '10 at 02:49
  • @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 Aug 08 '10 at 13:03
  • @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 Aug 08 '10 at 13:57
  • @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 Aug 08 '10 at 15:40