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 "platform/geometry/FloatPolygon.h"
32
33#include "wtf/MathExtras.h"
34
35namespace blink {
36
37static inline float determinant(const FloatSize& a, const FloatSize& b)
38{
39    return a.width() * b.height() - a.height() * b.width();
40}
41
42static inline bool areCollinearPoints(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)
43{
44    return !determinant(p1 - p0, p2 - p0);
45}
46
47static inline bool areCoincidentPoints(const FloatPoint& p0, const FloatPoint& p1)
48{
49    return p0.x() == p1.x() && p0.y() == p1.y();
50}
51
52static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
53{
54    return point.x() >= std::min(vertex1.x(), vertex2.x())
55        && point.x() <= std::max(vertex1.x(), vertex2.x())
56        && areCollinearPoints(vertex1, vertex2, point);
57}
58
59static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise)
60{
61    return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;
62}
63
64static unsigned findNextEdgeVertexIndex(const FloatPolygon& polygon, unsigned vertexIndex1, bool clockwise)
65{
66    unsigned nVertices = polygon.numberOfVertices();
67    unsigned vertexIndex2 = nextVertexIndex(vertexIndex1, nVertices, clockwise);
68
69    while (vertexIndex2 && areCoincidentPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2)))
70        vertexIndex2 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
71
72    while (vertexIndex2) {
73        unsigned vertexIndex3 = nextVertexIndex(vertexIndex2, nVertices, clockwise);
74        if (!areCollinearPoints(polygon.vertexAt(vertexIndex1), polygon.vertexAt(vertexIndex2), polygon.vertexAt(vertexIndex3)))
75            break;
76        vertexIndex2 = vertexIndex3;
77    }
78
79    return vertexIndex2;
80}
81
82FloatPolygon::FloatPolygon(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fillRule)
83    : m_vertices(vertices)
84    , m_fillRule(fillRule)
85{
86    unsigned nVertices = numberOfVertices();
87    m_edges.resize(nVertices);
88    m_empty = nVertices < 3;
89
90    if (nVertices)
91        m_boundingBox.setLocation(vertexAt(0));
92
93    if (m_empty)
94        return;
95
96    unsigned minVertexIndex = 0;
97    for (unsigned i = 1; i < nVertices; ++i) {
98        const FloatPoint& vertex = vertexAt(i);
99        if (vertex.y() < vertexAt(minVertexIndex).y() || (vertex.y() == vertexAt(minVertexIndex).y() && vertex.x() < vertexAt(minVertexIndex).x()))
100            minVertexIndex = i;
101    }
102    FloatPoint nextVertex = vertexAt((minVertexIndex + 1) % nVertices);
103    FloatPoint prevVertex = vertexAt((minVertexIndex + nVertices - 1) % nVertices);
104    bool clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVertex - prevVertex) > 0;
105
106    unsigned edgeIndex = 0;
107    unsigned vertexIndex1 = 0;
108    do {
109        m_boundingBox.extend(vertexAt(vertexIndex1));
110        unsigned vertexIndex2 = findNextEdgeVertexIndex(*this, vertexIndex1, clockwise);
111        m_edges[edgeIndex].m_polygon = this;
112        m_edges[edgeIndex].m_vertexIndex1 = vertexIndex1;
113        m_edges[edgeIndex].m_vertexIndex2 = vertexIndex2;
114        m_edges[edgeIndex].m_edgeIndex = edgeIndex;
115        ++edgeIndex;
116        vertexIndex1 = vertexIndex2;
117    } while (vertexIndex1);
118
119    if (edgeIndex > 3) {
120        const FloatPolygonEdge& firstEdge = m_edges[0];
121        const FloatPolygonEdge& lastEdge = m_edges[edgeIndex - 1];
122        if (areCollinearPoints(lastEdge.vertex1(), lastEdge.vertex2(), firstEdge.vertex2())) {
123            m_edges[0].m_vertexIndex1 = lastEdge.m_vertexIndex1;
124            edgeIndex--;
125        }
126    }
127
128    m_edges.resize(edgeIndex);
129    m_empty = m_edges.size() < 3;
130
131    if (m_empty)
132        return;
133
134    for (unsigned i = 0; i < m_edges.size(); ++i) {
135        FloatPolygonEdge* edge = &m_edges[i];
136        m_edgeTree.add(EdgeInterval(edge->minY(), edge->maxY(), edge));
137    }
138}
139
140bool FloatPolygon::overlappingEdges(float minY, float maxY, Vector<const FloatPolygonEdge*>& result) const
141{
142    Vector<FloatPolygon::EdgeInterval> overlappingEdgeIntervals;
143    m_edgeTree.allOverlaps(FloatPolygon::EdgeInterval(minY, maxY, 0), overlappingEdgeIntervals);
144    unsigned overlappingEdgeIntervalsSize = overlappingEdgeIntervals.size();
145    result.resize(overlappingEdgeIntervalsSize);
146    for (unsigned i = 0; i < overlappingEdgeIntervalsSize; ++i) {
147        const FloatPolygonEdge* edge = static_cast<const FloatPolygonEdge*>(overlappingEdgeIntervals[i].data());
148        ASSERT(edge);
149        result[i] = edge;
150    }
151    return overlappingEdgeIntervalsSize > 0;
152}
153
154static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
155{
156    return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
157}
158
159bool FloatPolygon::containsEvenOdd(const FloatPoint& point) const
160{
161    unsigned crossingCount = 0;
162    for (unsigned i = 0; i < numberOfEdges(); ++i) {
163        const FloatPoint& vertex1 = edgeAt(i).vertex1();
164        const FloatPoint& vertex2 = edgeAt(i).vertex2();
165        if (isPointOnLineSegment(vertex1, vertex2, point))
166            return true;
167        if ((vertex1.y() <= point.y() && vertex2.y() > point.y()) || (vertex1.y() > point.y() && vertex2.y() <= point.y())) {
168            float vt = (point.y()  - vertex1.y()) / (vertex2.y() - vertex1.y());
169            if (point.x() < vertex1.x() + vt * (vertex2.x() - vertex1.x()))
170                ++crossingCount;
171        }
172    }
173    return crossingCount & 1;
174}
175
176bool FloatPolygon::containsNonZero(const FloatPoint& point) const
177{
178    int windingNumber = 0;
179    for (unsigned i = 0; i < numberOfEdges(); ++i) {
180        const FloatPoint& vertex1 = edgeAt(i).vertex1();
181        const FloatPoint& vertex2 = edgeAt(i).vertex2();
182        if (isPointOnLineSegment(vertex1, vertex2, point))
183            return true;
184        if (vertex2.y() <= point.y()) {
185            if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0))
186                ++windingNumber;
187        } else if (vertex2.y() >= point.y()) {
188            if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0))
189                --windingNumber;
190        }
191    }
192    return windingNumber;
193}
194
195bool FloatPolygon::contains(const FloatPoint& point) const
196{
197    if (!m_boundingBox.contains(point))
198        return false;
199    return (fillRule() == RULE_NONZERO) ? containsNonZero(point) : containsEvenOdd(point);
200}
201
202bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
203{
204    // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions"
205
206    const FloatSize& thisDelta = vertex2() - vertex1();
207    const FloatSize& otherDelta = other.vertex2() - other.vertex1();
208    float denominator = determinant(thisDelta, otherDelta);
209    if (!denominator)
210        return false;
211
212    // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined
213    // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1),
214    // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point.
215
216    const FloatSize& vertex1Delta = vertex1() - other.vertex1();
217    float uThisLine = determinant(otherDelta, vertex1Delta) / denominator;
218    float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator;
219
220    if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1)
221        return false;
222
223    point = vertex1() + uThisLine * thisDelta;
224    return true;
225}
226
227} // namespace blink
228