Search code examples
ralgorithmspatialcomputational-geometry

How to determine orientation of points in 2D spatial data and arrange in clockwise manner [for corner cases]?

Essentially I have spatial data in which I go through each point and figure out what are the surrounding points within a circle of some radius. I then want to arrange those points in a clockwise manner and I managed to have done that for "most" cases. The unique feature about this data is that there are only 6 maximum possible location that can surround any center point with how I defined my circle's radius[top-left, top-right, right, bottom-right, bottom-left, left]

So as a sample data

Center Point: 161.3861 368.8119

     col      row
1 164.5365 363.4114
2 155.2205 368.7669
3 167.5968 368.8569
4 158.2358 374.1674
5 164.4465 374.2124
6 158.3258 363.3663

The function would then output [4, 5 ,3, 1, 6, 2] which is the clockwise order. This sub-sample [highlighted in red with the center remained as black] of the data looks like this. [To be clear I have this case working]

enter image description here

But you can imagine that it is not exactly straightforward for the various corner cases. For instance the following case it has no point to the right of it so in the final out put array there should be a zero in the "right, top-right, top-left" index of the array I described earlier.

enter image description here

What I am struggling with is a systematic way to go through the corner cases and assign labels to the missing points. I tried using a dot product approach to quantify how closely the points are from each other (using a normal vector of straight up) but this lead to issues with discriminating top-right, right. I imagine that checking if a line goes through the point we get a sense of what axis the point exists on, but I have not managed to make it work. To summarize the two main corner cases are

  1. Edge points
  2. Island points
Solution

  • You could write a function to tell you which direction a point is in, given the point and the center-point:

    Pseudo-code:

    direction_vector = point - center_point
angle = atan2(direction_vector.y, direction_vector.x)
direction_index = ((angle * 12 / TWO_TIMES_PI) + 12) % 12

    This will give you an index from 0 to 11 (imagine hours on bizarro clock face that goes anti-clockwise from 0, with 0 on the right where 3 o'clock is on a normal clock).

    Now map this onto your directions, with 1 being top-left, 2 being top-right, 3 being right etc:

    direction_index = (((16 - x) // 2) % 6) + 1

    Where // is integer division and % is modulo.

    Now that you have the directions, iterate from 1 to 6 and output the array index of your point that has the corresponding direction index, or 0 if there isn't one (assuming 1-based array indexing).