在道路网路内编码一连续路径的方法、电脑程式元件及编码一连续路径位置的系统

摘要

本发明描述一种对一道路网路内之一连续路径编码的有效方法。理想地，待编码之该路径能够于一数位地图内完全表示且可表达为存在于该数位地图中及经相继排序的线路及/或片段之一路径清单。该方法包含以下步骤：(i)在一路线搜寻清单中储存一开始位置，该开始位置为以下各者中之一者：(a)首先出现在该路径清单中之线路或片段，或在该第一线路或片段之开始节点为人工的情况下，出现在该数位地图中之具有一真实开始节点且视情况经由其他人工节点而直接导向至该第一线路或片段的第一线路或片段，或(b)亦出现在该路径清单中之一最近识别的偏差线路或片段；(ii)在该数位地图内判定自该开始位置之该开始节点且包括该开始位置至该路径清单中之最后线路或片段的一结束节点之一路径，该路径系根据一演算法而判定，(iii)针对同一性而将如此判定之最短路径与该路径清单比较，且在不存在同一性之情况下，识别至少一偏差线路或片段，该至少一偏差线路或片段为该路径清单之一部分且具有一表示该数位地图中之一相交的开始节点但并非首先出现在该路径清单中之线路或片段，且若该偏差线路或片段不在出现在该路径清单中之该最后线路或片段的该结束节点处终止，则使用该偏差线路或片段来重复步骤(i)，及(iv)将该路径清单中之该最后线路或片段在尚未储存之情况下储存于该路线搜寻清单中。最佳地，所使用之该演算法为一最短路径演算法。

主权项

一种在一道路网路内编码(encoding)一连续路径(path)之方法，该路径于一数位地图(digital map)内完全表示(presented)且可表达为存在于该数位地图中及经相继排序(consecutively ordered)的线路(lines)及/或片段(segments)之一路径清单，该方法包含以下步骤：(i)在一路线搜寻清单(route search list)中储存一开始位置(start position)，该开始位置为以下各者中之一者：首先出现在该路径清单中之线路或片段，或当首先出现在该路径清单中的该线路或片段之开始节点(start node)为虚拟的(artificial)，出现在该数位地图中的第一线路或片段，该数位地图具有一真实(real)开始节点且随选地(optionally)经由其他虚拟节点而直接导向至该第一线路或片段，出现在该路径清单中之一最近识别的偏差(deviation)线路或片段，(ii)在该数位地图内自该开始位置之该开始节点判定(determining)一路径，且将该开始位置包含于该路径清单中之最后(last)线路或片段的一结束(end)节点，该路径系根据一演算法(algorithm)而判定，(iii)为一致性(identity)，将经上述判定之最短路径与该路径清单比较，且在不存在一致性之情况下，识别至少一偏差线路或片段，该至少一偏差线路或片段为该路径清单之一部分且具有表示该数位地图中之一相交(intersection)的一开始节点但并非首先出现在该路径清单中之线路或片段，且若该偏差线路或片段并非终止于出现在该路径清单中之该最后线路或片段的该结束节点处，则使用该偏差线路或片段来重复步骤(i)，及(iv)若该最后线路或片段尚未储存，将该路径清单中之该最后线路或片段储存于该路线搜寻清单中。