1/*
2 * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
6 * are met:
7 *
8 * 1. Redistributions of source code must retain the above
9 * copyright notice, this list of conditions and the following
10 * disclaimer.
11 * 2. Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following
13 * disclaimer in the documentation and/or other materials
14 * provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
19 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
20 * COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
21 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
23 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
25 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
26 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
27 * OF THE POSSIBILITY OF SUCH DAMAGE.
28 */
29
30#include "config.h"
31#include "ExclusionPolygon.h"
32
33#include <wtf/MathExtras.h>
34
35namespace WebCore {
36
37enum EdgeIntersectionType {
38 Normal = 0,
39 VertexYMin = 1,
40 VertexYMax = 2,
41 VertexYBoth = 3
42};
43
44struct EdgeIntersection {
45 const ExclusionPolygonEdge* edge;
46 float x;
47 float y;
48 EdgeIntersectionType type;
49};
50
51struct EdgeMinYComparator {
52 bool operator() (const ExclusionPolygonEdge* e1, const ExclusionPolygonEdge* e2) const
53 {
54 return e1->minY() < e2->minY();
55 }
56
57 bool operator() (const ExclusionPolygonEdge* e, float y) const
58 {
59 return e->minY() < y;
60 }
61};
62struct IntersectionXComparator {
63 bool operator() (const EdgeIntersection& i1, const EdgeIntersection& i2) const
64 {
65 return (i1.x == i2.x) ? i1.type < i2.type : i1.x < i2.x;
66 }
67};
68
69ExclusionPolygonEdgeTree::ExclusionPolygonEdgeTree(const Vector<ExclusionPolygonEdge*>& sortedEdges)
70 : center(0)
71{
72 if (sortedEdges.size() > 0)
73 initEdgeTree(this, sortedEdges);
74}
75
76void ExclusionPolygonEdgeTree::initEdgeTree(ExclusionPolygonEdgeTree* node, const Vector<ExclusionPolygonEdge*>& edges)
77{
78 size_t edgesSize = edges.size();
79 size_t centerIndex = edgesSize / 2;
80 node->center = (edges[centerIndex]->minY() + edges[centerIndex]->maxY()) / 2;
81
82 Vector<ExclusionPolygonEdge*> aboveCenterEdges;
83 Vector<ExclusionPolygonEdge*> belowCenterEdges;
84
85 // FIXME: minSubtreeSize - don't bother creating subtrees for less than N edges, https://bugs.webkit.org/show_bug.cgi?id=97795
86
87 for (size_t i = 0; i < edgesSize; i++) {
88 ExclusionPolygonEdge* edge = edges[i];
89 if (edge->maxY() < node->center)
90 aboveCenterEdges.append(edge);
91 else if (edge->minY() > node->center)
92 belowCenterEdges.append(edge);
93 else
94 node->overlapCenter.append(edge);
95 }
96
97 // FIXME: create two sorted copies of overlapCenter: overlapCenterMinY, overlapCenterMaxY, https://bugs.webkit.org/show_bug.cgi?id=97797
98
99 if (aboveCenterEdges.size() > 0)
100 node->aboveCenter = adoptPtr(new ExclusionPolygonEdgeTree(aboveCenterEdges));
101 if (belowCenterEdges.size() > 0)
102 node->belowCenter = adoptPtr(new ExclusionPolygonEdgeTree(belowCenterEdges));
103}
104
105void ExclusionPolygonEdgeTree::findEdgesThatOverlapY(float y, Vector<ExclusionPolygonEdge*>& result) const
106{
107 if (y < center) {
108 if (aboveCenter)
109 aboveCenter->findEdgesThatOverlapY(y, result);
110 } else if (y > center) {
111 if (belowCenter)
112 belowCenter->findEdgesThatOverlapY(y, result);
113 }
114
115 size_t overlapEdgesSize = overlapCenter.size();
116 for (size_t i = 0; i < overlapEdgesSize; i++) {
117 ExclusionPolygonEdge* edge = overlapCenter[i];
118 if (y >= edge->minY() && y <= edge->maxY())
119 result.append(edge);
120 }
121}
122
123void ExclusionPolygonEdgeTree::findEdgesThatOverlapInterval(float y1, float y2, Vector<ExclusionPolygonEdge*>& result) const
124{
125 if ((y1 < center) && aboveCenter)
126 aboveCenter->findEdgesThatOverlapInterval(y1, y2, result);
127
128 if ((y2 > center) && belowCenter)
129 belowCenter->findEdgesThatOverlapInterval(y1, y2, result);
130
131 size_t overlapEdgesSize = overlapCenter.size();
132 for (size_t i = 0; i < overlapEdgesSize; i++) {
133 ExclusionPolygonEdge* edge = overlapCenter[i];
134 if (y2 > edge->minY() && y1 < edge->maxY())
135 result.append(edge);
136 }
137}
138
139ExclusionPolygon::ExclusionPolygon(PassOwnPtr<Vector<float> > coordinates, WindRule fillRule)
140 : ExclusionShape()
141 , m_coordinates(coordinates)
142 , m_fillRule(fillRule)
143{
144 // FIXME: handle special cases: less than 3 non-colinear vertices
145 // FIXME: assuming open polygons for now
146
147 size_t nVertices = numberOfVertices();
148 m_edges.resize(nVertices);
149 Vector<ExclusionPolygonEdge*> sortedEdgesMinY(nVertices);
150
151 float minX = getXAt(0);
152 float minY = getYAt(0);
153 float maxX = minX;
154 float maxY = minY;
155
156 for (size_t i = 0; i < nVertices; i++) {
157 float x = getXAt(i);
158 float y = getYAt(i);
159
160 minX = std::min(x, minX);
161 maxX = std::max(x, maxX);
162 minY = std::min(y, minY);
163 maxY = std::max(y, maxY);
164
165 m_edges[i].polygon = this;
166 m_edges[i].i1 = i;
167 m_edges[i].i2 = (i+1) % nVertices;
168
169 sortedEdgesMinY[i] = &m_edges[i];
170 }
171
172 m_boundingBox.setX(minX);
173 m_boundingBox.setY(minY);
174 m_boundingBox.setWidth(maxX - minX);
175 m_boundingBox.setHeight(maxY - minY);
176
177 std::sort(sortedEdgesMinY.begin(), sortedEdgesMinY.end(), EdgeMinYComparator());
178 m_edgeTree = adoptPtr(new ExclusionPolygonEdgeTree(sortedEdgesMinY));
179}
180
181static bool computeXIntersection(const ExclusionPolygonEdge* ep, float y, EdgeIntersection& result)
182{
183 const ExclusionPolygonEdge& e = *ep;
184
185 if (e.minY() > y || e.maxY() < y)
186 return false;
187
188 float x1 = e.x1();
189 float y1 = e.y1();
190 float x2 = e.x2();
191 float y2 = e.y2();
192 float dy = y2 - y1;
193
194 result.edge = ep;
195 result.y = y;
196
197 if (!dy) {
198 result.type = VertexYBoth;
199 result.x = e.minX();
200 } else if (y == e.minY()) {
201 result.type = VertexYMin;
202 result.x = (y1 < y2) ? x1 : x2;
203 } else if (y == e.maxY()) {
204 result.type = VertexYMax;
205 result.x = (y1 > y2) ? x1 : x2;
206 } else {
207 result.type = Normal;
208 result.x = ((y - y1) * (x2 - x1) / dy) + x1;
209 }
210
211 return true;
212}
213
214float ExclusionPolygon::rightVertexY(size_t index) const
215{
216 size_t nVertices = numberOfVertices();
217 size_t i1 = (index + 1) % nVertices;
218 size_t i2 = (index - 1) % nVertices;
219
220 if (getXAt(i1) == getXAt(i2))
221 return getYAt(i1) > getYAt(i2) ? getYAt(i1) : getYAt(i2);
222
223 return getXAt(i1) > getXAt(i2) ? getYAt(i1) : getYAt(i2);
224}
225
226static bool appendIntervalX(float x, bool inside, Vector<ExclusionInterval>& result)
227{
228 if (!inside)
229 result.append(ExclusionInterval(x));
230 else
231 result[result.size() - 1].x2 = x;
232
233 return !inside;
234}
235
236void ExclusionPolygon::computeXIntersections(float y, Vector<ExclusionInterval>& result) const
237{
238 Vector<ExclusionPolygonEdge*> overlappingEdges;
239 m_edgeTree->findEdgesThatOverlapY(y, overlappingEdges);
240
241 Vector<EdgeIntersection> intersections;
242 EdgeIntersection intersection;
243 for (size_t i = 0; i < overlappingEdges.size(); i++) {
244 if (computeXIntersection(overlappingEdges[i], y, intersection))
245 intersections.append(intersection);
246 }
247 if (intersections.size() < 2)
248 return;
249
250 std::sort(intersections.begin(), intersections.end(), IntersectionXComparator());
251
252 size_t index = 0;
253 int windCount = 0;
254 bool inside = false;
255
256 while (index < intersections.size()) {
257 const EdgeIntersection& thisIntersection = intersections[index];
258
259 if (index + 1 < intersections.size()) {
260 const EdgeIntersection& nextIntersection = intersections[index +1];
261 if ((thisIntersection.x == nextIntersection.x) && (thisIntersection.type == VertexYMin || thisIntersection.type == VertexYMax)) {
262 if (thisIntersection.type == nextIntersection.type) {
263 // skip VertexYMax,VertexYMax and VertexYMin,VertexYMin
264 index += 2;
265 } else {
266 // VertexYMin,VertexYMax or VertexYMax,VertexYMin => VertexYMin
267 if (nextIntersection.type == VertexYMax)
268 intersections[index + 1] = thisIntersection;
269 index += 1;
270 }
271 continue;
272 }
273 }
274
275 const ExclusionPolygonEdge& thisEdge = *thisIntersection.edge;
276 bool crossing = !windCount;
277
278 if (fillRule() == RULE_EVENODD) {
279 windCount += (getYAt(thisEdge.i2) > getYAt(thisEdge.i1)) ? +1 : -1;
280 crossing = crossing || !windCount;
281 }
282
283 if ((thisIntersection.type == Normal) || (thisIntersection.type == VertexYMin)) {
284 if (crossing)
285 inside = appendIntervalX(thisIntersection.x, inside, result);
286 } else if (thisIntersection.type == VertexYMax) {
287 int vertexIndex = (getYAt(thisEdge.i2) > getYAt(thisEdge.i1)) ? thisEdge.i2 : thisEdge.i1;
288 if (crossing && rightVertexY(vertexIndex) > y)
289 inside = appendIntervalX(thisEdge.maxX(), inside, result);
290 } else if (thisIntersection.type == VertexYBoth)
291 result.append(ExclusionInterval(thisEdge.minX(), thisEdge.maxX()));
292
293 index += 1;
294 }
295}
296
297// Return the X projections of the edges that overlap y1,y2.
298void ExclusionPolygon::computeEdgeIntersections(float y1, float y2, Vector<ExclusionInterval>& result) const
299{
300 Vector<ExclusionPolygonEdge *> overlappingEdges;
301 m_edgeTree->findEdgesThatOverlapInterval(y1, y2, overlappingEdges);
302
303 EdgeIntersection intersection;
304 for (size_t i = 0; i < overlappingEdges.size(); i++) {
305 const ExclusionPolygonEdge& edge = *overlappingEdges[i];
306 float x1, x2;
307
308 if (edge.minY() < y1) {
309 computeXIntersection(overlappingEdges[i], y1, intersection);
310 x1 = intersection.x;
311 } else
312 x1 = (edge.y1() < edge.y2()) ? edge.x1() : edge.x2();
313
314 if (edge.maxY() > y2) {
315 computeXIntersection(overlappingEdges[i], y2, intersection);
316 x2 = intersection.x;
317 } else
318 x2 = (edge.y1() > edge.y2()) ? edge.x1() : edge.x2();
319
320 if (x1 > x2)
321 std::swap(x1, x2);
322
323 result.append(ExclusionInterval(x1, x2));
324 }
325
326 sortExclusionIntervals(result);
327}
328
329void ExclusionPolygon::getExcludedIntervals(float logicalTop, float logicalBottom, SegmentList& result) const
330{
331 float y1 = minYForLogicalLine(logicalTop, logicalBottom);
332 float y2 = maxYForLogicalLine(logicalTop, logicalBottom);
333
334 Vector<ExclusionInterval> y1XIntervals, y2XIntervals;
335 computeXIntersections(y1, y1XIntervals);
336 computeXIntersections(y2, y2XIntervals);
337
338 Vector<ExclusionInterval> mergedIntervals;
339 mergeExclusionIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
340
341 Vector<ExclusionInterval> edgeIntervals;
342 computeEdgeIntersections(y1, y2, edgeIntervals);
343
344 Vector<ExclusionInterval> excludedIntervals;
345 mergeExclusionIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
346
347 for (size_t i = 0; i < excludedIntervals.size(); i++) {
348 ExclusionInterval interval = excludedIntervals[i];
349 result.append(LineSegment(interval.x1, interval.x2));
350 }
351}
352
353void ExclusionPolygon::getIncludedIntervals(float logicalTop, float logicalBottom, SegmentList& result) const
354{
355 float y1 = minYForLogicalLine(logicalTop, logicalBottom);
356 float y2 = maxYForLogicalLine(logicalTop, logicalBottom);
357
358 Vector<ExclusionInterval> y1XIntervals, y2XIntervals;
359 computeXIntersections(y1, y1XIntervals);
360 computeXIntersections(y2, y2XIntervals);
361
362 Vector<ExclusionInterval> commonIntervals;
363 intersectExclusionIntervals(y1XIntervals, y2XIntervals, commonIntervals);
364
365 Vector<ExclusionInterval> edgeIntervals;
366 computeEdgeIntersections(y1, y2, edgeIntervals);
367
368 Vector<ExclusionInterval> includedIntervals;
369 subtractExclusionIntervals(commonIntervals, edgeIntervals, includedIntervals);
370
371 for (size_t i = 0; i < includedIntervals.size(); i++) {
372 ExclusionInterval interval = includedIntervals[i];
373 result.append(LineSegment(interval.x1, interval.x2));
374 }
375}
376
377} // namespace WebCore