SQL Algorithm to Compute Shortest Distance in a Plane

  • 时间:2020-09-28 16:28:51
  • 分类:网络文摘
  • 阅读:102 次

Given the following SQL Schema,

CREATE TABLE If Not Exists point_2d (x INT NOT NULL, y INT NOT NULL)
Truncate table point_2d
insert into point_2d (x, y) values ('-1', '-1')
insert into point_2d (x, y) values ('0', '0')
insert into point_2d (x, y) values ('-1', '-2')

Table point_2d holds the coordinates (x,y) of some unique points (more than two) in a plane.

Write a query to find the shortest distance between these points rounded to 2 decimals.

| x  | y  |
|----|----|
| -1 | -1 |
| 0  | 0  |
| -1 | -2 |

The shortest distance is 1.00 from point (-1,-1) to (-1,2). So the output should be:

| shortest |
|----------|
| 1.00     |

Note: The longest distance among all the points are less than 10000.

SQL to compute the shortest distance from array of points

We know the math formula to compute the distance between two points is: sqrt((a.x – b.x)^2 + (a.y – b.y)^2.

Given an array of points, we want to brute force every point except itself to compute the minimal distance. We can connect the table to itself, however need to exclude the computation of the same point to itself, which is zero obviously.

select 
  round(min(sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2))), 2) as 'shortest'
from 
  point_2d a, point_2d b
where
  a.x != b.x or a.y != b.y

We might put the min function first, i.e. sqrt(min(…)), which might slightly be faster as the sqrt (square root) is computed only once.

The above could be rewritten in the SQL inner join query:

select
  round(sqrt(min(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2)))), 2) as shortest
from
  point_2d p1
join
  point_2d p2 on p1.x != p2.x or p1.y != p2.y;

SQL Improvement by Avoiding Duplication

The above SQL query actually computes the same pair of points twice, namely, (A, B) and (B, A) should be only computed once as the distance is exactly the same.

We can always assume doing the computing with a bigger X value, thus:

select 
  round(min(sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2))), 2) as 'shortest'
from 
  point_2d a, point_2d b
where
  (a.x != b.x or a.y != b.y) and
  (a.x >= b.x)

Or, in the form of connecting two tables:

select 
  round(min(sqrt(pow(a.x - b.x,2) + pow(a.y - b.y,2))), 2) as 'shortest'
from 
  point_2d a, point_2d b
where
  (a.x != b.x or a.y != b.y) and
  (a.x >= b.x)

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
Design a Logger Rate Limiter in C++/Java  C++ Coding Exercise: Smallest Range of Array  Coding For Profit: 4 Types Of Websites To Consider Building  How to Compute the Projection Area of 3D Shapes?  How To Find The Ideal Monitor For Coders?  How to Partition an Array Into Three Parts With Equal Sum?  Compute the Sum of Even Numbers After Queries  How to Compute Nested List Weight Sum of Any Arrays?  7 Laws Every Blogger Must Know to Avoid Lawsuits  New App Protects You From Becoming A Victim Of White Collar Crim 
评论列表
添加评论