2 * Copyright (C) 2012 Adobe Systems Incorporated. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
8 * 1. Redistributions of source code must retain the above
9 * copyright notice, this list of conditions and the following
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.
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.
31 #include "core/rendering/shapes/PolygonShape.h"
33 #include "platform/geometry/LayoutPoint.h"
34 #include "wtf/MathExtras.h"
38 static inline FloatSize inwardEdgeNormal(const FloatPolygonEdge& edge)
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);
49 static inline FloatSize outwardEdgeNormal(const FloatPolygonEdge& edge)
51 return -inwardEdgeNormal(edge);
54 static inline bool overlapsYRange(const FloatRect& rect, float y1, float y2) { return !rect.isEmpty() && y2 >= y1 && y2 >= rect.y() && y1 <= rect.maxY(); }
56 float OffsetPolygonEdge::xIntercept(float y) const
58 ASSERT(y >= minY() && y <= maxY());
60 if (vertex1().y() == vertex2().y() || vertex1().x() == vertex2().x())
63 return vertex1().y() < vertex2().y() ? vertex1().x() : vertex2().x();
65 return vertex1().y() > vertex2().y() ? vertex1().x() : vertex2().x();
67 return vertex1().x() + ((y - vertex1().y()) * (vertex2().x() - vertex1().x()) / (vertex2().y() - vertex1().y()));
70 FloatShapeInterval OffsetPolygonEdge::clippedEdgeXRange(float y1, float y2) const
72 if (!overlapsYRange(y1, y2) || (y1 == maxY() && minY() <= y1) || (y2 == minY() && maxY() >= y2))
73 return FloatShapeInterval();
75 if (isWithinYRange(y1, y2))
76 return FloatShapeInterval(minX(), maxX());
78 // Clip the edge line segment to the vertical range y1,y2 and then return
79 // the clipped line segment's horizontal range.
81 FloatPoint minYVertex;
82 FloatPoint maxYVertex;
83 if (vertex1().y() < vertex2().y()) {
84 minYVertex = vertex1();
85 maxYVertex = vertex2();
87 minYVertex = vertex2();
88 maxYVertex = vertex1();
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));
95 static float circleXIntercept(float y, float radius)
98 return radius * sqrt(1 - (y * y) / (radius * radius));
101 static FloatShapeInterval clippedCircleXRange(const FloatPoint& center, float radius, float y1, float y2)
103 if (y1 >= center.y() + radius || y2 <= center.y() - radius)
104 return FloatShapeInterval();
106 if (center.y() >= y1 && center.y() <= y2)
107 return FloatShapeInterval(center.x() - radius, center.x() + radius);
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
112 float xi = circleXIntercept((y2 < center.y() ? y2 : y1) - center.y(), radius);
113 return FloatShapeInterval(center.x() - xi, center.x() + xi);
116 LayoutRect PolygonShape::shapeMarginLogicalBoundingBox() const
118 FloatRect box = m_polygon.boundingBox();
119 box.inflate(shapeMargin());
120 return LayoutRect(box);
123 LineSegment PolygonShape::getExcludedInterval(LayoutUnit logicalTop, LayoutUnit logicalHeight) const
125 float y1 = logicalTop.toFloat();
126 float y2 = logicalTop.toFloat() + logicalHeight.toFloat();
128 if (m_polygon.isEmpty() || !overlapsYRange(m_polygon.boundingBox(), y1 - shapeMargin(), y2 + shapeMargin()))
129 return LineSegment();
131 Vector<const FloatPolygonEdge*> overlappingEdges;
132 if (!m_polygon.overlappingEdges(y1 - shapeMargin(), y2 + shapeMargin(), overlappingEdges))
133 return LineSegment();
135 FloatShapeInterval excludedInterval;
136 for (unsigned i = 0; i < overlappingEdges.size(); i++) {
137 const FloatPolygonEdge& edge = *(overlappingEdges[i]);
138 if (edge.maxY() == edge.minY())
140 if (!shapeMargin()) {
141 excludedInterval.unite(OffsetPolygonEdge(edge, FloatSize()).clippedEdgeXRange(y1, y2));
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));
150 if (excludedInterval.isEmpty())
151 return LineSegment();
153 return LineSegment(excludedInterval.x1(), excludedInterval.x2());
156 void PolygonShape::buildDisplayPaths(DisplayPaths& paths) const
158 if (!m_polygon.numberOfVertices())
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();