5#include "flutter/display_list/geometry/dl_rtree.h"
6#include "flutter/display_list/geometry/dl_region.h"
8#include "flutter/fml/logging.h"
17 : invalid_id_(invalid_id) {
28 for (
int i = 0;
i <
N;
i++) {
29 if (!rects[
i].isEmpty()) {
30 if (ids ==
nullptr ||
p(ids[
i])) {
41 while (gen_count > 1) {
42 uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
43 total_node_count += family_count;
44 gen_count = family_count;
47 nodes_.resize(total_node_count);
53 for (
int i = 0;
i <
N;
i++) {
54 if (!rects[
i].isEmpty()) {
55 if (ids ==
nullptr ||
p(
id = ids[
i])) {
56 Node& node = nodes_[leaf_index++];
57 node.bounds = rects[
i];
89 uint32_t gen_start = 0;
91 while (gen_count > 1) {
92 uint32_t gen_end = gen_start + gen_count;
94 uint32_t family_count = (gen_count + kMaxChildren - 1u) / kMaxChildren;
95 FML_DCHECK(gen_end + family_count <= total_node_count);
117 uint32_t sibling_index = gen_start;
118 uint32_t parent_index = gen_end;
119 Node* parent =
nullptr;
120 while (sibling_index < gen_end) {
121 if ((
D += family_count) > 0) {
123 FML_DCHECK(parent_index < gen_end + family_count);
124 parent = &nodes_[parent_index++];
125 parent->bounds.setEmpty();
126 parent->child.index = sibling_index;
127 parent->child.count = 0;
130 parent->bounds.join(nodes_[sibling_index++].
bounds);
131 parent->child.count++;
135 FML_DCHECK(parent_index == gen_end + family_count);
137 gen_count = family_count;
139 FML_DCHECK(gen_start + gen_count == total_node_count);
147 if (nodes_.size() <= 0) {
151 const Node&
root = nodes_.back();
152 if (
root.bounds.intersects(query)) {
153 if (nodes_.size() == 1) {
156 results->push_back(0);
166 std::vector<int> intermediary_results;
167 search(query, &intermediary_results);
169 std::vector<SkIRect> rects;
170 rects.reserve(intermediary_results.size());
171 for (
int index : intermediary_results) {
174 rects.push_back(current_record_rect);
179 std::list<SkRect> final_results;
180 for (
const auto&
rect : non_overlapping_rects) {
183 return final_results;
188 std::vector<int>* results)
const {
190 int start = parent.child.index;
191 int end =
start + parent.child.count;
192 for (
int i = start;
i <
end;
i++) {
193 const Node& node = nodes_[
i];
194 if (node.bounds.intersects(query)) {
195 if (
i < leaf_count_) {
196 results->push_back(
i);
198 search(node, query, results);
206 std::vector<SkIRect> rects;
207 rects.resize(leaf_count_);
208 for (
int i = 0;
i < leaf_count_;
i++) {
209 nodes_[
i].bounds.roundOut(&rects[
i]);
211 region_.emplace(rects);
217 if (!nodes_.empty()) {
218 return nodes_.back().bounds;
int id(int result_index) const
const SkRect & bounds() const
void search(const SkRect &query, std::vector< int > *results) const
DlRTree(const SkRect rects[], int N, const int ids[]=nullptr, bool predicate(int id)=[](int) { return true;}, int invalid_id=-1)
const DlRegion & region() const
std::list< SkRect > searchAndConsolidateRects(const SkRect &query, bool deband=true) const
std::vector< SkIRect > getRects(bool deband=true) const
#define FML_DCHECK(condition)
sk_sp< SkBlender > blender SkRect rect
static SkRect Make(const SkISize &size)
void roundOut(SkIRect *dst) const