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