Home | History | Annotate | Download | only in shapes 
      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/rendering/shapes/PolygonShape.h"
     32 
     33 #include "core/platform/graphics/LayoutPoint.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] = flooredLayoutPoint(vertices[i]);
    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())
    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())
    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, Vector<ShapeInterval>& result)
    229 {
    230     if (!inside)
    231         result.append(ShapeInterval(x));
    232     else
    233         result[result.size() - 1].x2 = 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, Vector<ShapeInterval>& 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         const FloatPolygonEdge& thisEdge = *thisIntersection.edge;
    284         bool evenOddCrossing = !windCount;
    285 
    286         if (polygon.fillRule() == RULE_EVENODD) {
    287             windCount += (thisEdge.vertex2().y() > thisEdge.vertex1().y()) ? 1 : -1;
    288             evenOddCrossing = evenOddCrossing || !windCount;
    289         }
    290 
    291         if (evenOddCrossing) {
    292             bool edgeCrossing = thisIntersection.type == Normal;
    293             if (!edgeCrossing) {
    294                 FloatPoint prevVertex;
    295                 FloatPoint thisVertex;
    296                 FloatPoint nextVertex;
    297 
    298                 if (getVertexIntersectionVertices(thisIntersection, prevVertex, thisVertex, nextVertex)) {
    299                     if (nextVertex.y() == y)
    300                         edgeCrossing = (isMinY) ? prevVertex.y() > y : prevVertex.y() < y;
    301                     else if (prevVertex.y() == y)
    302                         edgeCrossing = (isMinY) ? nextVertex.y() > y : nextVertex.y() < y;
    303                     else
    304                         edgeCrossing = true;
    305                 }
    306             }
    307             if (edgeCrossing)
    308                 inside = appendIntervalX(thisIntersection.point.x(), inside, result);
    309         }
    310 
    311         ++index;
    312     }
    313 }
    314 
    315 static void computeOverlappingEdgeXProjections(const FloatPolygon& polygon, float y1, float y2, Vector<ShapeInterval>& result)
    316 {
    317     Vector<const FloatPolygonEdge*> edges;
    318     if (!polygon.overlappingEdges(y1, y2, edges))
    319         return;
    320 
    321     EdgeIntersection intersection;
    322     for (unsigned i = 0; i < edges.size(); ++i) {
    323         const FloatPolygonEdge *edge = edges[i];
    324         float x1;
    325         float x2;
    326 
    327         if (edge->minY() < y1) {
    328             computeXIntersection(edge, y1, intersection);
    329             x1 = intersection.point.x();
    330         } else {
    331             x1 = (edge->vertex1().y() < edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
    332         }
    333 
    334         if (edge->maxY() > y2) {
    335             computeXIntersection(edge, y2, intersection);
    336             x2 = intersection.point.x();
    337         } else {
    338             x2 = (edge->vertex1().y() > edge->vertex2().y()) ? edge->vertex1().x() : edge->vertex2().x();
    339         }
    340 
    341         if (x1 > x2)
    342             std::swap(x1, x2);
    343 
    344         if (x2 > x1)
    345             result.append(ShapeInterval(x1, x2));
    346     }
    347 
    348     sortShapeIntervals(result);
    349 }
    350 
    351 void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
    352 {
    353     const FloatPolygon& polygon = shapeMarginBounds();
    354     if (polygon.isEmpty())
    355         return;
    356 
    357     float y1 = logicalTop;
    358     float y2 = logicalTop + logicalHeight;
    359 
    360     Vector<ShapeInterval> y1XIntervals, y2XIntervals;
    361     computeXIntersections(polygon, y1, true, y1XIntervals);
    362     computeXIntersections(polygon, y2, false, y2XIntervals);
    363 
    364     Vector<ShapeInterval> mergedIntervals;
    365     mergeShapeIntervals(y1XIntervals, y2XIntervals, mergedIntervals);
    366 
    367     Vector<ShapeInterval> edgeIntervals;
    368     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
    369 
    370     Vector<ShapeInterval> excludedIntervals;
    371     mergeShapeIntervals(mergedIntervals, edgeIntervals, excludedIntervals);
    372 
    373     for (unsigned i = 0; i < excludedIntervals.size(); ++i) {
    374         ShapeInterval interval = excludedIntervals[i];
    375         result.append(LineSegment(interval.x1, interval.x2));
    376     }
    377 }
    378 
    379 void PolygonShape::getIncludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
    380 {
    381     const FloatPolygon& polygon = shapePaddingBounds();
    382     if (polygon.isEmpty())
    383         return;
    384 
    385     float y1 = logicalTop;
    386     float y2 = logicalTop + logicalHeight;
    387 
    388     Vector<ShapeInterval> y1XIntervals, y2XIntervals;
    389     computeXIntersections(polygon, y1, true, y1XIntervals);
    390     computeXIntersections(polygon, y2, false, y2XIntervals);
    391 
    392     Vector<ShapeInterval> commonIntervals;
    393     intersectShapeIntervals(y1XIntervals, y2XIntervals, commonIntervals);
    394 
    395     Vector<ShapeInterval> edgeIntervals;
    396     computeOverlappingEdgeXProjections(polygon, y1, y2, edgeIntervals);
    397 
    398     Vector<ShapeInterval> includedIntervals;
    399     subtractShapeIntervals(commonIntervals, edgeIntervals, includedIntervals);
    400 
    401     for (unsigned i = 0; i < includedIntervals.size(); ++i) {
    402         ShapeInterval interval = includedIntervals[i];
    403         result.append(LineSegment(interval.x1, interval.x2));
    404     }
    405 }
    406 
    407 static inline bool firstFitRectInPolygon(const FloatPolygon& polygon, const FloatRect& rect, unsigned offsetEdgeIndex1, unsigned offsetEdgeIndex2)
    408 {
    409     Vector<const FloatPolygonEdge*> edges;
    410     if (!polygon.overlappingEdges(rect.y(), rect.maxY(), edges))
    411         return true;
    412 
    413     for (unsigned i = 0; i < edges.size(); ++i) {
    414         const FloatPolygonEdge* edge = edges[i];
    415         if (edge->edgeIndex() != offsetEdgeIndex1 && edge->edgeIndex() != offsetEdgeIndex2 && edge->overlapsRect(rect))
    416             return false;
    417     }
    418 
    419     return true;
    420 }
    421 
    422 static inline bool aboveOrToTheLeft(const FloatRect& r1, const FloatRect& r2)
    423 {
    424     if (r1.y() < r2.y())
    425         return true;
    426     if (r1.y() == r2.y())
    427         return r1.x() < r2.x();
    428     return false;
    429 }
    430 
    431 bool PolygonShape::firstIncludedIntervalLogicalTop(LayoutUnit minLogicalIntervalTop, const LayoutSize& minLogicalIntervalSize, LayoutUnit& result) const
    432 {
    433     float minIntervalTop = minLogicalIntervalTop;
    434     float minIntervalHeight = minLogicalIntervalSize.height();
    435     float minIntervalWidth = minLogicalIntervalSize.width();
    436 
    437     const FloatPolygon& polygon = shapePaddingBounds();
    438     const FloatRect boundingBox = polygon.boundingBox();
    439     if (minIntervalWidth > boundingBox.width())
    440         return false;
    441 
    442     float minY = std::max(boundingBox.y(), minIntervalTop);
    443     float maxY = minY + minIntervalHeight;
    444 
    445     if (maxY > boundingBox.maxY())
    446         return false;
    447 
    448     Vector<const FloatPolygonEdge*> edges;
    449     polygon.overlappingEdges(minIntervalTop, boundingBox.maxY(), edges);
    450 
    451     float dx = minIntervalWidth / 2;
    452     float dy = minIntervalHeight / 2;
    453     Vector<OffsetPolygonEdge> offsetEdges;
    454 
    455     for (unsigned i = 0; i < edges.size(); ++i) {
    456         const FloatPolygonEdge& edge = *(edges[i]);
    457         const FloatPoint& vertex0 = edge.previousEdge().vertex1();
    458         const FloatPoint& vertex1 = edge.vertex1();
    459         const FloatPoint& vertex2 = edge.vertex2();
    460         Vector<OffsetPolygonEdge> offsetEdgeBuffer;
    461 
    462         if (vertex2.y() > vertex1.y() ? vertex2.x() >= vertex1.x() : vertex1.x() >= vertex2.x()) {
    463             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, -dy)));
    464             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, dy)));
    465         } else {
    466             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(dx, dy)));
    467             offsetEdgeBuffer.append(OffsetPolygonEdge(edge, FloatSize(-dx, -dy)));
    468         }
    469 
    470         if (isReflexVertex(vertex0, vertex1, vertex2)) {
    471             if (vertex2.x() <= vertex1.x() && vertex0.x() <= vertex1.x())
    472                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(dx, -dy), FloatSize(dx, dy)));
    473             else if (vertex2.x() >= vertex1.x() && vertex0.x() >= vertex1.x())
    474                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(-dx, dy)));
    475             if (vertex2.y() <= vertex1.y() && vertex0.y() <= vertex1.y())
    476                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, dy), FloatSize(dx, dy)));
    477             else if (vertex2.y() >= vertex1.y() && vertex0.y() >= vertex1.y())
    478                 offsetEdgeBuffer.append(OffsetPolygonEdge(vertex1, FloatSize(-dx, -dy), FloatSize(dx, -dy)));
    479         }
    480 
    481         for (unsigned j = 0; j < offsetEdgeBuffer.size(); ++j) {
    482             if (offsetEdgeBuffer[j].maxY() >= minY)
    483                 offsetEdges.append(offsetEdgeBuffer[j]);
    484         }
    485     }
    486 
    487     offsetEdges.append(OffsetPolygonEdge(polygon, minIntervalTop, FloatSize(0, dy)));
    488 
    489     FloatPoint offsetEdgesIntersection;
    490     FloatRect firstFitRect;
    491     bool firstFitFound = false;
    492 
    493     for (unsigned i = 0; i < offsetEdges.size() - 1; ++i) {
    494         for (unsigned j = i + 1; j < offsetEdges.size(); ++j) {
    495             if (offsetEdges[i].intersection(offsetEdges[j], offsetEdgesIntersection)) {
    496                 FloatPoint potentialFirstFitLocation(offsetEdgesIntersection.x() - dx, offsetEdgesIntersection.y() - dy);
    497                 FloatRect potentialFirstFitRect(potentialFirstFitLocation, minLogicalIntervalSize);
    498                 if ((offsetEdges[i].basis() == OffsetPolygonEdge::LineTop
    499                     || offsetEdges[j].basis() == OffsetPolygonEdge::LineTop
    500                     || potentialFirstFitLocation.y() >= minIntervalTop)
    501                     && (!firstFitFound || aboveOrToTheLeft(potentialFirstFitRect, firstFitRect))
    502                     && polygon.contains(offsetEdgesIntersection)
    503                     && firstFitRectInPolygon(polygon, potentialFirstFitRect, offsetEdges[i].edgeIndex(), offsetEdges[j].edgeIndex())) {
    504                     firstFitFound = true;
    505                     firstFitRect = potentialFirstFitRect;
    506                 }
    507             }
    508         }
    509     }
    510 
    511     if (firstFitFound)
    512         result = LayoutUnit::fromFloatCeil(firstFitRect.y());
    513     return firstFitFound;
    514 }
    515 
    516 } // namespace WebCore
    517