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 36namespace blink { 37 38static 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 49static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge) 50{ 51 return -inwardEdgeNormal(edge); 52} 53 54static inline bool overlapsYRange(const FloatRect& rect, float y1, float y2) { return !rect.isEmpty() && y2 >= y1 && y2 >= rect.y() && y1 <= rect.maxY(); } 55 56float 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 70FloatShapeInterval 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 95static float circleXIntercept(float y, float radius) 96{ 97 ASSERT(radius > 0); 98 return radius * sqrt(1 - (y * y) / (radius * radius)); 99} 100 101static 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 116LayoutRect PolygonShape::shapeMarginLogicalBoundingBox() const 117{ 118 FloatRect box = m_polygon.boundingBox(); 119 box.inflate(shapeMargin()); 120 return LayoutRect(box); 121} 122 123LineSegment PolygonShape::getExcludedInterval(LayoutUnit logicalTop, LayoutUnit logicalHeight) 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 LineSegment(); 130 131 Vector<const FloatPolygonEdge*> overlappingEdges; 132 if (!m_polygon.overlappingEdges(y1 - shapeMargin(), y2 + shapeMargin(), overlappingEdges)) 133 return LineSegment(); 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 excludedInterval.unite(clippedCircleXRange(edge.vertex2(), shapeMargin(), y1, y2)); 147 } 148 } 149 150 if (excludedInterval.isEmpty()) 151 return LineSegment(); 152 153 return LineSegment(excludedInterval.x1(), excludedInterval.x2()); 154} 155 156void PolygonShape::buildDisplayPaths(DisplayPaths& paths) const 157{ 158 if (!m_polygon.numberOfVertices()) 159 return; 160 paths.shape.moveTo(m_polygon.vertexAt(0)); 161 for (size_t i = 1; i < m_polygon.numberOfVertices(); ++i) 162 paths.shape.addLineTo(m_polygon.vertexAt(i)); 163 paths.shape.closeSubpath(); 164} 165 166} // namespace blink 167