CODEWITHSUNDEEP
algorithmpostgresqlgisgeospatialpostgis
user1244932
user1244932

Reputation: 8142

How ST_Within/ST_Contains works with geo data?

The question: what algorithm/or algorithms uses spatial databases to check that geo point (latitude and longitude) belong to "geo rect" (4 geo points connected by meridians and parallels)?

At first I thought that it is simple projection plus algorithms for 2-D plane indexing, like r-tree, but how then these databases dealing with points near south/north pole and/or -180 and 180 longitude.

For example lets our point is (0, E 180), and the rectangle is (N 1, W 179), (N 1, E 179), (S 1, E 179), (S 1, E 179),

where N = north, E = east, W = west, S = south.

If map rectangle to Mercator then we got:

(-126799830, 5434036), (139214148, 6832332),
(-126799830, -16488164) (139214148, -17886459),

and our point is (142452996, -5527064).

And in such projection point not belong to rectangle, while it actually belong.

Actually no one projection can helps with such case, because of it should map geo point to several different locations, to handle cases when rectangle cross E 180, W 180, N 90, S 90 and when rectangle not cross such boundaries.

So how spatial databases check that geo point belongs to geo rect?

Upvotes: 1

Views: 1637

Answers (2)

fradal83
fradal83

Reputation: 2022

Looking at the postgis source code, the "within" calculation for geographic types is done calculating the distance between objects.

Here's the geography_dwtithin function, that is called by st_dwithin https://github.com/gravitystorm/postgis/blob/master/postgis/geography_measurement.c#L107

Then lwgeom_distance_spheroid http://postgis.net/docs/doxygen/2.1/da/de7/liblwgeom_8h_a2aac0f91b6dfd27873ab828a1874805b.html that compares bboxes before measuring distance.

The distance calculation can be found here http://postgis.net/docs/doxygen/2.1/d2/ddd/lwgeodetic_8c_a56339ad4a240527a078249dc8e56b082.html#a56339ad4a240527a078249dc8e56b082

At rows 1756 - 1764 you can find the calculation for the simplest case (point to point). The other cases uses the same logic, but looking for the nearest points.

Then you can find the sphere_distance calculation here http://postgis.net/docs/doxygen/2.1/d2/ddd/lwgeodetic_8c_ab9f003c831c66b723beca7103e811785.html#ab9f003c831c66b723beca7103e811785

and the spheroid_distance calculation here http://postgis.net/docs/doxygen/2.1/d0/d7a/lwgeodetic_8h_a5c2565cd7f88783c32b777ca58d4dbcc.html#a5c2565cd7f88783c32b777ca58d4dbcc

Upvotes: 2

RusArt
RusArt

Reputation: 576

In PostGIS there are difference between geometry and geography.

Take a look at their documentation:

The basis for the PostGIS geometry type is a plane. The shortest path between two points on the plane is a straight line. That means calculations on geometries (areas, distances, lengths, intersections, etc) can be calculated using cartesian mathematics and straight line vectors.

The basis for the PostGIS geographic type is a sphere. The shortest path between two points on the sphere is a great circle arc. That means that calculations on geographies (areas, distances, lengths, intersections, etc) must be calculated on the sphere, using more complicated mathematics.

Mercator is geometry based projection. Use geographic projection WGS-84 if you need to work with lat-lon coordinates.

Upvotes: 0

Related Questions