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] [source]

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 [source]

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 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] [source]

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] [source]

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:

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.

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

SELECT … WHERE B.l < A.r

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

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.