在SQL Server中使用STDistance查找图中的最短路径

I have a table which contain information about edges of the graph in form of geometry linestring. Spatial result of query select * from edge look like this 在SQL Server中使用STDistance查找图中的最短路径 EACH linestring is created always from two geometry points with insert statement like:

我有一个表格,其中包含几何线串形式的图表边缘信息。查询select *的空间结果从边看起来像这样EACH线串总是从两个几何点创建,插入语句如下:

INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 1 ,1 2)'))

In order to finding shortest path between two points I have implemented Dijkstra algorith according to Dijkstra in c#, However I have found out about STDistance() function which is ment to do the same thing just by executing simple query. Could anyone give me a hint how could I use STDistance with objects created like I described? Every example I find use linestrings created from 3 points.

为了找到两点之间的最短路径,我在c#中根据Dijkstra实现了Dijkstra算法,但是我已经发现了STDistance()函数,它只是通过执行简单查询来做同样的事情。任何人都可以给我一个提示我如何使用STDistance与我描述的对象创建?我找到的每个例子都使用从3点创建的线串。

I have difficulty using example in the situation I have lets say 3 linestrings as bellow:

在我已经让3个线串如下所示的情况下,我很难使用示例:

INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 1 ,1 2)'))
INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 2 ,1 3)'))
INSERT INTO edge VALUES( geometry::Parse('LINESTRING(1 3 ,1 4)'))

and finding shortest path from 1 1 to 1 4

并找到从1 1到1 4的最短路径

Edit: I have suceeded with combining all linestrings into one shape by:

编辑:我已经成功通过以下方式将所有线串组合成一个形状:

SELECT geometry::UnionAggregate(linestring) FROM edge

i get shape :

我变形了:

0x000000000104160000002242C0E56A32834050D72864D98D714000000000003082400000000000B0784000000000000071400000000000A075402242C0E56A32834050D72864D98D7140CFB591AC8CBA83402B7FD245B3976B400000000000F087400000000000806F402242C0E56A32834050D72864D98D7140CFB591AC8CBA83402B7FD245B3976B40000000000000854000000000004053400000000000E06940000000000080504000000000009076400000000000C06340F89FD09A6BDC8140A4AC72B9CEDB69404AAD03D8122784408FC4879BE4996540CFB591AC8CBA83402B7FD245B3976B40F89FD09A6BDC8140A4AC72B9CEDB694000000000000071400000000000A075400000000000E06940000000000080504000000000001073400000000000C05E4000000000009076400000000000C06340000000000000854000000000004053404AAD03D8122784408FC4879BE49965400000000000688B40000000000040504004000000010000000001040000000108000000010A00000005000000FFFFFFFF0000000005000000000000000002000000000100000002000000000200000002000000000300000002

Now I use STDistance as follows:

现在我使用STDistance如下:

SELECT (geometry::UnionAggregate(linestring)).STDistance(geometry::STGeomFromText('POINT(0 0)', 0)) FROM edge

However the return value is about distance between point (0,0) and presented shape, when my intend is to count edges length from one point to the other, any clues?

然而,返回值是关于点(0,0)和呈现形状之间的距离,当我打算计算从一个点到另一个点的边长时,任何线索?

1 个解决方案

#1

Code Kata. As others have said in comments STDistance will give you the minimum straight line distance between two geometry objects, not a path through a graph. Implementing Dijkstra in Sql is beyond me, but the brute force method is acceptable for small numbers of nodes such as you've demonstrated. This code calculates all paths within the graph from A to B and then selects the shortest.

代码卡塔。正如其他人在评论中所说,STDistance将为您提供两个几何对象之间的最小直线距离,而不是图表中的路径。在Sql中实现Dijkstra超出了我的范围,但是对于少数节点来说,暴力方法是可以接受的,例如你已经演示过的。此代码计算图形中从A到B的所有路径,然后选择最短路径。

Please note that this is a only a proof that it can be done, not a recommendation that it should be done. Your existing code in c# is probably simpler and quicker.

请注意,这只是证明它可以完成,而不是建议它应该完成。您在c#中的现有代码可能更简单,更快捷。

Thanks for giving me an opportunity to learn about geometry functions in sql server.

感谢您让我有机会了解sql server中的几何函数。

-- Declare and set parameters.
DECLARE @start geometry, @end geometry

SET @start = geometry::STGeomFromText('POINT(-1 1)', 0);
SET @end = geometry::STGeomFromText('POINT(1 3)', 0);

-- Caching of ST function results and for reversibility.
DECLARE @segments TABLE  (
edge geometry,
start_point geometry,
end_point geometry,
[weight] float
)
INSERT @segments
        ( edge, start_point, end_point, [weight])
SELECT e, e.STStartPoint(), e.STEndPoint(),  e.STLength() FROM edge UNION ALL 
-- Can traverse edges both ways unless we're in a directed graph?
SELECT e, e.STEndPoint(), e.STStartPoint(),  e.STLength() FROM edge 

-- We need to know number of edges for some bookkeeping later.
DECLARE @total_edges INT
SELECT @total_edges = COUNT(*) FROM edge;

-- Meat of the procedure. Find all sensible paths from @start to @end allowed by the graph, using a recursive common table expression.
WITH cte (path, start_point, end_point, [weight], segments_traversed) AS (
SELECT 
    edge AS path,
    start_point, 
    end_point, 
    [weight] ,
    1 AS segments_traversed
FROM 
    @segments 
WHERE 
    @start.STEquals(start_point) = 1 UNION ALL 
SELECT 
    c.path.STUnion(s.edge) AS PATH,
    s.start_point, 
    s.end_point, 
    s.[weight] + c.[weight] AS weight,
    c.segments_traversed + 1 AS segments_traversed
FROM cte c 
    INNER JOIN @segments s ON 
        -- next edge must start where this one ended.
        s.start_point.STEquals(c.end_point) = 1 AND 
        -- terminate paths that hit the endpoint.
        c.start_point.STEquals(@end) = 0 AND
        -- if we traveled more than the number of edges there's surely a better path that doesn't loop!    
        -- also acts as a guarantee of termination.  
        c.segments_traversed < @total_edges
)
SELECT TOP 1
    path 
FROM 
    cte c
WHERE 
    -- Restrict to paths ending at end point.
    c.end_point.STEquals(@end) = 1
ORDER BY 
    weight ASC

#1