Find nearest points with MySQL from points Table

Question

I have a DB Schema like this (from this tutorial by Google) -

So the actual points in a graph for them is like this-

What I want is to find points near a given point (by point_id) point ordered by distance

Location of a point (x,y) is (point_x,point_y) in DB

I want to solve it with MySQL because my DB is already in MySQL.

Update-

Finding distance of 2 points is so easy like this-

I want to sort on distance with MySQL.

Re-

For removing the confusions, I want the points inside the circle, later. But now I want to find only the sorted points.

So u can ignore the circles.

I don't have any idea how to do it, can anyone please help?

It is a common question to find distance between 2 points, it is given in updated question — S M Abrar Jahin
– S M Abrar Jahin, Commented Mar 16, 2016 at 4:53
I didn't ask for that. You marked a circle. Probably you want all those points inside the circle. That's why I asked what's your criteria to grab those points? — 1000111
– 1000111, Commented Mar 16, 2016 at 4:56
Yes, I want the points inside the circle, later. But now I want to find only the sorted points — S M Abrar Jahin
– S M Abrar Jahin, Commented Mar 16, 2016 at 4:57

Community · Accepted Answer · 2017-05-23 11:54:25Z

13

I have found a better solution than @1000111 's solution.

There is custom DB type in MySQL for this kind of data which gives a better performance.

OpenGIS in MySQL is perfect for this.

Functions are given here.

An illustrative definition is given in this StackOverflow question.

My solution is like this-

DB Table-

CREATE TABLE geoTable
(
    id INT(6) UNSIGNED AUTO_INCREMENT PRIMARY KEY,
    name VARCHAR(30) NOT NULL,
    geoPoint POINT NOT NULL,
    SPATIAL INDEX(geoPoint)
) ENGINE=MyISAM;


INSERT INTO geoTable (name, geoPoint)
VALUES
  ( "A", GeomFromText('POINT(0.1 -1.01)') ),
  ( "B", ST_GeomFromText('POINT(56.31 2.81)') ),
  ( "C", ST_GeomFromText('POINT(11.1 1.176)') ),
  ( "ui", ST_GeomFromText('POINT(9.1 2.1)') );

SQL Query-

SELECT
  id,
  name,
  X(geoPoint) AS "latitude",
  Y(geoPoint) AS "longitude",
  (
    GLength(
      LineStringFromWKB(
        LineString(
          geoPoint, 
          GeomFromText('POINT(51.5177 -0.0968)')
        )
      )
    )
  )
  AS distance
FROM geoTable
  ORDER BY distance ASC;

An example SQL Fiddle is given here.

See the execution time-

For 150 entry, it is only 13ms.

edited May 23, 2017 at 11:54

CommunityBot

11 silver badge

answered Mar 17, 2016 at 9:30

S M Abrar Jahin

14.7k24 gold badges116 silver badges170 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Hendy Irawan Over a year ago

Why the LineStringFromWKB ? Without it, the query runs fine with exactly same result

Sam Barnum Over a year ago

If your table is very large, you might filter it using the MBRContains function, before sorting, as this can make use of SPATIAL indexes.

krhitesh Over a year ago

LineStringFromWKB Why use it? Can you please explain?

Amin Mirakhorli Over a year ago

How about high dimensions?

Mahdi Esmaeili Over a year ago

ST_Distance( geoPoint , 'POINT(51.5177 -0.0968)' ) OR ST_Distance_Sphere( geoPoint , 'POINT(51.5177 -0.0968)' )

1000111 · Accepted Answer · 2016-03-16 05:43:17Z

1

Try this query please [a straight forward approach]:

Suppose, you want to find the nearest 20 points of the point having point_id = 5

SET @givent_point_id := 5;

SELECT 
P1.point_id,
P1.point_name,
P1.point_x,
P1.point_y,
(POW(ABS((P2.point_x - P1.point_x)),2) + POW(ABS((P2.point_y - P1.point_y)),2)) AS sqr_distance
FROM Point P1,
    (SELECT point_x,point_y FROM Point WHERE point_id = @givent_point_id) P2
WHERE P1.point_id <> @givent_point_id
ORDER BY sqr_distance
LIMIT 20;

Demo Here

More: You may have a look at MySQL SPATIAL DATATYPE.

MySQL spatial indexes use R-tree as data structure which is specially designed for spatial access methods.

R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

edited Mar 16, 2016 at 5:43

answered Mar 16, 2016 at 5:00

1000111

13.5k2 gold badges32 silver badges43 bronze badges

6 Comments

S M Abrar Jahin Over a year ago

Sorry to say, I can't use this straight forward way. Because it is too slow and if the total points> 10000 then we can't expect an answer from this query

S M Abrar Jahin Over a year ago

Because it is server, so may be 1000 request comes in 1 sec and there may be 100000 points. SO this procedure will fail

S M Abrar Jahin Over a year ago

No, it is DB budy, so we have to apply some algo to find result in a efficient way, not this way

1000111 Over a year ago

Have you run this query? What's the execution time? You may share the Explain ... result of this query. @AbrarJahin

S M Abrar Jahin Over a year ago

There is only 4 points now, so u can't compare. Can compare if u have 10000 points or more. NP, let me try if there is any alternative, if not, I should have accept your answer. Thanks for your help

|

Collectives™ on Stack Overflow

Find nearest points with MySQL from points Table

Update-

Re-

2 Answers 2

An example SQL Fiddle is given here.

5 Comments

6 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

Update-

Re-

2 Answers 2

An example SQL Fiddle is given here.

5 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related