在我的 iOS 应用程序中,我有很多盒子(四边形)。我想知道检测屏幕上的触摸是否在哪个框内的最佳数据结构是什么。

我在 GameplayKit 中阅读了 GKRTree 和 GKQuadTree。似乎它们都不是我所需要的。 GKRTree 允许灵活的四边形,但不支持点查询。 GKQuadTree 支持按点查询,但似乎不允许灵活的形状/大小。

编辑:添加示例代码以演示在目标框中带有框的查询不会返回目标框。

import UIKit
import GameplayKit

// target rec.
let rec1v1 = vector_float2(0.0, 0.0)
let rec1v2 = vector_float2(10.0, 10.0)
// outside target rec
let rec2v1 = vector_float2(11.0, 11.0)
let rec2v2 = vector_float2(12.0, 12.0)
//small box inside target rec
let rec3v1 = vector_float2(1.0, 1.0)
let rec3v2 = vector_float2(2.0, 2.0)
// small box intersect with target rec
let rec4v1 = vector_float2(9.0, 9.0)
let rec4v2 = vector_float2(11.0, 11.0)


var mytree = GKRTree<NSString>(maxNumberOfChildren: 3)
mytree.addElement("rec1v1",
              boundingRectMin: rec1v1,
              boundingRectMax: rec1v2,
              splitStrategy: GKRTreeSplitStrategy.linear)
let t1 = mytree.elements(inBoundingRectMin: rec2v1, rectMax: rec2v2) // return [] (outside)
let t2 = mytree.elements(inBoundingRectMin: rec3v1, rectMax: rec3v2) // return [] (inside target box but smaller)
let t3 = mytree.elements(inBoundingRectMin: rec1v1, rectMax: rec1v2) // return ["rec1v1"] (same box)
let t4 = mytree.elements(inBoundingRectMin: rec4v1, rectMax: rec4v2) // return [] (intersect with target box but not containing)

EDIT2:我遇到了 this post ,这是非常相同的问题。我想找到一个好的 swift/objective-c 实现。

最佳答案

我认为任何非自定义 R-tree 实现都不会提供您真正需要的东西。您可以使用 GKRTree 来实现您想要的。

  • 确定每个四边形的边界框并将其插入 GKRTree 。我假设并非所有这些都是轴对齐的框,如果是这样,您可以使用实际形状作为边界框。
  • Query 一个足够小的矩形,用户可以在其中触摸屏幕。返回的形状是候选命中。
  • 遍历候选命中以确定接触点是否位于实际形状内,而不仅仅是其边界框。
  • 10-06 13:25