5

In my iOS app, I have many boxes (Quadrilaterals). I wonder what is the best data structure to detect if a touch on the screen is inside which box.

I have read about GKRTree and GKQuadTree in the GameplayKit. It appears that none of them are exactly what I need. GKRTree allows flexible quads but does not support query by a point. GKQuadTree supports query by a point, but does not seems allow flexible shapes/sizes.

EDIT: Add a sample code to demonstrate that the query with a box inside target box does not return the target box.

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: I came across this post, it is very much the same problem. I would like to find a good swift/objective-c implementation.

halfer
  • 19,824
  • 17
  • 99
  • 186
BSharer App - Share Books
  • 860
  • 10
  • 21

1 Answers1

2

I don't think any non-custom R-tree implementation will provide what you exactly need. You can use GKRTree to achieve what you want though.

  • Determine and insert the bounding boxes for each of your quadrilaterals to the GKRTree. I'm assuming not all of them are axis aligned boxes, if so you can use the actual shape as the bounding box.

  • Query a small enough rectangle where the user touches the screen. The shapes returned are candidate hits.

  • Iterate through the candidate hits to determine whether the touch point lies within the actual shape and not just its bounding box.

halileohalilei
  • 2,220
  • 2
  • 25
  • 52
  • Thanks for the note. That was exactly what I tried to do. However, it seems not working in my case. The issue is this: when I set the touch point (extended to a small rectangular) small, and it is inside a target box, that target box would NOT be returned by the GKRTree. In fact, even if I define a query rect intersect with my target box, it still would not return my target box. Here is my sample code. I am adding that sample code to my question. – BSharer App - Share Books Dec 28 '17 at 16:37
  • Now, I think I know what you mean by "a small enough rectangle" (a pretty big rec that will contain my target box). In my case, it will need some work to do so. As the target shape is not well defined. – BSharer App - Share Books Dec 28 '17 at 17:56
  • Every rectangle is a view isn't it ? – Abu Ul Hassan Jan 04 '18 at 13:05