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 "core/platform/graphics/FloatPolygon.h" 32 33#include "wtf/MathExtras.h" 34 35namespace WebCore { 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::contains(const FloatPoint& point) const 160{ 161 if (!m_boundingBox.contains(point)) 162 return false; 163 164 int windingNumber = 0; 165 for (unsigned i = 0; i < numberOfEdges(); ++i) { 166 const FloatPoint& vertex1 = edgeAt(i).vertex1(); 167 const FloatPoint& vertex2 = edgeAt(i).vertex2(); 168 if (isPointOnLineSegment(vertex1, vertex2, point)) 169 return true; 170 if (vertex2.y() < point.y()) { 171 if ((vertex1.y() > point.y()) && (leftSide(vertex1, vertex2, point) > 0)) 172 ++windingNumber; 173 } else if (vertex2.y() > point.y()) { 174 if ((vertex1.y() <= point.y()) && (leftSide(vertex1, vertex2, point) < 0)) 175 --windingNumber; 176 } 177 } 178 179 return windingNumber; 180} 181 182bool VertexPair::overlapsRect(const FloatRect& rect) const 183{ 184 bool boundsOverlap = (minX() < rect.maxX()) && (maxX() > rect.x()) && (minY() < rect.maxY()) && (maxY() > rect.y()); 185 if (!boundsOverlap) 186 return false; 187 188 float leftSideValues[4] = { 189 leftSide(vertex1(), vertex2(), rect.minXMinYCorner()), 190 leftSide(vertex1(), vertex2(), rect.maxXMinYCorner()), 191 leftSide(vertex1(), vertex2(), rect.minXMaxYCorner()), 192 leftSide(vertex1(), vertex2(), rect.maxXMaxYCorner()) 193 }; 194 195 int currentLeftSideSign = 0; 196 for (unsigned i = 0; i < 4; ++i) { 197 if (!leftSideValues[i]) 198 continue; 199 int leftSideSign = leftSideValues[i] > 0 ? 1 : -1; 200 if (!currentLeftSideSign) 201 currentLeftSideSign = leftSideSign; 202 else if (currentLeftSideSign != leftSideSign) 203 return true; 204 } 205 206 return false; 207} 208 209bool VertexPair::intersection(const VertexPair& other, FloatPoint& point) const 210{ 211 // See: http://paulbourke.net/geometry/pointlineplane/, "Intersection point of two lines in 2 dimensions" 212 213 const FloatSize& thisDelta = vertex2() - vertex1(); 214 const FloatSize& otherDelta = other.vertex2() - other.vertex1(); 215 float denominator = determinant(thisDelta, otherDelta); 216 if (!denominator) 217 return false; 218 219 // The two line segments: "this" vertex1,vertex2 and "other" vertex1,vertex2, have been defined 220 // in parametric form. Each point on the line segment is: vertex1 + u * (vertex2 - vertex1), 221 // when 0 <= u <= 1. We're computing the values of u for each line at their intersection point. 222 223 const FloatSize& vertex1Delta = vertex1() - other.vertex1(); 224 float uThisLine = determinant(otherDelta, vertex1Delta) / denominator; 225 float uOtherLine = determinant(thisDelta, vertex1Delta) / denominator; 226 227 if (uThisLine < 0 || uOtherLine < 0 || uThisLine > 1 || uOtherLine > 1) 228 return false; 229 230 point = vertex1() + uThisLine * thisDelta; 231 return true; 232} 233 234} // namespace WebCore 235