1

Sorry for the ambiguous title. This is not a duplicate from MySQL - Find points​ within radius from database . Here is the detailed problem:

I have a location database with indexed latitude and longitude values. I can freely add index and indexed computed column if needed.

I will be given a coordinates point and a distance (5km for example), I need:

  • Returns all points within 5km of the point.

  • OR if it is simpler, all points within a 5km-sided square on the map.

The requirement is for the database lookup operation to be as simple as it can. The precision is not at top priority. The result may be refined later at client-side, so it is preferably to return more result from server if needed.

The database I am using is SQL Server if it matters.

EDIT: Sorry I forgot another problem when posting the 1st post. I have another similar question:

Same rule applied, either circular or squared shape, now each target point has its own radius too. Let's say, point A has Lat, Lng and Radius properties and so on for B and C. Now I need to extract the points that has its shape collides with the source shape.

Luke Vo
  • 17,859
  • 21
  • 105
  • 181
  • 2
    This is what [spatial indexes](https://learn.microsoft.com/en-us/sql/relational-databases/spatial/spatial-indexes-overview?view=sql-server-2017) are for. – Vladimir Baranov May 06 '18 at 12:44
  • @VladimirBaranov hi, thanks, I didn't know about this. I am checking the article. In the meantime, could you check my edit for the 2nd question, if it could be solved with the same technique? – Luke Vo May 06 '18 at 12:45
  • 1
    Since you said that precision is not very important, you can replace a point+radius with several points that lie on that circle. As engineers say, octagon is a good approximation of a circle. If you do need precision, there are plenty built-in geography functions/methods, such as [STIntersects](https://learn.microsoft.com/en-us/sql/t-sql/spatial-geography/stintersects-geography-data-type?view=sql-server-2017). – Vladimir Baranov May 06 '18 at 12:51
  • 1
    You should try several approaches and test their performance. Spatial indexes support the following predicate forms: `geography1.STIntersects(geography2) = 1` ; `geography1.STEquals(geography2) = 1` ; `geography1.STDistance(geography2) < number` ; `geography1.STDistance(geography2) <= number` – Vladimir Baranov May 06 '18 at 13:02
  • Works great! This feature is wonderful and satisfied all my needs. Please post it as an answer. – Luke Vo May 06 '18 at 13:05

1 Answers1

1

SQL Server has a feature called spatial indexes.

Geography Methods Supported by Spatial Indexes

Under certain conditions, spatial indexes support the following set-oriented geography methods: STIntersects(),STEquals(), and STDistance(). To be supported by a spatial index, these methods must be used within the WHERE clause of a query, and they must occur within a predicate of the following general form:

geography1.method_name(geography2) comparison_operator valid_number

To return a non-null result, geography1 and geography2 must have the same Spatial Reference Identifier (SRID). Otherwise, the method returns NULL.

Spatial indexes support the following predicate forms:

geography1.STIntersects(geography2) = 1
geography1.STEquals(geography2) = 1
geography1.STDistance(geography2) < number
geography1.STDistance(geography2) <= number

Your geography objects can be simple points and it may be enough, since you said that you don't need high precision, especially if the radius of a point is much smaller than 5km distance.

You can also approximate your circles with few points, for example, octagons may be a good enough approximation.

Have a look at available spatial types and methods, try several approaches and test their performance.

You may also find methods STBuffer and/or BufferWithTolerance useful to build circles around your points.

Vladimir Baranov
  • 31,799
  • 5
  • 53
  • 90
  • Not sure if I should ask another question or post here. I tried to Google but none said about Compound Index of a spatial index and a normal Index (let's say I have a `Enabled` bit column). Is it possible or I am thinking it in a wrong way? There seem to be no documentation or question about this one. – Luke Vo May 06 '18 at 13:36
  • @LukeVo, I don't think you can create an index that mixes spatial and non-spatial columns. [`CREATE SPATIAL INDEX`](https://learn.microsoft.com/en-us/sql/t-sql/statements/create-spatial-index-transact-sql?view=sql-server-2017) syntax suggests that you can't mix them. – Vladimir Baranov May 06 '18 at 13:40
  • Thanks for clarifying. Please tell me your experience if you have come across this use case (compound index). If not, still thank you. – Luke Vo May 06 '18 at 13:50
  • 1
    I don't have a lot of experience with spatial indexes. Based on the docs you can't have spatial and non-spatial columns in the same index. There are other indirect ways to achieve similar performance effect. For example, split a table into two tables for each value of the `Enabled` column. It is also quite possible that having two independent indexes (spatial and non-spatial) may be enough. – Vladimir Baranov May 06 '18 at 14:04