SQLite Forum

Finding overlap of boxed coordinates
Login

Finding overlap of boxed coordinates

(1) By Chris (83dons) on 2021-08-31 13:24:49 [link]

I have a SQLite table that I would like to now query using python and panda dataframe. The table contains the 4 coordinates of a geographic area using longitude and latitude so effectively each entry represents a box shape. What I would like is to query the table and return one line for every occurrence where box overlaps another box and to miss out any rows where there is a box that has no overlap at all. I am ideally looking to show the number of overlaps a row has and to which original rows all link together to form this overlap. Further down the line I would like to visually represent these on the screen to show the overlap perhaps with a backing image to give context.

An example of the data is below (which is for Mars) which uses aerocentric latitude and an east positive longitude I think it was which goes up to 360 from the central point.

UPPER_LEFT_LONGITUDE 347.15
UPPER_LEFT_LATITUDE -36.545832
UPPER_RIGHT_LONGITUDE 347.69
UPPER_RIGHT_LATITUDE -36.486035
LOWER_LEFT_LONGITUDE 347.81
LOWER_LEFT_LATITUDE -40.795116
LOWER_RIGHT_LONGITUDE 348.38
LOWER_RIGHT_LATITUDE -40.735216

Any help appreciated.

(2) By Larry Brasfield (larrybr) on 2021-08-31 15:52:04 in reply to 1 [link]

Provided that your boxes do not span more than 180 degrees in either direction, the relative signs of a few coordinate differences after subjecting them to mod(), with some XORs, will yield overlap.  A web search will yield several algorithms, not to be repeated here. (Use the phrase "bounding box".)

You may find [the Geopoly extension](https://sqlite.org/geopoly.html) useful. It can do general polygon overlap, although some trickery may be needed for anything that includes poles or the longitude 180.

(3) By Chris (83dons) on 2021-08-31 16:18:07 in reply to 2 [link]

Hi the example above is one one rectangular area. I am looking to match up any other examples that would have some of their area overlapping this rectangle lets say. Yes I am looking for a solution that can query the table in order to select all those where their bounding box overlaps another bouncing box from another row. The area i am interested in just goes from 0 to 90 degrees plus or minus from the equator in latitude and 0 to 360 degrees positive eastwards from the central 0,0 spot. I guess the coordinate system doesn't matter though as the overlap will be determined by a mathematic formula of some type.

(4) By Simon Slavin (slavin) on 2021-09-01 12:32:08 in reply to 1 [link]

Can be done by SQLite using multiple CASE constructions, or nested IF statements.  However, It's not going to be fast, compact, neat, or easy to debug. IMO it's a task which should be performed in a programming language rather than trying to make a complicated SQLite command.

Given two isometric (same axes) rectangles A and B, with boundaries l, r, b, t, intersection rectangle C is as follows:

<pre>C <-- A
IF B.l > C.l, C.b <-- B.l
IF B.b > C.b, C.b <-- B.b
IF B.r < C.r, C.r <-- B.r
IF B.t < C.t, C.t <-- B.t

If C.l >= C.r, there is no overlap
If C.b >= C.t, there is no overlap
Otherwise overlap is C.</pre>

Edge cases (e.g. left line of A is exactly the same as right line of B, or wrap around at -180/+180) must be considered within the context of your requirements.

Suppose you have the coordinates of a rectangle A, and your left longitude column of the database is indexed.  You can quickly dismiss a swathe of rectangles B which won't intersect with A using

<code>SELECT … WHERE B.l < A.r</code>

(5) By Keith Medcalf (kmedcalf) on 2021-09-01 17:59:06 in reply to 1

There is an R-Tree extension specifically for this purpose when working with fixed co-ordinate systems and multi-dimensional rectangles.
<https://sqlite.org/rtree.html>

There is a Geopoly extension specifically for this purpose when working with fixed co-ordinate systems and 2-dimensional polygons, which extends R-Tree by converting the N-sided polygons to 2-dimensional "bounding boxes" to quickly locate candidates. <https://sqlite.org/geopoly.html>

As for Python and Panda dataframe, have reference to the documentation for those whacks of code, neither of which are SQLite3.