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 |
236 | |