Move Source/WebCore/rendering/ code to std::unique_ptr
[WebKit-https.git] / Source / WebCore / platform / graphics / FloatPolygon.cpp
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 "FloatPolygon.h"
32
33 #include <wtf/MathExtras.h>
34
35 namespace WebCore {
36
37 static inline float determinant(const FloatSize& a, const FloatSize& b)
38 {
39     return a.width() * b.height() - a.height() * b.width();
40 }
41
42 static inline bool areCollinearPoints(const FloatPoint& p0, const FloatPoint& p1, const FloatPoint& p2)
43 {
44     return !determinant(p1 - p0, p2 - p0);
45 }
46
47 static inline bool areCoincidentPoints(const FloatPoint& p0, const FloatPoint& p1)
48 {
49     return p0.x() == p1.x() && p0.y() == p1.y();
50 }
51
52 static 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
59 static inline unsigned nextVertexIndex(unsigned vertexIndex, unsigned nVertices, bool clockwise)
60 {
61     return ((clockwise) ? vertexIndex + 1 : vertexIndex - 1 + nVertices) % nVertices;
62 }
63
64 static 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
82 FloatPolygon::FloatPolygon(std::unique_ptr<Vector<FloatPoint>> vertices, WindRule fillRule)
83     : m_vertices(std::move(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
140 bool 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
154 static 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
159 bool 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
176 bool 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
195 bool 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
202 bool VertexPair::overlapsRect(const FloatRect& rect) const
203 {
204     bool boundsOverlap = (minX() < rect.maxX()) && (maxX() > rect.x()) && (minY() < rect.maxY()) && (maxY() > rect.y());
205     if (!boundsOverlap)
206         return false;
207
208     float leftSideValues[4] = {
209         leftSide(vertex1(), vertex2(), rect.minXMinYCorner()),
210         leftSide(vertex1(), vertex2(), rect.maxXMinYCorner()),
211         leftSide(vertex1(), vertex2(), rect.minXMaxYCorner()),
212         leftSide(vertex1(), vertex2(), rect.maxXMaxYCorner())
213     };
214
215     int currentLeftSideSign = 0;
216     for (unsigned i = 0; i < 4; ++i) {
217         if (!leftSideValues[i])
218             continue;
219         int leftSideSign = leftSideValues[i] > 0 ? 1 : -1;
220         if (!currentLeftSideSign)
221             currentLeftSideSign = leftSideSign;
222         else if (currentLeftSideSign != leftSideSign)
223             return true;
224     }
225
226     return false;
227 }
228
229 bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const
230 {
231     // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions"
232
233     const FloatSize& thisDelta = vertex2() - vertex1();
234     const FloatSize& otherDelta = other.vertex2() - other.vertex1();
235     float denominator = determinant(thisDelta, otherDelta);
236     if (!denominator)
237         return false;
238
239     // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined
240     // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1),
241     // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point.
242
243     const FloatSize& vertex1Delta = vertex1() - other.vertex1();
244     float uThisLine = determinant(otherDelta, vertex1Delta) / denominator;
245     float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator;
246
247     if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1)
248         return false;
249
250     point = vertex1() + uThisLine * thisDelta;
251     return true;
252 }
253
254 } // namespace WebCore