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