Ytukyg

I have a coordinate system with a certain amount of regions, similar to this one:

The difference in my case is however, that all regions are uniquely numbered, are all of the same size and there are 16 of them (so each quadrant would have 4 slices of exactly the same size).

I also have a set of tuples (two dimensional coordinates), which are all between (-1,-1) and (1,1). I'd now like to check into which region (i.e. 1 to 16) they'd land if mapped onto the coordinate system.

As a total beginner, I have no idea on how to tackle this, but here is my approach so far:

Make all the dividing lines functions and check for each point whether they're above and below them. Ignore those on the decision boundary

For example: Quadrant 1 has four regions. From the x-axis to the y-axis (counter-clockwise) let's call them a, b, c and d.

a would be the region between the x-axis and f1(x) = 0.3333x (red)

b between f1 and f2, f2(x) = x (yellow)

c between f2 and f3, f3(x) = 3x (blue)

d between f3 and the y-axis

As code:

def a(p):

   if(y > 0 and y < 0.3333x):

      return "a"

   else:

      b(p)



def b(p):

   if(y > 0.3333x and y < x)

      return "b"

   else:

      c(p)



def c(p):

   if(y > x and y < 3x):

      return "c"

   else: 

      d(p)



def d(p): 

   if(y > 3x and x > 0):

      return "d"

Note: for readability's sake I just wrote "x" and "y" for the tuple's respective coordinates, instead p[0] or p[1] every time. Also, as stated above, I'm assuming that there are not items directly on the functions, so those are ignored.

Now, that is a possible solution, but I feel like there's almost certainly a more efficient one.

Since you're working between (-1,-1) and (1,1) coordinates and divinding equaly the cartesian plane, it becomes naturally to use trigonometry functions. Thinking in the unitary circle, which has 2*pi deegres, you are dividing it in n equal parts (in this case n = 16). So each slice has (2*pi)/16 = pi/8 deegres. Now you can imagine an arbitray point (x, y) connected to the origin point (0, 0), it formes an angle with the x-axis. To find this angle you just need to calculate the arc-tangent of y/x. Then you just need to verify in which angle section it is.

Here is a sketch:

And to directly map to the interval you can use the bisect module:

import bisect

from math import atan2

from math import pi



def find_section(x, y):



    # create intervals

    sections = [2 * pi * i / 16 for i in range(1, 17)]



    # find the angle

    angle = atan2(y, x)



    # adjusts the angle to the other half circle

    if y < 0:

        angle += 2*pi



    # map into sections

    return bisect.bisect_left(sections, angle)

Usage:

In [1]: find_section(0.4, 0.2)

Out[1]: 1



In [2]: find_section(0.8, 0.2)

Out[2]: 0

Shapely is a python library that can help you with typical cartesian geometry, but as far as I know it doesn't have an easy way of extending its Line objects indefinitely based on a function.

If you're ok with that, then you can check if any Point is in any Polygon using the Polygon.contains(Point) pattern, as shown here: https://shapely.readthedocs.io/en/stable/manual.html#object.contains