Web Inspector: [CSS Shapes] Refactor highlighting code to decrease Shapes API surface
[WebKit-https.git] / Source / WebCore / rendering / shapes / PolygonShape.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 "PolygonShape.h"
32
33 #include "ShapeInterval.h"
34 #include <wtf/MathExtras.h>
35
36 namespace WebCore {
37
38 enum EdgeIntersectionType {
39     Normal,
40     VertexMinY,
41     VertexMaxY,
42     VertexYBoth
43 };
44
45 struct EdgeIntersection {
46     const FloatPolygonEdge* edge;
47     FloatPoint point;
48     EdgeIntersectionType type;
49 };
50
51 static inline float leftSide(const FloatPoint& vertex1, const FloatPoint& vertex2, const FloatPoint& point)
52 {
53     return ((point.x() - vertex1.x()) * (vertex2.y() - vertex1.y())) - ((vertex2.x() - vertex1.x()) * (point.y() - vertex1.y()));
54 }
55
56 static inline bool isReflexVertex(const FloatPoint& prevVertex, const FloatPoint& vertex, const FloatPoint& nextVertex)
57 {
58     return leftSide(prevVertex, nextVertex, vertex) < 0;
59 }
60
61 static bool computeXIntersection(const FloatPolygonEdge* edgePointer, float y, EdgeIntersection& result)
62 {
63     const FloatPolygonEdge& edge = *edgePointer;
64
65     if (edge.minY() > y || edge.maxY() < y)
66         return false;
67
68     const FloatPoint& vertex1 = edge.vertex1();
69     const FloatPoint& vertex2 = edge.vertex2();
70     float dy = vertex2.y() - vertex1.y();
71
72     float intersectionX;
73     EdgeIntersectionType intersectionType;
74
75     if (!dy) {
76         intersectionType = VertexYBoth;
77         intersectionX = edge.minX();
78     } else if (y == edge.minY()) {
79         intersectionType = VertexMinY;
80         intersectionX = (vertex1.y() < vertex2.y()) ? vertex1.x() : vertex2.x();
81     } else if (y == edge.maxY()) {
82         intersectionType = VertexMaxY;
83         intersectionX = (vertex1.y() > vertex2.y()) ? vertex1.x() : vertex2.x();
84     } else {
85         intersectionType = Normal;
86         intersectionX = ((y - vertex1.y()) * (vertex2.x() - vertex1.x()) / dy) + vertex1.x();
87     }
88
89     result.edge = edgePointer;
90     result.type = intersectionType;
91     result.point.set(intersectionX, y);
92
93     return true;
94 }
95
96 static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge)
97 {
98     FloatSize edgeDelta = edge.vertex2() - edge.vertex1();
99     if (!edgeDelta.width())
100         return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0);
101     if (!edgeDelta.height())
102         return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1));
103     float edgeLength = edgeDelta.diagonalLength();
104     return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength);
105 }
106
107 static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge)
108 {
109     return -inwardEdgeNormal(edge);
110 }
111
112 static inline void appendArc(Vector<FloatPoint>& vertices, const FloatPoint& arcCenter, float arcRadius, const FloatPoint& startArcVertex, const FloatPoint& endArcVertex, bool padding)
113 {
114     float startAngle = atan2(startArcVertex.y() - arcCenter.y(), startArcVertex.x() - arcCenter.x());
115     float endAngle = atan2(endArcVertex.y() - arcCenter.y(), endArcVertex.x() - arcCenter.x());
116     const float twoPI = piFloat * 2;
117     if (startAngle < 0)
118         startAngle += twoPI;
119     if (endAngle < 0)
120         endAngle += twoPI;
121     float angle = (startAngle > endAngle) ? (startAngle - endAngle) : (startAngle + twoPI - endAngle);
122     const float arcSegmentCount = 6; // An even number so that one arc vertex will be eactly arcRadius from arcCenter.
123     float arcSegmentAngle =  ((padding) ? -angle : twoPI - angle) / arcSegmentCount;
124
125     vertices.append(startArcVertex);
126     for (unsigned i = 1; i < arcSegmentCount; ++i) {
127         float angle = startAngle + arcSegmentAngle * i;
128         vertices.append(arcCenter + FloatPoint(cos(angle) * arcRadius, sin(angle) * arcRadius));
129     }
130     vertices.append(endArcVertex);
131 }
132
133 static inline void snapVerticesToLayoutUnitGrid(Vector<FloatPoint>& vertices)
134 {
135     for (unsigned i = 0; i < vertices.size(); ++i)
136         vertices[i].set(LayoutUnit(vertices[i].x()).toFloat(), LayoutUnit(vertices[i].y()).toFloat());
137 }
138
139 static inline PassOwnPtr<FloatPolygon> computeShapePaddingBounds(const FloatPolygon& polygon, float padding, WindRule fillRule)
140 {
141     OwnPtr<Vector<FloatPoint>> paddedVertices = adoptPtr(new Vector<FloatPoint>());
142     FloatPoint intersection;
143
144     for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
145         const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
146         const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
147         OffsetPolygonEdge thisOffsetEdge(thisEdge, inwardEdgeNormal(thisEdge) * padding);
148         OffsetPolygonEdge prevOffsetEdge(prevEdge, inwardEdgeNormal(prevEdge) * padding);
149
150         if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
151             paddedVertices->append(intersection);
152         else if (isReflexVertex(prevEdge.vertex1(), thisEdge.vertex1(), thisEdge.vertex2()))
153             appendArc(*paddedVertices, thisEdge.vertex1(), padding, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), true);
154     }
155
156     snapVerticesToLayoutUnitGrid(*paddedVertices);
157     return adoptPtr(new FloatPolygon(paddedVertices.release(), fillRule));
158 }
159
160 static inline PassOwnPtr<FloatPolygon> computeShapeMarginBounds(const FloatPolygon& polygon, float margin, WindRule fillRule)
161 {
162     OwnPtr<Vector<FloatPoint>> marginVertices = adoptPtr(new Vector<FloatPoint>());
163     FloatPoint intersection;
164
165     for (unsigned i = 0; i < polygon.numberOfEdges(); ++i) {
166         const FloatPolygonEdge& thisEdge = polygon.edgeAt(i);
167         const FloatPolygonEdge& prevEdge = thisEdge.previousEdge();
168         OffsetPolygonEdge thisOffsetEdge(thisEdge, outwardEdgeNormal(thisEdge) * margin);
169         OffsetPolygonEdge prevOffsetEdge(prevEdge, outwardEdgeNormal(prevEdge) * margin);
170
171         if (prevOffsetEdge.intersection(thisOffsetEdge, intersection))
172             marginVertices->append(intersection);
173         else
174             appendArc(*marginVertices, thisEdge.vertex1(), margin, prevOffsetEdge.vertex2(), thisOffsetEdge.vertex1(), false);
175     }
176
177     snapVerticesToLayoutUnitGrid(*marginVertices);
178     return adoptPtr(new FloatPolygon(marginVertices.release(), fillRule));
179 }
180
181 const FloatPolygon& PolygonShape::shapePaddingBounds() const
182 {
183     ASSERT(shapePadding() >= 0);
184     if (!shapePadding() || m_polygon.isEmpty())
185         return m_polygon;
186
187     if (!m_paddingBounds)
188         m_paddingBounds = computeShapePaddingBounds(m_polygon, shapePadding(), m_polygon.fillRule());
189
190     return *m_paddingBounds;
191 }
192
193 const FloatPolygon& PolygonShape::shapeMarginBounds() const
194 {
195     ASSERT(shapeMargin() >= 0);
196     if (!shapeMargin() || m_polygon.isEmpty())
197         return m_polygon;
198
199     if (!m_marginBounds)
200         m_marginBounds = computeShapeMarginBounds(m_polygon, shapeMargin(), m_polygon.fillRule());
201
202     return *m_marginBounds;
203 }
204
205 static inline bool getVertexIntersectionVertices(const EdgeIntersection& intersection, FloatPoint& prevVertex, FloatPoint& thisVertex, FloatPoint& nextVertex)
206 {
207     if (intersection.type != VertexMinY && intersection.type != VertexMaxY)
208         return false;
209
210     ASSERT(intersection.edge && intersection.edge->polygon());
211     const FloatPolygon& polygon = *(intersection.edge->polygon());
212     const FloatPolygonEdge& thisEdge = *(intersection.edge);
213
214     if ((intersection.type == VertexMinY && (thisEdge.vertex1().y() < thisEdge.vertex2().y()))
215         || (intersection.type == VertexMaxY && (thisEdge.vertex1().y() > thisEdge.vertex2().y()))) {
216         prevVertex = polygon.vertexAt(thisEdge.previousEdge().vertexIndex1());
217         thisVertex = polygon.vertexAt(thisEdge.vertexIndex1());
218         nextVertex = polygon.vertexAt(thisEdge.vertexIndex2());
219     } else {
220         prevVertex = polygon.vertexAt(thisEdge.vertexIndex1());
221         thisVertex = polygon.vertexAt(thisEdge.vertexIndex2());
222         nextVertex = polygon.vertexAt(thisEdge.nextEdge().vertexIndex2());
223     }
224
225     return true;
226 }
227
228 static inline bool appendIntervalX(float x, bool inside, FloatShapeIntervals& result)
229 {
230     if (!inside)
231         result.append(FloatShapeInterval(x, x));
232     else
233         result.last().setX2(x);
234
235     return !inside;
236 }
237
238 static bool compareEdgeIntersectionX(const EdgeIntersection& intersection1, const EdgeIntersection& intersection2)
239 {
240     float x1 = intersection1.point.x();
241     float x2 = intersection2.point.x();
242     return (x1 == x2) ? intersection1.type < intersection2.type : x1 < x2;
243 }
244
245 static void computeXIntersections(const FloatPolygon& polygon, float y, bool isMinY, FloatShapeIntervals& result)
246 {
247     Vector<const FloatPolygonEdge*> edges;
248     if (!polygon.overlappingEdges(y, y, edges))
249         return;
250
251     Vector<EdgeIntersection> intersections;
252     EdgeIntersection intersection;
253     for (unsigned i = 0; i < edges.size(); ++i) {
254         if (computeXIntersection(edges[i], y, intersection) && intersection.type != VertexYBoth)
255             intersections.append(intersection);
256     }
257
258     if (intersections.size() < 2)
259         return;
260
261     std::sort(intersections.begin(), intersections.end(), WebCore::compareEdgeIntersectionX);
262
263     unsigned index = 0;
264     int windCount = 0;
265     bool inside = false;
266
267     while (index < intersections.size()) {
268         const EdgeIntersection& thisIntersection = intersections[index];
269         if (index + 1 < intersections.size()) {
270             const EdgeIntersection& nextIntersection = intersections[index + 1];
271             if ((thisIntersection.point.x() == nextIntersection.point.x()) && (thisIntersection.type == VertexMinY || thisIntersection.type == VertexMaxY)) {
272                 if (thisIntersection.type == nextIntersection.type) {
273                     // Skip pairs of intersections whose types are VertexMaxY,VertexMaxY and VertexMinY,VertexMinY.
274                     index += 2;
275                 } else {
276                     // Replace pairs of intersections whose types are VertexMinY,VertexMaxY or VertexMaxY,VertexMinY with one intersection.
277                     ++index;
278                 }
279                 continue;
280             }
281         }
282
283         bool edgeCrossing = thisIntersection.type == Normal;
284         if (!edgeCrossing) {
285             FloatPoint prevVertex;
286             FloatPoint thisVertex;
287             FloatPoint nextVertex;
288
289             if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) {
290                 if (nextVertex.y() == y)
291                     edgeCrossing = (isMinY) ? prevVertex.y() > y : prevVertex.y() < y;
292                 else if (prevVertex.y() == y)
293                     edgeCrossing = (isMinY) ? nextVertex.y() > y : nextVertex.y() < y;
294                 else
295                     edgeCrossing = true;
296             }
297         }
298
299         if (edgeCrossing && polygon.fillRule() == RULE_NONZERO) {
300             const FloatPolygonEdge& thisEdge = *thisIntersection.edge;
301             windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
302         }
303
304         if (edgeCrossing && (!inside || !windCount))
305             inside = appendIntervalX(thisIntersection.point.x(), inside, result);
306
307         ++index;
308     }
309 }
310
311 static bool compareX1(const FloatShapeInterval a, const FloatShapeInterval& b) { return a.x1() < b.x1(); }
312
313 static void sortAndMergeShapeIntervals(FloatShapeIntervals& intervals)
314 {
315     std::sort(intervals.begin(), intervals.end(), compareX1);
316
317     for (unsigned i = 1; i < intervals.size(); ) {
318         const FloatShapeInterval& thisInterval = intervals[i];
319         FloatShapeInterval& previousInterval = intervals[i - 1];
320         if (thisInterval.overlaps(previousInterval)) {
321             previousInterval.setX2(std::max<float>(previousInterval.x2(), thisInterval.x2()));
322             intervals.remove(i);
323         } else
324             ++i;
325     }
326 }
327
328 static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, FloatShapeIntervals& result)
329 {
330     Vector<const FloatPolygonEdge*> edges;
331     if (!polygon.overlappingEdges(y1, y2, edges))
332         return;
333
334     EdgeIntersection intersection;
335     for (unsigned i = 0; i < edges.size(); ++i) {
336         const FloatPolygonEdge *edge = edges[i];
337         float x1;
338         float x2;
339
340         if (edge->minY() < y1) {
341             computeXIntersection(edge, y1, intersection);
342             x1 = intersection.point.x();
343         } else
344             x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
345
346         if (edge->maxY() > y2) {
347             computeXIntersection(edge, y2, intersection);
348             x2 = intersection.point.x();
349         } else
350             x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
351
352         if (x1 > x2)
353             std::swap(x1, x2);
354
355         if (x2 > x1)
356             result.append(FloatShapeInterval(x1, x2));
357     }
358
359     sortAndMergeShapeIntervals(result);
360 }
361
362 void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
363 {
364     const FloatPolygon& polygon = shapeMarginBounds();
365     if (polygon.isEmpty())
366         return;
367
368     float y1 = logicalTop;
369     float y2 = logicalTop + logicalHeight;
370
371     FloatShapeIntervals y1XIntervals, y2XIntervals;
372     computeXIntersections(polygon, y1, true, y1XIntervals);
373     computeXIntersections(polygon, y2, false, y2XIntervals);
374
375     FloatShapeIntervals mergedIntervals;
376     FloatShapeInterval::uniteShapeIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
377
378     FloatShapeIntervals edgeIntervals;
379     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
380
381     FloatShapeIntervals excludedIntervals;
382     FloatShapeInterval::uniteShapeIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
383
384     for (unsigned i = 0; i < excludedIntervals.size(); ++i) {
385         FloatShapeInterval interval = excludedIntervals[i];
386         result.append(LineSegment(interval.x1(), interval.x2()));
387     }
388 }
389
390 void PolygonShape::getIncludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
391 {
392     const FloatPolygon& polygon = shapePaddingBounds();
393     if (polygon.isEmpty())
394         return;
395
396     float y1 = logicalTop;
397     float y2 = logicalTop + logicalHeight;
398
399     FloatShapeIntervals y1XIntervals, y2XIntervals;
400     computeXIntersections(polygon, y1, true, y1XIntervals);
401     computeXIntersections(polygon, y2, false, y2XIntervals);
402
403     FloatShapeIntervals commonIntervals;
404     FloatShapeInterval::intersectShapeIntervals(y1XIntervals, y2XIntervals, commonIntervals);
405
406     FloatShapeIntervals edgeIntervals;
407     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
408
409     FloatShapeIntervals includedIntervals;
410     FloatShapeInterval::subtractShapeIntervals(commonIntervals, edgeIntervals, includedIntervals);
411
412     for (unsigned i = 0; i < includedIntervals.size(); ++i) {
413         const FloatShapeInterval& interval = includedIntervals[i];
414         result.append(LineSegment(interval.x1(), interval.x2()));
415     }
416 }
417
418 static inline bool firstFitRectInPolygon(const FloatPolygon& polygon, const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2)
419 {
420     Vector<const FloatPolygonEdge*> edges;
421     if (!polygon.overlappingEdges(rect.y(), rect.maxY(), edges))
422         return true;
423
424     for (unsigned i = 0; i < edges.size(); ++i) {
425         const FloatPolygonEdge* edge = edges[i];
426         if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect))
427             return false;
428     }
429
430     return true;
431 }
432
433 static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2)
434 {
435     if (r1.y() < r2.y())
436         return true;
437     if (r1.y() == r2.y())
438         return r1.x() < r2.x();
439     return false;
440 }
441
442 bool PolygonShape::firstIncludedIntervalLogicalTop(LayoutUnit minLogicalIntervalTop, const LayoutSize& minLogicalIntervalSize, LayoutUnit& result) const
443 {
444     float minIntervalTop = minLogicalIntervalTop;
445     float minIntervalHeight = minLogicalIntervalSize.height();
446     float minIntervalWidth = minLogicalIntervalSize.width();
447
448     const FloatPolygon& polygon = shapePaddingBounds();
449     const FloatRect boundingBox = polygon.boundingBox();
450     if (minIntervalWidth > boundingBox.width())
451         return false;
452
453     float minY = std::max(boundingBox.y(), minIntervalTop);
454     float maxY = minY + minIntervalHeight;
455
456     if (maxY > boundingBox.maxY())
457         return false;
458
459     Vector<const FloatPolygonEdge*> edges;
460     polygon.overlappingEdges(minIntervalTop, boundingBox.maxY(), edges);
461
462     float dx = minIntervalWidth / 2;
463     float dy = minIntervalHeight / 2;
464     Vector<OffsetPolygonEdge> offsetEdges;
465
466     for (unsigned i = 0; i < edges.size(); ++i) {
467         const FloatPolygonEdge& edge = *(edges[i]);
468         const FloatPoint& vertex0 = edge.previousEdge().vertex1();
469         const FloatPoint& vertex1 = edge.vertex1();
470         const FloatPoint& vertex2 = edge.vertex2();
471         Vector<OffsetPolygonEdge> offsetEdgeBuffer;
472
473         if (vertex2.y() > vertex1.y() ? vertex2.x() >= vertex1.x() : vertex1.x() >= vertex2.x()) {
474             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, -dy)));
475             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, dy)));
476         } else {
477             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, dy)));
478             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, -dy)));
479         }
480
481         if (isReflexVertex(vertex0, vertex1, vertex2)) {
482             if (vertex2.x() <= vertex1.x() && vertex0.x() <= vertex1.x())
483                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(dx, -dy), FloatSize(dx, dy)));
484             else if (vertex2.x() >= vertex1.x() && vertex0.x() >= vertex1.x())
485                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(-dx, dy)));
486             if (vertex2.y() <= vertex1.y() && vertex0.y() <= vertex1.y())
487                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, dy), FloatSize(dx, dy)));
488             else if (vertex2.y() >= vertex1.y() && vertex0.y() >= vertex1.y())
489                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(dx, -dy)));
490         }
491
492         for (unsigned j = 0; j < offsetEdgeBuffer.size(); ++j)
493             if (offsetEdgeBuffer[j].maxY() >= minY)
494                 offsetEdges.append(offsetEdgeBuffer[j]);
495     }
496
497     offsetEdges.append(OffsetPolygonEdge(polygon, minIntervalTop, FloatSize(0, dy)));
498
499     FloatPoint offsetEdgesIntersection;
500     FloatRect firstFitRect;
501     bool firstFitFound = false;
502
503     for (unsigned i = 0; i < offsetEdges.size() - 1; ++i) {
504         for (unsigned j = i + 1; j < offsetEdges.size(); ++j) {
505             if (offsetEdges[i].intersection(offsetEdges[j], offsetEdgesIntersection)) {
506                 FloatPoint potentialFirstFitLocation(offsetEdgesIntersection.x() - dx, offsetEdgesIntersection.y() - dy);
507                 FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize);
508                 if ((offsetEdges[i].basis() == OffsetPolygonEdge::LineTop
509                     || offsetEdges[j].basis() == OffsetPolygonEdge::LineTop
510                     || potentialFirstFitLocation.y() >= minIntervalTop)
511                     && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect))
512                     && polygon.contains(offsetEdgesIntersection)
513                     && firstFitRectInPolygon(polygon, potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
514                     firstFitFound = true;
515                     firstFitRect = potentialFirstFitRect;
516                 }
517             }
518         }
519     }
520
521     if (firstFitFound)
522         result = ceiledLayoutUnit(firstFitRect.y());
523     return firstFitFound;
524 }
525
526 void PolygonShape::buildPath(Path& path) const
527 {
528     FloatPoint vertex;
529
530     if (!m_polygon.numberOfVertices())
531         return;
532
533     path.moveTo(m_polygon.vertexAt(0));
534
535     for (size_t i = 1; i < m_polygon.numberOfVertices(); i++)
536         path.addLineTo(m_polygon.vertexAt(i));
537
538     path.closeSubpath();
539 }
540
541 } // namespace WebCore