供应四叉树的GPS数据到应用的最佳选择吗？ [英] Best option for supplying Quadtree GPS Data to an app?

问题描述

我们有> 25 MB的静态四叉树数据，我们希望提供尽可能的跨平台的应用程序，然后可以通过应用程序code被搜索得到的位置信息贴近用户的当前GPS位置的部分

我们想搜索的数据，而无需加载所有的数据到内存中，在快速的时间，最好不重新发明轮子。

我们已经看过提供使用R-树在SQLite，让这个数据库，这听起来像这将是理想的，但显然这些都不在了Android提供的SQLite的版本。航运我们自己的Andr​​oid版本的SQLite（包含R树结构）听起来像很多痛苦的 - 但我们很想听听别人的这方面的经验。

我们可以创建一个文件系统的模型，但我们的数据可能会非常大，感觉就像我们可能会碰到麻烦不当使用文件系统这样的。

我们都希望有可能是已经为此目的设计，也许现有搜索该爪哇/物镜-C库一些其他的文件格式。任何人都可以带我们去这样的事情？

另一个显而易见的解决方案是创建我们自己的文件格式和检索系统，但是这很可能是大量的工作。

该应用程序实际上是一个科尔多瓦/ PhoneGap的应用程序，将可用于iOS和Android，但它不是一个问题，编写本机插件为每个平台来处理这个问题。

在此先感谢

解决方案

忽略了问题的题外话方面，采用R树的数据在Android上，您需要编译的SQLite的NDK和出货不管是什么架构（S ）要支持。

然而，SQLite的的R树模块被实施为一个使用正常表来存储R-树数据的扩展。 处理的更新和重新平衡树R树中最复杂的部分;相比的是，搜索是微不足道的。 如果你想要做什么，但在搜索上的静态数据，你可以只手动实现它们。

借助源$ C ​​$ C 有这样一段话：

  

的R树表的数据库格式

     

的数据结构为单个虚拟的r-树表被存储在三个   本机的SQLite表声明如下。在每种情况下，％字符   在表名替换为R树的用户提供的名称   表中。

  CREATE TABLE％_node（nodeno INTEGER PRIMARY KEY，数据BLOB）
CREATE TABLE％_parent（nodeno INTEGER PRIMARY KEY，parentnode INTEGER）
CREATE TABLE％_rowid（ROWID INTEGER PRIMARY KEY，nodeno INTEGER）
 

有第r树结构的每个节点的数据存储在％_node   表。对于每个节点不是R-树的根节点，有   在％_parent一个表项关联与其父节点。   并且针对表中数据的各行中，有在％_rowid一个条目   表映射从条目的rowid到节点的id，它   存储在

     

的r树的根节点总是存在，即使第r树表是   空。根节点的nodeno始终为1，在所有其他节点   表必须是相同的大小作为根节点。每个节点的内容   格式如下：

     

  

1. 如果该节点是根节点（节点1），则第2个字节    节点包含的树深度为大端整数。    对于非根节点，前2个字节被闲置。

  

2. 接下来的2个字节包含的条目数当前    存储在节点。

  

3. 该节点的其余部分包含节点项。每个条目    由一个单一的8字节的整数，其后为偶数的    的4个字节的坐标。对于叶节点的整数的ROWID    的记录。对于内部节点是一个节点号    子页面。

  

有关的搜索，你就不需要在 _parent 或 _rowid 表。

该算法是这样的：

高清搜索（nodeno = 1，根= TRUE，tree_depth = -1，深度= 0）：     执行（选择数据X_node WHERE nodeno =？，[nodeno]）     如果根：         tree_depth = first_two_bytes     用于在数据输入：         如果entry.rectangle比赛：             如果深度== tree_depth：                 结果+ = entry.id             其他：                 搜索（entry.nodeno，假，tree_depth，深度+ 1）

We have >25 MB of static Quadtree Data that we would like to provide as part of a cross platform app, which can then be searched by the app code to get details of locations close to the user's current GPS position.

We would like to search the data without loading all of the data into memory, in a quick time, and ideally without reinventing the wheel.

We have looked at supplying a database using R-Trees in SQLite for this, which sounds like it would be ideal, but apparently these are not available in the SQLite version supplied with android. Shipping our own version of SQLite for android (that includes the R-Tree structures) sounds like a lot of pain - but we would be interested to hear about others' experience with this.

We could create a filesystem model, but our data could be very large and it feels like we might run into trouble mis-using the filesystem this way.

We are hoping there might be some other file format already designed for this purpose and perhaps java/obj-c libraries existing to search this. Can anyone point us to such a thing?

The other obvious solution is to create our own file format and searching system, but this would probably be a lot of work.

The app is actually a cordova/phonegap app that will be available for ios and android, but its not a problem to write a native plugin for each platform to handle this.

Thanks in advance

解决方案

Ignoring the off-topic aspects of the question, using R-tree data on Android requires that you compile SQLite with the NDK and ship it for whatever architecture(s) you want to support.

However, SQLite's R-tree module is implemented as an extension that uses 'normal' tables to store the R-tree data. The most complex part of handling R-trees is updating and rebalancing the tree; compared to that, searches are trivial. If you want to do nothing but searching on static data, you could just implement them manually.

The source code has this to say:

Database Format of R-Tree Tables

The data structure for a single virtual r-tree table is stored in three native SQLite tables declared as follows. In each case, the '%' character in the table name is replaced with the user-supplied name of the r-tree table.

CREATE TABLE %_node(nodeno INTEGER PRIMARY KEY, data BLOB)
CREATE TABLE %_parent(nodeno INTEGER PRIMARY KEY, parentnode INTEGER)
CREATE TABLE %_rowid(rowid INTEGER PRIMARY KEY, nodeno INTEGER)

The data for each node of the r-tree structure is stored in the %_node table. For each node that is not the root node of the r-tree, there is an entry in the %_parent table associating the node with its parent. And for each row of data in the table, there is an entry in the %_rowid table that maps from the entries rowid to the id of the node that it is stored on.

The root node of an r-tree always exists, even if the r-tree table is empty. The nodeno of the root node is always 1. All other nodes in the table must be the same size as the root node. The content of each node is formatted as follows:

1. If the node is the root node (node 1), then the first 2 bytes of the node contain the tree depth as a big-endian integer. For non-root nodes, the first 2 bytes are left unused.

2. The next 2 bytes contain the number of entries currently stored in the node.

3. The remainder of the node contains the node entries. Each entry consists of a single 8-byte integer followed by an even number of 4-byte coordinates. For leaf nodes the integer is the rowid of a record. For internal nodes it is the node number of a child page.

For searches, you would not need the _parent or _rowid tables.

The algorithm would look like this:

def search(nodeno = 1, root = True, tree_depth = -1, depth = 0):
    execute("SELECT data FROM X_node WHERE nodeno = ?", [nodeno])
    if root:
        tree_depth = first_two_bytes
    for entry in data:
        if entry.rectangle matches:
            if depth == tree_depth:
                result += entry.id
            else:
                search(entry.nodeno, False, tree_depth, depth + 1)

这篇关于供应四叉树的GPS数据到应用的最佳选择吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！