Iteration over two tables with lat and lon data

FranciscoHoff · ‎06-23-2022

I have an task for something really challenging. The idea is to execute the logic described in this link.

Given the following tables:

table "points"

table "polygons"

which represents the following plane:

Find out if the point is inside any polygon, and which polygon it would be. I believe the logic would be something like:

Iterate through each of the points in the points table.
Within each point iteration, iterate through each of the polygons in the polygon table.
For each polygon, iterate through each of its vertices, seeking its coordinates and the coordinates of the next vertex (which will represent the segment of one of the sides of the polygon) and then run the check.

So it would be a main iteration (over the point table) with two nested iterations (one for each polygon, and one for each vertex of that polygon). In the iteration of the vertices, the main calculation is performed.

The main calculation is based on the orientation concept for three ordered points.

Basically, four coordinates are used in this main calculation: [X, Y] from the point being iterated (P), [X, Y] from vertex n of the polygon (Vn) and [X, Y] from vertex n+1 ( Vn+1). In the last vertex iteration, the next vertex to be considered will be the first vertex. The fourth coordinate would be the X value of the point being iterated, and the Y with the value of 1000 (we'll call it Q).

The calculation is four repetitions of the following formula (just changing the variables):

((A[Y] - B[Y]) * (C[X] - A[X])) - ((A[X] - B[X]) * (C[Y] - A[Y]))

Each repetition can be called by On (O1, O2, O3 and O4).

The variables of each repetition are:

O1
A = Vn
B = Vn+1
C = P

O2
A = Vn
B = Vn+1
C = Q

O3
A = P
B = Q
C = Vn

O4
A = P
B = Q
C = Vn+1

The condition that will assert that a given point is inside the iterated polygon will be when any of the following is true, at the end of any iteration over any of the vertices:

(O1 = O2) and (O3 = O4)
(O1 = 0) and (ON_SEGMENT)
(O2 = 0) and (ON_SEGMENT)
(O3 = 0) and (ON_SEGMENT)
(O4 = 0) and (ON_SEGMENT)

The verification that returns true for ON_SEGMENT is:

B[x] <= max({A[X], C[X]}) &&
B[x] >= min({A[X], C[X]}) &&
B[Y] <= max({A[Y], C[Y]}) &&
B[Y] >= min({A[Y], C[Y]})

On getting true for the above condition, 1 is added to a counter. At the end of the iteration over all vertices of the polygon, if the counter value is odd then the point is inside the polygon.

I know it's a lot but the concept can be better understood in the link I provided above. The implementation of this calculation within Power Query would be very interesting, as Power BI does not have any native tool that performs the intersection of points and polygons distributed geographically and could open doors to even more robust analysis. Anyone accept the challenge?