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.