python - 在 Python 中从 rtree 中删除二维点

Question

我正在尝试将 2D 点存储在 rtree(版本 0.8.2)中，然后使用 Python 删除它们。我知道 rtree 适用于矩形(或 3D 中的框)，但我猜点是矩形的子集。

我从 rtree 中删除项目时出现奇怪的行为。下面的脚本显示了行为:

from rtree import index as rtindex

def pt2rect(pt):
    return pt[0], pt[1], pt[0], pt[1]

pts = [(0.0, 0.0), (1.0, 1.0), (0.0, 1.0)]
rt = rtindex.Index()

# Add the points
[rt.add(0, pt2rect(pt)) for pt in pts]
print [r.bbox for r in list(rt.nearest((0, 0), 10, True))]

# Remove the same points
for pt in pts:
    rt.delete(0, pt2rect(pt))
    print pt2rect(pt), [r.bbox for r in list(rt.nearest((0, 0), 10, True))]

输出是:

True
[[0.0, 0.0, 0.0, 0.0], [0.0, 1.0, 0.0, 1.0], [1.0, 1.0, 1.0, 1.0]]  # Whole index
(0.0, 0.0, 0.0, 0.0) [[0.0, 1.0, 0.0, 1.0], [1.0, 1.0, 1.0, 1.0]]  # <-- Ok
(1.0, 1.0, 1.0, 1.0) [[1.0, 1.0, 1.0, 1.0]]  # <-- Wrong point deleted!
(0.0, 1.0, 0.0, 1.0) [[1.0, 1.0, 1.0, 1.0]]  # <-- Ok, as it's not found.

来自文档(http://toblerity.org/rtree/class.html):

delete(id, coordinates) Deletes items from the index with the given 'id' within the specified coordinates.

Parameters:

id – long integer A long integer that is the identifier for this index entry. IDs need not be unique to be inserted into the index, and it is up to the user to ensure they are unique if this is a requirement.

coordinates – sequence or array Dimension * 2 coordinate pairs, representing the min and max coordinates in each dimension of the item to be deleted from the index. Their ordering will depend on the index’s interleaved data member. These are not the coordinates of a space containing the item, but those of the item itself. Together with the id parameter, they determine which item will be deleted. This may be an object that satisfies the numpy array protocol.

但是可以看出，在输出的第 4 行中删除了具有给定 id 但不在给定坐标内的点。

文档还明确指出，id 在插入或删除时不需要是唯一的。 (示例中重复的 0 == id 是故意的，因为我的应用程序需要重复的 id。同一“事物”的多个点。)

还确认可以使用 xmin == xmax 和 ymin == ymax 对点进行索引。

我是不是使用了错误的库，或者 libspatialindex(Python rtree 背后的二进制库)的行为与 rtree 文档状态不同？

Answer 1

不要将重复的 id 分配给不同的对象。

它正在删除它在叶中找到的第一个具有匹配id的对象(检查libspatialindex源代码，Leaf::deleteData如果你不要相信我)。 坐标仅用于找到要从中删除的正确叶子。你所有的 id 都是 0，所以它总是从叶子中删除第一个元素。后面的删除失败了，因为你的树的边界框现在是 [0.0,1.0,1.0,1.0]，y=0.0 的点不能在这个叶子中。

尝试

[rt.add(id, [x[0], x[1], x[0], x[1]]) for id, x in enumerate(pts)]

和

for id, x in enumerate(pts):
    rt.delete(id, [x[0], x[1], x[0], x[1]])
    print [x.bbox for x in list(rt.nearest([0, 0], 10, True))]

请注意，rtree 模块的文档具有误导性。

Deletes items from the index with the given 'id' within the specified coordinates.

Parameters:

• id – long integer A long integer that is the identifier for this index entry. IDs need not be unique to be inserted into the index, and it is up to the user to ensure they are unique if this is a requirement.
• coordinates – sequence or array Dimension * 2 coordinate pairs, representing the min and max coordinates in each dimension of the item to be deleted from the index. Their ordering will depend on the index’s interleaved data member. These are not the coordinates of a space containing the item, but those of the item itself. Together with the id parameter, they determine which item will be deleted. This may be an object that satisfies the numpy array protocol.

(强调已添加。)

这不是说 id 不需要是唯一的删除。它说您可以插入具有相同 id 的多个条目，但它并没有说删除是可预测的。 ;-) “确定”也含糊不清。坐标用于找到正确的叶子，然后删除该叶子中第一个匹配的 id。 (从 libspatialindex 的源代码来看)因此，id 必须是唯一的才能可靠地删除。