Geo Intersection

Geo Intersection Support

Query Engine

Format of vectors of Lat and Long coordinates (float32)

[a1,a2,...an,a1,FLT_MAX,b1,bz,...bn]

• FLT_MAX denotes the beginning of next polygon.
• We repeat the first vertex at end of each polygon
• Number of coordinates including FLT_MAX placeholders in the vector.
• The GeoShape can be presented as a struct

struct GeoShape {
    uint32_t numPoints
    float32_t* lats
    float32_t* longs
}

Crossing Number Algorithm

For each row/point P, we counts the number of times a ray starting from this point crosses a polygon boundary edge separating it's inside and outside. If it’s odd, it’s inside, otherwise it’s outside. Each GPU thread is responsible for calculation of one point and one line and we will use atomicXor to flip the parity. We will do one geofence per kernel and will do calculations based on previous results. E.g. we will skip calculations if we find the point is already in previous gefences.

Pseudo code

__global__
void pnpoly(int nvert,
           float *polyX,
           float *polyY,
           float *testX,
           float *testY,
           bool *inputPredicate, // filled with !inOrOut
           bool *outputPredicate,// filled with !inOrOut
           bool inOrOut) {
   int i = blockIdx.x * blockDim.x + threadIdx.x;
   int row = i / nvert;
   // Only do calculations if it's inside a polygon.
   if (inputPredicate[row] ^ inOrOut && polyX[i + 1] != FLT_MAX) {
       if (((vertY[i] > testY) != (vertY[i+1] > testY)) && (testX
           < (vertX[i+1] - vertX[i]) * (testY - vertY[i]) / (vertY[i+1] - vertY[i])
               + vertX[i]))
           atomicXor(outputPredicate[i], 1);
   }

}