Flutter Engine
flutter::RTree Class Reference

#include <rtree.h>

Inheritance diagram for flutter::RTree:

Public Member Functions

 RTree ()
 
void insert (const SkRect[], const SkBBoxHierarchy::Metadata[], int N) override
 
void insert (const SkRect[], int N) override
 
void search (const SkRect &query, std::vector< int > *results) const override
 
size_t bytesUsed () const override
 
std::list< SkRect > searchNonOverlappingDrawnRects (const SkRect &query) const
 
int getCount () const
 

Detailed Description

An R-Tree implementation that forwards calls to an SkRTree.

This implementation provides a searchNonOverlappingDrawnRects method, which can be used to query the rects for the operations recorded in the tree.

Definition at line 21 of file rtree.h.

Constructor & Destructor Documentation

◆ RTree()

flutter::RTree::RTree ( )

Definition at line 14 of file rtree.cc.

14 : bbh_{SkRTreeFactory{}()}, all_ops_count_(0) {}

Member Function Documentation

◆ bytesUsed()

size_t flutter::RTree::bytesUsed ( ) const
override

Definition at line 84 of file rtree.cc.

84  {
85  return bbh_->bytesUsed();
86 }

◆ getCount()

int flutter::RTree::getCount ( ) const
inline

Definition at line 41 of file rtree.h.

41 { return all_ops_count_; }

◆ insert() [1/2]

void flutter::RTree::insert ( const SkRect  boundsArray[],
const SkBBoxHierarchy::Metadata  metadata[],
int  N 
)
override

Definition at line 16 of file rtree.cc.

References FML_DCHECK.

Referenced by insert().

18  {
19  FML_DCHECK(0 == all_ops_count_);
20  bbh_->insert(boundsArray, metadata, N);
21  for (int i = 0; i < N; i++) {
22  if (metadata != nullptr && metadata[i].isDraw) {
23  draw_op_[i] = boundsArray[i];
24  }
25  }
26  all_ops_count_ = N;
27 }
#define FML_DCHECK(condition)
Definition: logging.h:86

◆ insert() [2/2]

void flutter::RTree::insert ( const SkRect  boundsArray[],
int  N 
)
override

Definition at line 29 of file rtree.cc.

References insert().

29  {
30  insert(boundsArray, nullptr, N);
31 }
void insert(const SkRect[], const SkBBoxHierarchy::Metadata[], int N) override
Definition: rtree.cc:16

◆ search()

void flutter::RTree::search ( const SkRect &  query,
std::vector< int > *  results 
) const
override

Definition at line 33 of file rtree.cc.

Referenced by searchNonOverlappingDrawnRects().

33  {
34  bbh_->search(query, results);
35 }

◆ searchNonOverlappingDrawnRects()

std::list< SkRect > flutter::RTree::searchNonOverlappingDrawnRects ( const SkRect &  query) const

Definition at line 37 of file rtree.cc.

References search().

38  {
39  // Get the indexes for the operations that intersect with the query rect.
40  std::vector<int> intermediary_results;
41  search(query, &intermediary_results);
42 
43  std::list<SkRect> final_results;
44  for (int index : intermediary_results) {
45  auto draw_op = draw_op_.find(index);
46  // Ignore records that don't draw anything.
47  if (draw_op == draw_op_.end()) {
48  continue;
49  }
50  auto current_record_rect = draw_op->second;
51  auto replaced_existing_rect = false;
52  // // If the current record rect intersects with any of the rects in the
53  // // result list, then join them, and update the rect in final_results.
54  std::list<SkRect>::iterator curr_rect_itr = final_results.begin();
55  std::list<SkRect>::iterator first_intersecting_rect_itr;
56  while (!replaced_existing_rect && curr_rect_itr != final_results.end()) {
57  if (SkRect::Intersects(*curr_rect_itr, current_record_rect)) {
58  replaced_existing_rect = true;
59  first_intersecting_rect_itr = curr_rect_itr;
60  curr_rect_itr->join(current_record_rect);
61  }
62  curr_rect_itr++;
63  }
64  // It's possible that the result contains duplicated rects at this point.
65  // For example, consider a result list that contains rects A, B. If a
66  // new rect C is a superset of A and B, then A and B are the same set after
67  // the merge. As a result, find such cases and remove them from the result
68  // list.
69  while (replaced_existing_rect && curr_rect_itr != final_results.end()) {
70  if (SkRect::Intersects(*curr_rect_itr, *first_intersecting_rect_itr)) {
71  first_intersecting_rect_itr->join(*curr_rect_itr);
72  curr_rect_itr = final_results.erase(curr_rect_itr);
73  } else {
74  curr_rect_itr++;
75  }
76  }
77  if (!replaced_existing_rect) {
78  final_results.push_back(current_record_rect);
79  }
80  }
81  return final_results;
82 }
void search(const SkRect &query, std::vector< int > *results) const override
Definition: rtree.cc:33

The documentation for this class was generated from the following files: