In Qt, how to efficiently determine that a point is inside of one of rectangles?

Question

There is a large set of rectangles. Given a point, I need to quickly find if this point belongs to at least one of the rectangles, and find one.

Answer 1

A space partitioning index would do the trick. You could, in a pinch, add all the rectangles to the graphics scene — it will index them for you and hit tests will have O(log(N)) cost. You’d want a “low cost” item like:

class RectItem : public QGraphicsItem {
  QSizeF size;
public:
  RectItem(const QRectF &r = {}) : size(r.size()) {
    setFlag(ItemHasNoContents);
    setPos(r.topLeft());
  }
  RectItem(const RectItem &o) :
    RectItem(o.boundingRect()) {
    if (o.scene()) o.scene()->addItem(this);
  }
  void setRect(const QRect &r) {
    prepareGeometryChange();
    setPos(r.topLeft());
    size = r.size();
  }

  QRectF boundingRect() const override {
    return {{}, size};
  }
  void paint(QPainter*, const QStyleOptionGraphicsItem*, QWidget *) override {}
};

Then:

class HitCache {
  QGraphicsScene scene;
  std::vector<RectItem> items;
public:
  int addRect(const QRectF &rect) {
    items.emplace_back(rect);
    return items.size()-1;
  }
  int itemAt(const QPointF &p) const {
    auto *item = scene.itemAt(p, {});
    if (item)
      return item - &items[0];
    return -1;
  }
  QRectF operator[](int i) const {
    return items[i].boundingRect();
  }
  RectItem &get(int i) {
    return items[i];
  }
};