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

Question

我有一个表格,其中包含有关图形边缘的信息geometry linestring.查询的空间结果select * from edge如下所示 linestring始终geometry points使用insert语句创建EACH,如:

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

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

在我已经让我们说3 linestrings如下的情况下,我很难使用示例:

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)'))

并发现从最短路径1 1到1 4

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

SELECT geometry::UnionAggregate(linestring) FROM edge

我变形了:

0x000000000104160000002242C0E56A32834050D72864D98D714000000000003082400000000000B0784000000000000071400000000000A075402242C0E56A32834050D72864D98D7140CFB591AC8CBA83402B7FD245B3976B400000000000F087400000000000806F402242C0E56A32834050D72864D98D7140CFB591AC8CBA83402B7FD245B3976B40000000000000854000000000004053400000000000E06940000000000080504000000000009076400000000000C06340F89FD09A6BDC8140A4AC72B9CEDB69404AAD03D8122784408FC4879BE4996540CFB591AC8CBA83402B7FD245B3976B40F89FD09A6BDC8140A4AC72B9CEDB694000000000000071400000000000A075400000000000E06940000000000080504000000000001073400000000000C05E4000000000009076400000000000C06340000000000000854000000000004053404AAD03D8122784408FC4879BE49965400000000000688B40000000000040504004000000010000000001040000000108000000010A00000005000000FFFFFFFF0000000005000000000000000002000000000100000002000000000200000002000000000300000002

现在我使用STDistance如下:

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

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

Answer 1

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

请注意，这只是证明可以做到这一点，而不是建议应该这样做。您现有的 C# 代码可能更简单、更快。

感谢您给我机会学习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