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