Flutter Engine
rtree_unittests.cc
Go to the documentation of this file.
1 // Copyright 2013 The Flutter Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "rtree.h"
6 
7 #include "flutter/testing/testing.h"
8 #include "third_party/skia/include/core/SkCanvas.h"
9 #include "third_party/skia/include/core/SkPictureRecorder.h"
10 
11 namespace flutter {
12 namespace testing {
13 
14 TEST(RTree, searchNonOverlappingDrawnRectsNoIntersection) {
15  auto rtree_factory = RTreeFactory();
16  auto recorder = std::make_unique<SkPictureRecorder>();
17  auto recording_canvas =
18  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
19 
20  auto rect_paint = SkPaint();
21  rect_paint.setColor(SkColors::kCyan);
22  rect_paint.setStyle(SkPaint::Style::kFill_Style);
23 
24  // If no rect is intersected with the query rect, then the result list is
25  // empty.
26  recording_canvas->drawRect(SkRect::MakeLTRB(20, 20, 40, 40), rect_paint);
27  recorder->finishRecordingAsPicture();
28 
29  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
30  SkRect::MakeLTRB(40, 40, 80, 80));
31  ASSERT_TRUE(hits.empty());
32 }
33 
34 TEST(RTree, searchNonOverlappingDrawnRectsSingleRectIntersection) {
35  auto rtree_factory = RTreeFactory();
36  auto recorder = std::make_unique<SkPictureRecorder>();
37  auto recording_canvas =
38  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
39 
40  auto rect_paint = SkPaint();
41  rect_paint.setColor(SkColors::kCyan);
42  rect_paint.setStyle(SkPaint::Style::kFill_Style);
43 
44  // Given a single rect A that intersects with the query rect,
45  // the result list contains this rect.
46  recording_canvas->drawRect(SkRect::MakeLTRB(120, 120, 160, 160), rect_paint);
47 
48  recorder->finishRecordingAsPicture();
49 
50  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
51  SkRect::MakeLTRB(140, 140, 150, 150));
52  ASSERT_EQ(1UL, hits.size());
53  ASSERT_EQ(*hits.begin(), SkRect::MakeLTRB(120, 120, 160, 160));
54 }
55 
56 TEST(RTree, searchNonOverlappingDrawnRectsIgnoresNonDrawingRecords) {
57  auto rtree_factory = RTreeFactory();
58  auto recorder = std::make_unique<SkPictureRecorder>();
59  auto recording_canvas =
60  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
61 
62  auto rect_paint = SkPaint();
63  rect_paint.setColor(SkColors::kCyan);
64  rect_paint.setStyle(SkPaint::Style::kFill_Style);
65 
66  // Creates two non drawing records.
67  recording_canvas->translate(100, 100);
68  // The result list should only contain the clipping rect.
69  recording_canvas->clipRect(SkRect::MakeLTRB(40, 40, 50, 50),
70  SkClipOp::kIntersect);
71  recording_canvas->drawRect(SkRect::MakeLTRB(20, 20, 80, 80), rect_paint);
72 
73  recorder->finishRecordingAsPicture();
74 
75  // The rtree has a translate, a clip and a rect record.
76  ASSERT_EQ(3, rtree_factory.getInstance()->getCount());
77 
78  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
79  SkRect::MakeLTRB(0, 0, 1000, 1000));
80  ASSERT_EQ(1UL, hits.size());
81  ASSERT_EQ(*hits.begin(), SkRect::MakeLTRB(120, 120, 180, 180));
82 }
83 
84 TEST(RTree, searchNonOverlappingDrawnRectsMultipleRectIntersection) {
85  auto rtree_factory = RTreeFactory();
86  auto recorder = std::make_unique<SkPictureRecorder>();
87  auto recording_canvas =
88  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
89 
90  auto rect_paint = SkPaint();
91  rect_paint.setColor(SkColors::kCyan);
92  rect_paint.setStyle(SkPaint::Style::kFill_Style);
93 
94  // Given the A, B that intersect with the query rect,
95  // there should be A and B in the result list since
96  // they don't intersect with each other.
97  //
98  // +-----+ +-----+
99  // | A | | B |
100  // +-----+ +-----+
101  // A
102  recording_canvas->drawRect(SkRect::MakeLTRB(100, 100, 200, 200), rect_paint);
103  // B
104  recording_canvas->drawRect(SkRect::MakeLTRB(300, 100, 400, 200), rect_paint);
105 
106  recorder->finishRecordingAsPicture();
107 
108  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
109  SkRect::MakeLTRB(0, 0, 1000, 1050));
110  ASSERT_EQ(2UL, hits.size());
111  ASSERT_EQ(*hits.begin(), SkRect::MakeLTRB(100, 100, 200, 200));
112  ASSERT_EQ(*std::next(hits.begin(), 1), SkRect::MakeLTRB(300, 100, 400, 200));
113 }
114 
115 TEST(RTree, searchNonOverlappingDrawnRectsJoinRectsWhenIntersectedCase1) {
116  auto rtree_factory = RTreeFactory();
117  auto recorder = std::make_unique<SkPictureRecorder>();
118  auto recording_canvas =
119  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
120 
121  auto rect_paint = SkPaint();
122  rect_paint.setColor(SkColors::kCyan);
123  rect_paint.setStyle(SkPaint::Style::kFill_Style);
124 
125  // Given the A, and B rects, which intersect with the query rect,
126  // the result list contains the rect resulting from the union of A and B.
127  //
128  // +-----+
129  // | A |
130  // | +-----+
131  // | | C |
132  // | +-----+
133  // | |
134  // +-----+
135 
136  // A
137  recording_canvas->drawRect(SkRect::MakeLTRB(100, 100, 150, 150), rect_paint);
138  // B
139  recording_canvas->drawRect(SkRect::MakeLTRB(125, 125, 175, 175), rect_paint);
140 
141  recorder->finishRecordingAsPicture();
142 
143  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
144  SkRect::MakeXYWH(120, 120, 126, 126));
145  ASSERT_EQ(1UL, hits.size());
146  ASSERT_EQ(*hits.begin(), SkRect::MakeLTRB(100, 100, 175, 175));
147 }
148 
149 TEST(RTree, searchNonOverlappingDrawnRectsJoinRectsWhenIntersectedCase2) {
150  auto rtree_factory = RTreeFactory();
151  auto recorder = std::make_unique<SkPictureRecorder>();
152  auto recording_canvas =
153  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
154 
155  auto rect_paint = SkPaint();
156  rect_paint.setColor(SkColors::kCyan);
157  rect_paint.setStyle(SkPaint::Style::kFill_Style);
158 
159  // Given the A, B, and C rects that intersect with the query rect,
160  // there should be only C in the result list,
161  // since A and B are contained in C.
162  //
163  // +---------------------+
164  // | C |
165  // | +-----+ +-----+ |
166  // | | A | | B | |
167  // | +-----+ +-----+ |
168  // +---------------------+
169  // +-----+
170  // | D |
171  // +-----+
172 
173  // A
174  recording_canvas->drawRect(SkRect::MakeLTRB(100, 100, 200, 200), rect_paint);
175  // B
176  recording_canvas->drawRect(SkRect::MakeLTRB(300, 100, 400, 200), rect_paint);
177  // C
178  recording_canvas->drawRect(SkRect::MakeLTRB(50, 50, 500, 250), rect_paint);
179  // D
180  recording_canvas->drawRect(SkRect::MakeLTRB(280, 100, 280, 320), rect_paint);
181 
182  recorder->finishRecordingAsPicture();
183 
184  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
185  SkRect::MakeLTRB(30, 30, 550, 270));
186  ASSERT_EQ(1UL, hits.size());
187  ASSERT_EQ(*hits.begin(), SkRect::MakeLTRB(50, 50, 500, 250));
188 }
189 
190 TEST(RTree, searchNonOverlappingDrawnRectsJoinRectsWhenIntersectedCase3) {
191  auto rtree_factory = RTreeFactory();
192  auto recorder = std::make_unique<SkPictureRecorder>();
193  auto recording_canvas =
194  recorder->beginRecording(SkRect::MakeIWH(1000, 1000), &rtree_factory);
195 
196  auto rect_paint = SkPaint();
197  rect_paint.setColor(SkColors::kCyan);
198  rect_paint.setStyle(SkPaint::Style::kFill_Style);
199 
200  // Given the A, B, C and D rects that intersect with the query rect,
201  // the result list contains a single rect, which is the union of
202  // these four rects.
203  //
204  // +------------------------------+
205  // | D |
206  // | +-----+ +-----+ +-----+ |
207  // | | A | | B | | C | |
208  // | +-----+ +-----+ | | |
209  // +----------------------| |-+
210  // +-----+
211  // +-----+
212  // | E |
213  // +-----+
214 
215  // A
216  recording_canvas->drawRect(SkRect::MakeLTRB(100, 100, 200, 200), rect_paint);
217  // B
218  recording_canvas->drawRect(SkRect::MakeLTRB(300, 100, 400, 200), rect_paint);
219  // C
220  recording_canvas->drawRect(SkRect::MakeLTRB(500, 100, 600, 300), rect_paint);
221  // D
222  recording_canvas->drawRect(SkRect::MakeLTRB(50, 50, 620, 250), rect_paint);
223  // E
224  recording_canvas->drawRect(SkRect::MakeLTRB(280, 100, 280, 320), rect_paint);
225 
226  recorder->finishRecordingAsPicture();
227 
228  auto hits = rtree_factory.getInstance()->searchNonOverlappingDrawnRects(
229  SkRect::MakeLTRB(30, 30, 550, 270));
230  ASSERT_EQ(1UL, hits.size());
231  ASSERT_EQ(*hits.begin(), SkRect::MakeLTRB(50, 50, 620, 300));
232 }
233 
234 } // namespace testing
235 } // namespace flutter
TEST(EmbeddedViewParams, GetBoundingRectAfterMutationsWithNoMutations)