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

Question

我有一张包含图形边缘信息的表，以geometry linestring的形式呈现。查询select * from edge的空间结果如下图所示： 每个linestring总是由两个geometry points创建，并使用插入语句进行创建：

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

为了找到两点之间的最短路径，我按照c#中Dijkstra算法的方法实现了Dijkstra算法。然而，我发现STDistance()函数也能通过执行简单的查询来完成同样的任务。有人能给我一个提示，我如何使用像我描述的对象与STDistance？我找到的每个示例都是使用从3个点创建的linestrings。

我有困难在拥有以下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）和给定形状之间的距离，而我的目的是从一个点到另一个点计算边长，有什么线索吗？

- Mithrand1r

---

给定一组节点（表示为点）和边缘（节点之间的简单关系表），但实际上在T-SQL中实现整个算法似乎是一个巨大的挑战。在我看来，一旦数据以我上面描述的形式存储，按照你指向的链接中描述的算法实现并不太困难。 - Ben Thul

我成功地将附图中可见的10个线串组合成一个形状（编辑后的问题），现在我需要计算一个形状内两点之间的最短距离。有什么想法？ :) - Mithrand1r

STDistance不计算路径距离，它计算两个形状之间的最小直线距离。可能是一个误解？ - usr

如果STDistance无法完成，是否有其他方法可以计算它？ - Mithrand1r

对于几何（不是地理）而言，STDistance 所做的就是简单的三角函数。如果你真的想在 SQL 上实现这个功能，就必须像 @BenThul 建议的那样，在 T-SQL 中创建算法。 - psousa

Answer 1

Code Kata。像其他评论中所说的那样，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

- MonkeyPushButton