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
11namespace flutter {
12namespace testing {
13
14TEST(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
34TEST(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
56TEST(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
84TEST(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
115TEST(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
149TEST(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
190TEST(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
236