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 "PolygonShape.h"
32
33#include <wtf/MathExtras.h>
34
35namespace WebCore {
36
37enum EdgeIntersectionType {
38    Normal,
39    VertexMinY,
40    VertexMaxY,
41    VertexYBoth
42};
43
44struct EdgeIntersection {
45    const FloatPolygonEdge* edge;
46    FloatPoint point;
47    EdgeIntersectionType type;
48};
49
50static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
51{
52    return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
53}
54
55static inline bool isReflexVertex(const FloatPoint& prevVertex, const FloatPoint& vertex, const FloatPoint& nextVertex)
56{
57    return leftSide(prevVertex, nextVertex, vertex) < 0;
58}
59
60static bool computeXIntersection(const FloatPolygonEdge* edgePointer, float y, EdgeIntersection& result)
61{
62    const FloatPolygonEdge& edge = *edgePointer;
63
64    if (edge.minY() > y || edge.maxY() < y)
65        return false;
66
67    const FloatPoint& vertex1 = edge.vertex1();
68    const FloatPoint& vertex2 = edge.vertex2();
69    float dy = vertex2.y() - vertex1.y();
70
71    float intersectionX;
72    EdgeIntersectionType intersectionType;
73
74    if (!dy) {
75        intersectionType = VertexYBoth;
76        intersectionX = edge.minX();
77    } else if (y == edge.minY()) {
78        intersectionType = VertexMinY;
79        intersectionX = (vertex1.y() < vertex2.y()) ? vertex1.x() : vertex2.x();
80    } else if (y == edge.maxY()) {
81        intersectionType = VertexMaxY;
82        intersectionX = (vertex1.y() > vertex2.y()) ? vertex1.x() : vertex2.x();
83    } else {
84        intersectionType = Normal;
85        intersectionX = ((y - vertex1.y()) * (vertex2.x() - vertex1.x()) / dy) + vertex1.x();
86    }
87
88    result.edge = edgePointer;
89    result.type = intersectionType;
90    result.point.set(intersectionX, y);
91
92    return true;
93}
94
95static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge)
96{
97    FloatSize edgeDelta = edge.vertex2() - edge.vertex1();
98    if (!edgeDelta.width())
99        return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0);
100    if (!edgeDelta.height())
101        return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1));
102    float edgeLength = edgeDelta.diagonalLength();
103    return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength);
104}
105
106static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge)
107{
108    return -inwardEdgeNormal(edge);
109}
110
111static inline void appendArc(Vector<FloatPoint>& vertices, const FloatPoint& arcCenter, float arcRadius, const FloatPoint& startArcVertex, const FloatPoint& endArcVertex, bool padding)
112{
113    float startAngle = atan2(startArcVertex.y() - arcCenter.y(), startArcVertex.x() - arcCenter.x());
114    float endAngle = atan2(endArcVertex.y() - arcCenter.y(), endArcVertex.x() - arcCenter.x());
115    const float twoPI = piFloat * 2;
116    if (startAngle < 0)
117        startAngle += twoPI;
118    if (endAngle < 0)
119        endAngle += twoPI;
120    float angle = (startAngle > endAngle) ? (startAngle - endAngle) : (startAngle + twoPI - endAngle);
121    const float arcSegmentCount = 6; // An even number so that one arc vertex will be eactly arcRadius from arcCenter.
122    float arcSegmentAngle =  ((padding) ? -angle : twoPI - angle) / arcSegmentCount;
123
124    vertices.append(startArcVertex);
125    for (unsigned i = 1; i < arcSegmentCount; ++i) {
126        float angle = startAngle + arcSegmentAngle * i;
127        vertices.append(arcCenter + FloatPoint(cos(angle) * arcRadius, sin(angle) * arcRadius));
128    }
129    vertices.append(endArcVertex);
130}
131
132static inline void snapVerticesToLayoutUnitGrid(Vector<FloatPoint>& vertices)
133{
134    for (unsigned i = 0; i < vertices.size(); ++i)
135        vertices[i].set(LayoutUnit(vertices[i].x()).toFloat(), LayoutUnit(vertices[i].y()).toFloat());
136}
137
138static inline PassOwnPtr<FloatPolygon> computeShapePaddingBounds(const FloatPolygon& polygon, float padding, WindRule fillRule)
139{
140    OwnPtr<Vector<FloatPoint> > paddedVertices = adoptPtr(new Vector<FloatPoint>());
141    FloatPoint intersection;
142
143    for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
144        const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
145        const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
146        OffsetPolygonEdge thisOffsetEdge(thisEdge, inwardEdgeNormal(thisEdge) * padding);
147        OffsetPolygonEdge prevOffsetEdge(prevEdge, inwardEdgeNormal(prevEdge) * padding);
148
149        if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
150            paddedVertices->append(intersection);
151        else if (isReflexVertex(prevEdge.vertex1(), thisEdge.vertex1(), thisEdge.vertex2()))
152            appendArc(*paddedVertices, thisEdge.vertex1(), padding, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), true);
153    }
154
155    snapVerticesToLayoutUnitGrid(*paddedVertices);
156    return adoptPtr(new FloatPolygon(paddedVertices.release(), fillRule));
157}
158
159static inline PassOwnPtr<FloatPolygon> computeShapeMarginBounds(const FloatPolygon& polygon, float margin, WindRule fillRule)
160{
161    OwnPtr<Vector<FloatPoint> > marginVertices = adoptPtr(new Vector<FloatPoint>());
162    FloatPoint intersection;
163
164    for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
165        const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
166        const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
167        OffsetPolygonEdge thisOffsetEdge(thisEdge, outwardEdgeNormal(thisEdge) * margin);
168        OffsetPolygonEdge prevOffsetEdge(prevEdge, outwardEdgeNormal(prevEdge) * margin);
169
170        if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
171            marginVertices->append(intersection);
172        else
173            appendArc(*marginVertices, thisEdge.vertex1(), margin, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), false);
174    }
175
176    snapVerticesToLayoutUnitGrid(*marginVertices);
177    return adoptPtr(new FloatPolygon(marginVertices.release(), fillRule));
178}
179
180const FloatPolygon& PolygonShape::shapePaddingBounds() const
181{
182    ASSERT(shapePadding() >= 0);
183    if (!shapePadding())
184        return m_polygon;
185
186    if (!m_paddingBounds)
187        m_paddingBounds = computeShapePaddingBounds(m_polygon, shapePadding(), m_polygon.fillRule());
188
189    return *m_paddingBounds;
190}
191
192const FloatPolygon& PolygonShape::shapeMarginBounds() const
193{
194    ASSERT(shapeMargin() >= 0);
195    if (!shapeMargin())
196        return m_polygon;
197
198    if (!m_marginBounds)
199        m_marginBounds = computeShapeMarginBounds(m_polygon, shapeMargin(), m_polygon.fillRule());
200
201    return *m_marginBounds;
202}
203
204static inline bool getVertexIntersectionVertices(const EdgeIntersection& intersection, FloatPoint& prevVertex, FloatPoint& thisVertex, FloatPoint& nextVertex)
205{
206    if (intersection.type != VertexMinY && intersection.type != VertexMaxY)
207        return false;
208
209    ASSERT(intersection.edge && intersection.edge->polygon());
210    const FloatPolygon& polygon = *(intersection.edge->polygon());
211    const FloatPolygonEdge& thisEdge = *(intersection.edge);
212
213    if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y()))
214        || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) {
215        prevVertex = polygon.vertexAt(thisEdge.previousEdge().vertexIndex1());
216        thisVertex = polygon.vertexAt(thisEdge.vertexIndex1());
217        nextVertex = polygon.vertexAt(thisEdge.vertexIndex2());
218    } else {
219        prevVertex = polygon.vertexAt(thisEdge.vertexIndex1());
220        thisVertex = polygon.vertexAt(thisEdge.vertexIndex2());
221        nextVertex = polygon.vertexAt(thisEdge.nextEdge().vertexIndex2());
222    }
223
224    return true;
225}
226
227static inline bool appendIntervalX(float x, bool inside, Vector<ShapeInterval>& result)
228{
229    if (!inside)
230        result.append(ShapeInterval(x));
231    else
232        result[result.size() - 1].x2 = x;
233
234    return !inside;
235}
236
237static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, const EdgeIntersection& intersection2)
238{
239    float x1 = intersection1.point.x();
240    float x2 = intersection2.point.x();
241    return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2;
242}
243
244static void computeXIntersections(const FloatPolygon& polygon, float y, bool isMinY, Vector<ShapeInterval>& result)
245{
246    Vector<const FloatPolygonEdge*> edges;
247    if (!polygon.overlappingEdges(y, y, edges))
248        return;
249
250    Vector<EdgeIntersection> intersections;
251    EdgeIntersection intersection;
252    for (unsigned i = 0; i < edges.size(); ++i) {
253        if (computeXIntersection(edges[i], y, intersection) && intersection.type != VertexYBoth)
254            intersections.append(intersection);
255    }
256
257    if (intersections.size() < 2)
258        return;
259
260    std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX);
261
262    unsigned index = 0;
263    int windCount = 0;
264    bool inside = false;
265
266    while (index < intersections.size()) {
267        const EdgeIntersection& thisIntersection = intersections[index];
268        if (index + 1 < intersections.size()) {
269            const EdgeIntersection& nextIntersection = intersections[index + 1];
270            if ((thisIntersection.point.x() == nextIntersection.point.x()) && (thisIntersection.type == VertexMinY || thisIntersection.type == VertexMaxY)) {
271                if (thisIntersection.type == nextIntersection.type) {
272                    // Skip pairs of intersections whose types are VertexMaxY,VertexMaxY and VertexMinY,VertexMinY.
273                    index += 2;
274                } else {
275                    // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection.
276                    ++index;
277                }
278                continue;
279            }
280        }
281
282        const FloatPolygonEdge& thisEdge = *thisIntersection.edge;
283        bool evenOddCrossing = !windCount;
284
285        if (polygon.fillRule() == RULE_EVENODD) {
286            windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
287            evenOddCrossing = evenOddCrossing || !windCount;
288        }
289
290        if (evenOddCrossing) {
291            bool edgeCrossing = thisIntersection.type == Normal;
292            if (!edgeCrossing) {
293                FloatPoint prevVertex;
294                FloatPoint thisVertex;
295                FloatPoint nextVertex;
296
297                if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) {
298                    if (nextVertex.y() == y)
299                        edgeCrossing = (isMinY) ? prevVertex.y() > y : prevVertex.y() < y;
300                    else if (prevVertex.y() == y)
301                        edgeCrossing = (isMinY) ? nextVertex.y() > y : nextVertex.y() < y;
302                    else
303                        edgeCrossing = true;
304                }
305            }
306            if (edgeCrossing)
307                inside = appendIntervalX(thisIntersection.point.x(), inside, result);
308        }
309
310        ++index;
311    }
312}
313
314static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, Vector<ShapeInterval>& result)
315{
316    Vector<const FloatPolygonEdge*> edges;
317    if (!polygon.overlappingEdges(y1, y2, edges))
318        return;
319
320    EdgeIntersection intersection;
321    for (unsigned i = 0; i < edges.size(); ++i) {
322        const FloatPolygonEdge *edge = edges[i];
323        float x1;
324        float x2;
325
326        if (edge->minY() < y1) {
327            computeXIntersection(edge, y1, intersection);
328            x1 = intersection.point.x();
329        } else
330            x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
331
332        if (edge->maxY() > y2) {
333            computeXIntersection(edge, y2, intersection);
334            x2 = intersection.point.x();
335        } else
336            x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
337
338        if (x1 > x2)
339            std::swap(x1, x2);
340
341        if (x2 > x1)
342            result.append(ShapeInterval(x1, x2));
343    }
344
345    sortShapeIntervals(result);
346}
347
348void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
349{
350    const FloatPolygon& polygon = shapeMarginBounds();
351    if (polygon.isEmpty())
352        return;
353
354    float y1 = logicalTop;
355    float y2 = logicalTop + logicalHeight;
356
357    Vector<ShapeInterval> y1XIntervals, y2XIntervals;
358    computeXIntersections(polygon, y1, true, y1XIntervals);
359    computeXIntersections(polygon, y2, false, y2XIntervals);
360
361    Vector<ShapeInterval> mergedIntervals;
362    mergeShapeIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
363
364    Vector<ShapeInterval> edgeIntervals;
365    computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
366
367    Vector<ShapeInterval> excludedIntervals;
368    mergeShapeIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
369
370    for (unsigned i = 0; i < excludedIntervals.size(); ++i) {
371        ShapeInterval interval = excludedIntervals[i];
372        result.append(LineSegment(interval.x1, interval.x2));
373    }
374}
375
376void PolygonShape::getIncludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
377{
378    const FloatPolygon& polygon = shapePaddingBounds();
379    if (polygon.isEmpty())
380        return;
381
382    float y1 = logicalTop;
383    float y2 = logicalTop + logicalHeight;
384
385    Vector<ShapeInterval> y1XIntervals, y2XIntervals;
386    computeXIntersections(polygon, y1, true, y1XIntervals);
387    computeXIntersections(polygon, y2, false, y2XIntervals);
388
389    Vector<ShapeInterval> commonIntervals;
390    intersectShapeIntervals(y1XIntervals, y2XIntervals, commonIntervals);
391
392    Vector<ShapeInterval> edgeIntervals;
393    computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
394
395    Vector<ShapeInterval> includedIntervals;
396    subtractShapeIntervals(commonIntervals, edgeIntervals, includedIntervals);
397
398    for (unsigned i = 0; i < includedIntervals.size(); ++i) {
399        ShapeInterval interval = includedIntervals[i];
400        result.append(LineSegment(interval.x1, interval.x2));
401    }
402}
403
404static inline bool firstFitRectInPolygon(const FloatPolygon& polygon, const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2)
405{
406    Vector<const FloatPolygonEdge*> edges;
407    if (!polygon.overlappingEdges(rect.y(), rect.maxY(), edges))
408        return true;
409
410    for (unsigned i = 0; i < edges.size(); ++i) {
411        const FloatPolygonEdge* edge = edges[i];
412        if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect))
413            return false;
414    }
415
416    return true;
417}
418
419static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2)
420{
421    if (r1.y() < r2.y())
422        return true;
423    if (r1.y() == r2.y())
424        return r1.x() < r2.x();
425    return false;
426}
427
428bool PolygonShape::firstIncludedIntervalLogicalTop(LayoutUnit minLogicalIntervalTop, const LayoutSize& minLogicalIntervalSize, LayoutUnit& result) const
429{
430    float minIntervalTop = minLogicalIntervalTop;
431    float minIntervalHeight = minLogicalIntervalSize.height();
432    float minIntervalWidth = minLogicalIntervalSize.width();
433
434    const FloatPolygon& polygon = shapePaddingBounds();
435    const FloatRect boundingBox = polygon.boundingBox();
436    if (minIntervalWidth > boundingBox.width())
437        return false;
438
439    float minY = std::max(boundingBox.y(), minIntervalTop);
440    float maxY = minY + minIntervalHeight;
441
442    if (maxY > boundingBox.maxY())
443        return false;
444
445    Vector<const FloatPolygonEdge*> edges;
446    polygon.overlappingEdges(minIntervalTop, boundingBox.maxY(), edges);
447
448    float dx = minIntervalWidth / 2;
449    float dy = minIntervalHeight / 2;
450    Vector<OffsetPolygonEdge> offsetEdges;
451
452    for (unsigned i = 0; i < edges.size(); ++i) {
453        const FloatPolygonEdge& edge = *(edges[i]);
454        const FloatPoint& vertex0 = edge.previousEdge().vertex1();
455        const FloatPoint& vertex1 = edge.vertex1();
456        const FloatPoint& vertex2 = edge.vertex2();
457        Vector<OffsetPolygonEdge> offsetEdgeBuffer;
458
459        if (vertex2.y() > vertex1.y() ? vertex2.x() >= vertex1.x() : vertex1.x() >= vertex2.x()) {
460            offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, -dy)));
461            offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, dy)));
462        } else {
463            offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, dy)));
464            offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, -dy)));
465        }
466
467        if (isReflexVertex(vertex0, vertex1, vertex2)) {
468            if (vertex2.x() <= vertex1.x() && vertex0.x() <= vertex1.x())
469                offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(dx, -dy), FloatSize(dx, dy)));
470            else if (vertex2.x() >= vertex1.x() && vertex0.x() >= vertex1.x())
471                offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(-dx, dy)));
472            if (vertex2.y() <= vertex1.y() && vertex0.y() <= vertex1.y())
473                offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, dy), FloatSize(dx, dy)));
474            else if (vertex2.y() >= vertex1.y() && vertex0.y() >= vertex1.y())
475                offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(dx, -dy)));
476        }
477
478        for (unsigned j = 0; j < offsetEdgeBuffer.size(); ++j)
479            if (offsetEdgeBuffer[j].maxY() >= minY)
480                offsetEdges.append(offsetEdgeBuffer[j]);
481    }
482
483    offsetEdges.append(OffsetPolygonEdge(polygon, minIntervalTop, FloatSize(0, dy)));
484
485    FloatPoint offsetEdgesIntersection;
486    FloatRect firstFitRect;
487    bool firstFitFound = false;
488
489    for (unsigned i = 0; i < offsetEdges.size() - 1; ++i) {
490        for (unsigned j = i + 1; j < offsetEdges.size(); ++j) {
491            if (offsetEdges[i].intersection(offsetEdges[j], offsetEdgesIntersection)) {
492                FloatPoint potentialFirstFitLocation(offsetEdgesIntersection.x() - dx, offsetEdgesIntersection.y() - dy);
493                FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize);
494                if ((offsetEdges[i].basis() == OffsetPolygonEdge::LineTop
495                    || offsetEdges[j].basis() == OffsetPolygonEdge::LineTop
496                    || potentialFirstFitLocation.y() >= minIntervalTop)
497                    && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect))
498                    && polygon.contains(offsetEdgesIntersection)
499                    && firstFitRectInPolygon(polygon, potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
500                    firstFitFound = true;
501                    firstFitRect = potentialFirstFitRect;
502                }
503            }
504        }
505    }
506
507    if (firstFitFound)
508        result = ceiledLayoutUnit(firstFitRect.y());
509    return firstFitFound;
510}
511
512} // namespace WebCore
513