6

I have a point with coordinates x and y. I want to know all the points in a square around this point, with side L. For this, in postgresql/PostGIS, I use:

SELECT * FROM table_of_points WHERE (ST_Transform(the_geom,srid) && ST_MakeEnvelope(" + str(x-L) + ", " + str(y-L) + ", " + str(x+L) + ", " + str(y+L) + ", srid )

with srid being the Spatial Reference System Identifier.

What is the computational complexity of this query in PostGIS?

2
  • 1
    As a side note, another way to build a box around a point is to use ST_Expand, e.g.: ST_Expand(ST_SetSRID(ST_MakePoint(x, y), SRID), L)
    – Mike T
    Commented Nov 29, 2013 at 21:43
  • 1
    And in general, Mike's solution, avoiding string manipulations, is the preferred one. Commented Nov 30, 2013 at 3:45

1 Answer 1

4

If you have a spatial index built, it should be O(log(n))

4
  • 2
    If "n" refers to the number of points in the table, this answer cannot be correct in general, because it is possible for such a query to return all the points, which is a O(n) operation.
    – whuber
    Commented Nov 29, 2013 at 20:50
  • 1
    No, it refers to searching out one needle in the haystack, which I think is the usual question regards indexes, no? Commented Nov 30, 2013 at 3:44
  • I have a spatial index built. If n refers to the number of points in the table, @whuber has a point in my opinion. On the other hand, if we imagine that the total map of points is huge and that we look in a small square inside this map, with a spatial index built, wouldn't it be possible to express the complexity in terms of the mean density of points in the small square? (let's call it "d", the expected number of points in the square). In my example, d is not constant of course, but it stays in the same order of magnitude. So, O(log(d))?
    – Antonin
    Commented Nov 30, 2013 at 11:03
  • 1
    @Antonin Typically such searches take O(dlog(n)) computation: O(log(n)) for each of *d points. In certain circumstances, with certain data structures, the timing might be reducible to O(log(n) + d).
    – whuber
    Commented Nov 30, 2013 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.