| OLD | NEW |
|---|
| (Empty) |
| 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 | |
| 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& p
1) | |
| 48 { | |
| 49 return p0.x() == p1.x() && p0.y() == p1.y(); | |
| 50 } | |
| 51 | |
| 52 static inline bool isPointOnLineSegment(const FloatPoint& vertex1, const FloatPo
int& 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) % nVert
ices; | |
| 62 } | |
| 63 | |
| 64 static unsigned findNextEdgeVertexIndex(const FloatPolygon& polygon, unsigned ve
rtexIndex1, bool clockwise) | |
| 65 { | |
| 66 unsigned nVertices = polygon.numberOfVertices(); | |
| 67 unsigned vertexIndex2 = nextVertexIndex(vertexIndex1, nVertices, clockwise); | |
| 68 | |
| 69 while (vertexIndex2 && areCoincidentPoints(polygon.vertexAt(vertexIndex1), p
olygon.vertexAt(vertexIndex2))) | |
| 70 vertexIndex2 = nextVertexIndex(vertexIndex2, nVertices, clockwise); | |
| 71 | |
| 72 while (vertexIndex2) { | |
| 73 unsigned vertexIndex3 = nextVertexIndex(vertexIndex2, nVertices, clockwi
se); | |
| 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(PassOwnPtr<Vector<FloatPoint> > vertices, WindRule fi
llRule) | |
| 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) % nVertice
s); | |
| 104 bool clockwise = determinant(vertexAt(minVertexIndex) - prevVertex, nextVert
ex - 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, clo
ckwise); | |
| 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 FloatPo
lygonEdge*>& result) const | |
| 141 { | |
| 142 Vector<FloatPolygon::EdgeInterval> overlappingEdgeIntervals; | |
| 143 m_edgeTree.allOverlaps(FloatPolygon::EdgeInterval(minY, maxY, 0), overlappin
gEdgeIntervals); | |
| 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*>(over
lappingEdgeIntervals[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& vertex
2, 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) : containsEvenO
dd(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 * (ver
tex2 - 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 | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 32823017:
Move FloatPolygon.* and WindRule.h to Source/platform/ (Closed)
Base URL: https://chromium.googlesource.com/chromium/blink.git@master