公开(公告)号：US09235906B2

公开(公告)日：2016-01-12

申请号：US13632003

申请日：2012-09-30

Applicant: Apple Inc.

Inventor： Guillaume A. Carbonneau ,  Vincent Dumont

IPC: G09G5/00 ,  G06T11/00 ,  G01C21/32 ,  G06F17/30

CPC classification number: G06T11/00 ,  G01C21/32 ,  G06F17/30241

Abstract: A method is provided that utilizes a parallel processing system to determine whether different geometries intersect each tile in a map hierarchy. The method receives a description of a geometry and an identification of a tile in a tile tree. The method utilizes an available processing unit to determine whether the geometry intersects the tile. When the geometry intersects the tile and the tile has child tiles, the method stores several task descriptions that can be assigned to any processing units in the parallel processing system. Each task description includes the description of the portion of the geometry that overlaps the tile and an identification of one of the child tiles of the tile. The method then assigns each of the tasks to an available processing unit to continue down the tree hierarchy to determine whether each child tile intersects a portion of the geometry.

Abstract translation: 提供了一种利用并行处理系统来确定不同几何是否与地图层次结构中的每个瓦片相交的方法。 该方法接收瓦片树中的几何图形和瓦片的标识的描述。 该方法利用可用的处理单元来确定几何是否与瓦片相交。 当几何与瓦片相交并且瓦片具有子瓦片时，该方法存储可以分配给并行处理系统中的任何处理单元的若干任务描述。 每个任务描述包括与该瓦片重叠的几何的部分的描述和该瓦片的一个子瓦片的标识。 然后，该方法将每个任务分配给可用处理单元以继续向下树结构层次以确定每个子图块是否与几何的一部分相交。

公开(公告)号：US20130328941A1

公开(公告)日：2013-12-12

申请号：US13632003

申请日：2012-09-30

Applicant: APPLE INC.

Inventor： Guillaume A. Carbonneau ,  Vincent Dumont

IPC: G06F15/80 ,  G09G5/00

CPC classification number: G06T11/00 ,  G01C21/32 ,  G06F17/30241

Abstract: A method is provided that utilizes a parallel processing system to determine whether different geometries intersect each tile in a map hierarchy. The method receives a description of a geometry and an identification of a tile in a tile tree. The method utilizes an available processing unit to determine whether the geometry intersects the tile. When the geometry intersects the tile and the tile has child tiles, the method stores several task descriptions that can be assigned to any processing units in the parallel processing system. Each task description includes the description of the portion of the geometry that overlaps the tile and an identification of one of the child tiles of the tile. The method then assigns each of the tasks to an available processing unit to continue down the tree hierarchy to determine whether each child tile intersects a portion of the geometry.

Abstract translation: 提供了一种利用并行处理系统来确定不同几何是否与地图层次结构中的每个瓦片相交的方法。 该方法接收瓦片树中的几何图形和瓦片的标识的描述。 该方法利用可用的处理单元来确定几何是否与瓦片相交。 当几何与瓦片相交并且瓦片具有子瓦片时，该方法存储可以分配给并行处理系统中的任何处理单元的若干任务描述。 每个任务描述包括与该瓦片重叠的几何的部分的描述和该瓦片的一个子瓦片的标识。 然后，该方法将每个任务分配给可用处理单元以继续向下树结构层次以确定每个子图块是否与几何的一部分相交。

公开(公告)号：US20130328861A1

公开(公告)日：2013-12-12

申请号：US13631998

申请日：2012-09-30

Applicant: APPLE INC.

Inventor： Okan Arikan ,  Vincent Dumont ,  Guillaume A. Carbonneau ,  Billy P. Chen

IPC: G06T17/05

CPC classification number: G06T11/20 ,  G01C21/32 ,  G06T7/0004 ,  G06T11/00 ,  G06T11/60 ,  G06T17/05 ,  G09G5/00

Abstract: Some embodiments provide a method for generating road data. The method receives data regarding several road segments and several junctions for a map region. The road segments include a first road segment and a second road segment that intersect at a particular junction. The method determines whether the first road segment and the second road segment are separate segments of a same road. When the first and second road segments are separate segments of the same road, the method defines an aggregate road that references the first and second road segments. In some embodiments, the method determines whether the first and second road segments are separate segments of the same road by using location data and road properties of the first and second road segments. In some embodiments, the aggregate road is stored as an ordered list of road segments that link together at junctions.

Abstract translation: 一些实施例提供了一种用于生成道路数据的方法。 该方法接收关于地图区域的几个路段和几个路口的数据。 路段包括在特定交叉点相交的第一路段和第二路段。 该方法确定第一路段和第二路段是否是相同道路的分段。 当第一和第二路段是相同道路的独立段时，该方法定义参考第一和第二路段的总路。 在一些实施例中，该方法通过使用第一和第二路段的位置数据和道路属性来确定第一和第二路段是否是相同道路的分段。 在一些实施例中，集合道路被存储为在交叉点处连接在一起的路段的有序列表。

公开(公告)号：US09395193B2

公开(公告)日：2016-07-19

申请号：US13632004

申请日：2012-09-30

Applicant: Apple Inc.

Inventor： Guillaume A. Carbonneau ,  Vincent Dumont ,  Anuj Dhamija ,  Denis Laprise ,  Okan Arikan ,  James A. Howard

IPC: G06T11/20 ,  G01C21/32 ,  G06T11/00

CPC classification number: G01C21/32 ,  G06T11/00

Abstract: A process is provided that reduces the amount of data for a map tile that could not be displayed separately on the scale of that tile. The process generates an equivalent of the road data by rasterizing the vectors representing road segments lying within a tile and generating a connectivity mask that keeps track of which pixels are connected to which other pixels along the vectors. The process constructs an undirected graph. Each “on” pixel of the undirected graph represents a vertex and the vertices are connected by edges generated from the connectivity graph, but without a set direction. The process traces the undirected graph to generate chains of connected road segments and takes the chains and simplifies them in order to reduce the amount of data that must be stored and transmitted for the tile in order to produce all the visible roads of the tile at that scale.

Abstract translation: 提供了一个过程，减少了无法在该图块的比例上单独显示的地图图块的数据量。 该过程通过光栅化表示位于瓦片内的道路段的矢量来生成道路数据的等价物，并且生成连接掩模，该连接掩模跟踪哪些像素连接到沿向量的哪个其他像素。 该过程构建无向图。 无向图中的每个“on”像素表示顶点，并且顶点通过从连接图生成的边缘连接，但没有设置方向。 该过程跟踪无向图，以产生连接的路段的链，并采取链并简化它们，以减少必须为瓦片存储和传输的数据量，以便生成瓦片的所有可见道路 规模。

公开(公告)号：US20130328879A1

公开(公告)日：2013-12-12

申请号：US13632004

申请日：2012-09-30

Applicant: APPLE INC.

Inventor： Guillaume A. Carbonneau ,  Vincent Dumont ,  Anuj Dhamija ,  Denis Laprise ,  Okan Arikan ,  James A. Howard

IPC: G06T11/20

CPC classification number: G01C21/32 ,  G06T11/00

Abstract: A process is provided that reduces the amount of data for a map tile that could not be displayed separately on the scale of that tile. The process generates an equivalent of the road data by rasterizing the vectors representing road segments lying within a tile and generating a connectivity mask that keeps track of which pixels are connected to which other pixels along the vectors. The process constructs an undirected graph. Each “on” pixel of the undirected graph represents a vertex and the vertices are connected by edges generated from the connectivity graph, but without a set direction. The process traces the undirected graph to generate chains of connected road segments and takes the chains and simplifies them in order to reduce the amount of data that must be stored and transmitted for the tile in order to produce all the visible roads of the tile at that scale.

Abstract translation: 提供了一个过程，减少了无法在该图块的比例上单独显示的地图图块的数据量。 该过程通过光栅化表示位于瓦片内的道路段的矢量来生成道路数据的等价物，并且生成连接掩模，该连接掩模跟踪哪些像素连接到沿向量的哪个其他像素。 该过程构建无向图。 无向图中的每个“on”像素表示顶点，并且顶点通过从连接图生成的边缘连接，但没有设置方向。 该过程跟踪无向图，以产生连接的路段的链，并采取链并简化它们，以减少必须为瓦片存储和传输的数据量，以便生成瓦片的所有可见道路 规模。