src/third_party/WebKit/Source/core/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 "core/rendering/shapes/PolygonShape.h"
  32
  33 #include "platform/geometry/LayoutPoint.h"
  34 #include "wtf/MathExtras.h"
  35
  36 namespace WebCore {
  37
  38 static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge)
  39 {
  40     FloatSize edgeDelta = edge.vertex2() - edge.vertex1();
  41     if (!edgeDelta.width())
  42         return FloatSize((edgeDelta.height() > 0 ? -1 : 1), 0);
  43     if (!edgeDelta.height())
  44         return FloatSize(0, (edgeDelta.width() > 0 ? 1 : -1));
  45     float edgeLength = edgeDelta.diagonalLength();
  46     return FloatSize(-edgeDelta.height() / edgeLength, edgeDelta.width() / edgeLength);
  47 }
  48
  49 static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge)
  50 {
  51     return -inwardEdgeNormal(edge);
  52 }
  53
  54 static inline bool overlapsYRange(const FloatRect& rect, float y1, float y2) { return !rect.isEmpty() && y2 >= y1 && y2 >= rect.y() && y1 <= rect.maxY(); }
  55
  56 float OffsetPolygonEdge::xIntercept(float y) const
  57 {
  58     ASSERT(y >= minY() && y <= maxY());
  59
  60     if (vertex1().y() == vertex2().y() || vertex1().x() == vertex2().x())
  61         return minX();
  62     if (y == minY())
  63         return vertex1().y() < vertex2().y() ? vertex1().x() : vertex2().x();
  64     if (y == maxY())
  65         return vertex1().y() > vertex2().y() ? vertex1().x() : vertex2().x();
  66
  67     return vertex1().x() + ((y - vertex1().y()) * (vertex2().x() - vertex1().x()) / (vertex2().y() - vertex1().y()));
  68 }
  69
  70 FloatShapeInterval OffsetPolygonEdge::clippedEdgeXRange(float y1, float y2) const
  71 {
  72     if (!overlapsYRange(y1, y2) || (y1 == maxY() && minY() <= y1) || (y2 == minY() && maxY() >= y2))
  73         return FloatShapeInterval();
  74
  75     if (isWithinYRange(y1, y2))
  76         return FloatShapeInterval(minX(), maxX());
  77
  78     // Clip the edge line segment to the vertical range y1,y2 and then return
  79     // the clipped line segment's horizontal range.
  80
  81     FloatPoint minYVertex;
  82     FloatPoint maxYVertex;
  83     if (vertex1().y() < vertex2().y()) {
  84         minYVertex = vertex1();
  85         maxYVertex = vertex2();
  86     } else {
  87         minYVertex = vertex2();
  88         maxYVertex = vertex1();
  89     }
  90     float xForY1 = (minYVertex.y() < y1) ? xIntercept(y1) : minYVertex.x();
  91     float xForY2 = (maxYVertex.y() > y2) ? xIntercept(y2) : maxYVertex.x();
  92     return FloatShapeInterval(std::min(xForY1, xForY2), std::max(xForY1, xForY2));
  93 }
  94
  95 static float circleXIntercept(float y, float radius)
  96 {
  97     ASSERT(radius > 0);
  98     return radius * sqrt(1 - (y * y) / (radius * radius));
  99 }
 100
 101 static FloatShapeInterval clippedCircleXRange(const FloatPoint& center, float radius, float y1, float y2)
 102 {
 103     if (y1 > center.y() + radius || y2 < center.y() - radius)
 104         return FloatShapeInterval();
 105
 106     if (center.y() >= y1 && center.y() <= y2)
 107         return FloatShapeInterval(center.x() - radius, center.x() + radius);
 108
 109     // Clip the circle to the vertical range y1,y2 and return the extent of the clipped circle's
 110     // projection on the X axis
 111
 112     float xi =  circleXIntercept((y2 < center.y() ? y2 : y1) - center.y(), radius);
 113     return FloatShapeInterval(center.x() - xi, center.x() + xi);
 114 }
 115
 116 LayoutRect PolygonShape::shapeMarginLogicalBoundingBox() const
 117 {
 118     FloatRect box = m_polygon.boundingBox();
 119     box.inflate(shapeMargin());
 120     return LayoutRect(box);
 121 }
 122
 123 void PolygonShape::getExcludedIntervals(LayoutUnit logicalTop, LayoutUnit logicalHeight, SegmentList& result) const
 124 {
 125     float y1 = logicalTop.toFloat();
 126     float y2 = logicalTop.toFloat() + logicalHeight.toFloat();
 127
 128     if (m_polygon.isEmpty() || !overlapsYRange(m_polygon.boundingBox(), y1 - shapeMargin(), y2 + shapeMargin()))
 129         return;
 130
 131     Vector<const FloatPolygonEdge*> overlappingEdges;
 132     if (!m_polygon.overlappingEdges(y1 - shapeMargin(), y2 + shapeMargin(), overlappingEdges))
 133         return;
 134
 135     FloatShapeInterval excludedInterval;
 136     for (unsigned i = 0; i < overlappingEdges.size(); i++) {
 137         const FloatPolygonEdge& edge = *(overlappingEdges[i]);
 138         if (edge.maxY() == edge.minY())
 139             continue;
 140         if (!shapeMargin()) {
 141             excludedInterval.unite(OffsetPolygonEdge(edge, FloatSize()).clippedEdgeXRange(y1, y2));
 142         } else {
 143             excludedInterval.unite(OffsetPolygonEdge(edge, outwardEdgeNormal(edge) * shapeMargin()).clippedEdgeXRange(y1, y2));
 144             excludedInterval.unite(OffsetPolygonEdge(edge, inwardEdgeNormal(edge) * shapeMargin()).clippedEdgeXRange(y1, y2));
 145             excludedInterval.unite(clippedCircleXRange(edge.vertex1(), shapeMargin(), y1, y2));
 146         }
 147     }
 148
 149     if (!excludedInterval.isEmpty())
 150         result.append(LineSegment(excludedInterval.x1(), excludedInterval.x2()));
 151 }
 152
 153 void PolygonShape::buildDisplayPaths(DisplayPaths& paths) const
 154 {
 155     if (!m_polygon.numberOfVertices())
 156         return;
 157     paths.shape.moveTo(m_polygon.vertexAt(0));
 158     for (size_t i = 1; i < m_polygon.numberOfVertices(); ++i)
 159         paths.shape.addLineTo(m_polygon.vertexAt(i));
 160     paths.shape.closeSubpath();
 161 }
 162
 163 } // namespace WebCore