Modified: trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html (186975 => 186976)
--- trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/LayoutTests/fast/shrink-wrap/rect-shrink-wrap.html 2015-07-17 23:55:59 UTC (rev 186976)
@@ -1,20 +1,27 @@
<script>
-function testRects(rects) {
+function testRects(offset, rects, radius) {
if (!window.internals)
document.write("This test must be run in a test runner.")
+ if (radius == undefined)
+ radius = 8;
+
var concatRects = [];
for (var i in rects)
Array.prototype.push.apply(concatRects, rects[i]);
var path = undefined;
if (window.internals)
- path = window.internals.pathWithShrinkWrappedRects(concatRects);
+ path = window.internals.pathWithShrinkWrappedRects(concatRects, radius);
var canvas = document.getElementById("shrink");
var ctx = canvas.getContext("2d");
+ ctx.save();
+
+ ctx.translate.apply(ctx, offset);
+
ctx.fillStyle = "rgba(0,0,0,0.2)";
for (var i in rects)
@@ -29,118 +36,203 @@
ctx.lineWidth = 3;
if (path)
ctx.stroke(path);
+
+ ctx.restore();
}
window._onload_ = function () {
// Right and left aligned, touching:
- testRects([
- [20, 20, 50, 20],
- [20, 40, 35, 20],
- [20, 60, 20, 20]]);
+ testRects([20, 20], [
+ [0, 0, 50, 20],
+ [0, 20, 35, 20],
+ [0, 40, 20, 20]]);
- testRects([
- [20, 90, 20, 20],
- [20, 110, 35, 20],
- [20, 130, 50, 20]]);
+ testRects([20, 90], [
+ [0, 0, 20, 20],
+ [0, 20, 35, 20],
+ [0, 40, 50, 20]]);
- testRects([
- [80, 20, 50, 20],
- [95, 40, 35, 20],
- [110, 60, 20, 20]]);
+ testRects([80, 20], [
+ [0, 0, 50, 20],
+ [15, 20, 35, 20],
+ [30, 40, 20, 20]]);
- testRects([
- [110, 90, 20, 20],
- [95, 110, 35, 20],
- [80, 130, 50, 20]]);
+ testRects([80, 90], [
+ [30, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 40, 50, 20]]);
// Center aligned, touching:
- testRects([
- [170, 20, 100, 40],
- [190, 60, 60, 40],
- [205, 100, 30, 40]]);
+ testRects([170, 20], [
+ [0, 0, 100, 40],
+ [20, 40, 60, 40],
+ [35, 80, 30, 40]]);
- testRects([
- [305, 20, 30, 40],
- [290, 60, 60, 40],
- [270, 100, 100, 40]]);
+ testRects([270, 20], [
+ [35, 0, 30, 40],
+ [20, 40, 60, 40],
+ [0, 80, 100, 40]]);
- testRects([
- [370, 20, 100, 40],
- [405, 60, 30, 40],
- [390, 100, 60, 40]]);
+ testRects([370, 20], [
+ [0, 0, 100, 40],
+ [35, 40, 30, 40],
+ [20, 80, 60, 40]]);
// Other:
- testRects([
- [20, 200, 40, 40],
- [40, 220, 40, 40],
- [60, 240, 40, 40]]);
+ testRects([20, 200], [
+ [0, 0, 40, 40],
+ [20, 20, 40, 40],
+ [40, 40, 40, 40]]);
- testRects([
- [120, 200, 40, 40],
- [120, 240, 40, 40],
- [120, 280, 40, 40]]);
+ testRects([120, 200], [
+ [0, 40, 40, 40],
+ [20, 20, 40, 40],
+ [40, 0, 40, 40]]);
+ testRects([220, 200], [
+ [0, 0, 40, 40],
+ [0, 40, 40, 40],
+ [0, 80, 40, 40]]);
+
+ testRects([200, 350], [
+ [0, 0, 100, 50],
+ [0, 25, 50, 50]]);
+
// Non-touching:
- testRects([
- [180, 200, 40, 60],
- [180, 280, 40, 40]]);
+ testRects([20, 300], [
+ [0, 0, 40, 60],
+ [0, 80, 40, 40]]);
// Combination of touching and non-touching:
- testRects([
- [280, 200, 30, 40],
- [280, 280, 50, 40],
- [340, 200, 40, 40],
- [360, 240, 80, 40],
- [380, 280, 40, 40],
- [430, 200, 40, 20],
- [450, 215, 40, 20],
- [470, 230, 40, 20]]);
+ testRects([280, 200], [
+ [0, 0, 30, 40],
+ [0, 80, 50, 40],
+ [60, 0, 40, 40],
+ [80, 40, 80, 40],
+ [100, 80, 40, 40],
+ [150, 0, 40, 20],
+ [170, 15, 40, 20],
+ [190, 30, 40, 20]]);
- // Incorrectly sorted:
+ // Enclosing:
- testRects([
- [20, 380, 40, 40],
- [40, 360, 40, 40],
- [60, 340, 40, 40]]);
+ testRects([100, 300], [
+ [0, 0, 50, 50],
+ [10, 10, 20, 20]]);
- // Broken:
+ testRects([100, 370], [
+ [0, 0, 50, 50],
+ [10, 10, 20, 20],
+ [20, 20, 20, 20]]);
- testRects([
- [600+100, 90, 20, 20],
- [600+95, 110, 35, 20],
- [600+80, 130, 50, 20]]);
+ // Harder (widths less than the radius, horizontally arranged, etc.):
- testRects([
- [230+340, 20, 40, 40],
- [230+360, 60, 65, 40],
- [230+380, 100, 40, 40]]);
+ testRects([500, 20], [
+ [0, 0, 40, 40],
+ [20, 40, 65, 40],
+ [40, 80, 40, 40]]);
- // These should fallback to a rounded bounding rect:
+ testRects([600, 20], [
+ [20, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 40, 50, 20]]);
- testRects([
- [600+100, 190, 20, 20],
- [600+95, 210, 35, 20],
- [600+80, 210, 50, 20]]);
+ testRects([650, 100], [
+ [0, 0, 40, 40],
+ [40, 0, 40, 40],
+ [80, 0, 40, 40]]);
- testRects([
- [600+0, 250, 40, 40],
- [600+40, 250, 40, 40],
- [600+80, 250, 40, 40]]);
+ testRects([700, 20], [
+ [20, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 20, 50, 20]]);
- testRects([
- [600, 300, 20, 40],
- [600+20, 320, 20, 40],
- [600, 340, 20, 40]]);
+ testRects([600, 200], [
+ [0, 0, 20, 40],
+ [20, 20, 20, 40],
+ [40, 0, 20, 40]]);
- testRects([
- [700, 300, 20, 40],
- [700+20, 320, 20, 40],
- [700+40, 300, 20, 40]]);
+ testRects([700, 200], [
+ [0, 0, 20, 40],
+ [20, 25, 20, 40],
+ [0, 50, 20, 40]]);
+
+ // Huge radius:
+
+ testRects([20, 450], [
+ [0, 0, 50, 20],
+ [0, 20, 35, 20],
+ [0, 40, 20, 20]], 100);
+
+ testRects([20, 520], [
+ [0, 0, 20, 20],
+ [0, 20, 35, 20],
+ [0, 40, 50, 20]], 100);
+
+ testRects([80, 450], [
+ [0, 0, 50, 20],
+ [15, 20, 35, 20],
+ [30, 40, 20, 20]], 100);
+
+ testRects([80, 520], [
+ [30, 0, 20, 20],
+ [15, 20, 35, 20],
+ [0, 40, 50, 20]], 100);
+
+ testRects([170, 450], [
+ [0, 0, 100, 40],
+ [20, 40, 60, 40],
+ [35, 80, 30, 40]], 100);
+
+ testRects([270, 450], [
+ [35, 0, 30, 40],
+ [20, 40, 60, 40],
+ [0, 80, 100, 40]], 100);
+
+ testRects([370, 450], [
+ [0, 0, 100, 40],
+ [35, 40, 30, 40],
+ [20, 80, 60, 40]], 100);
+
+ testRects([750, 500], [
+ [0, 0, 20, 40],
+ [20, 20, 20, 40],
+ [0, 40, 20, 40]]);
+
+ // Holes:
+
+ testRects([400, 300], [
+ [30, 0, 40, 40],
+ [60, 40, 40, 40],
+ [30, 80, 40, 40],
+ [0, 40, 40, 40]]);
+
+ // Lines with overlap:
+
+ testRects([520, 450], [
+ [0, 0, 50, 20],
+ [0, 15, 35, 20],
+ [0, 30, 20, 20]]);
+
+ testRects([520, 520], [
+ [0, 0, 20, 20],
+ [0, 15, 35, 20],
+ [0, 30, 50, 20]]);
+
+ testRects([580, 450], [
+ [0, 0, 50, 20],
+ [15, 15, 35, 20],
+ [30, 30, 20, 20]]);
+
+ testRects([580, 520], [
+ [30, 0, 20, 20],
+ [15, 15, 35, 20],
+ [0, 30, 50, 20]]);
}
</script>
Modified: trunk/Source/WebCore/platform/graphics/PathUtilities.cpp (186975 => 186976)
--- trunk/Source/WebCore/platform/graphics/PathUtilities.cpp 2015-07-17 23:47:47 UTC (rev 186975)
+++ trunk/Source/WebCore/platform/graphics/PathUtilities.cpp 2015-07-17 23:55:59 UTC (rev 186976)
@@ -29,234 +29,305 @@
#include "FloatPoint.h"
#include "FloatRect.h"
+#include "GeometryUtilities.h"
#include <math.h>
namespace WebCore {
-static void addShrinkWrapRightCorner(Path& path, const FloatRect* fromRect, const FloatRect* toRect, float radius)
-{
- FloatSize horizontalRadius(radius, 0);
- FloatSize verticalRadius(0, radius);
+class FloatPointGraph {
+ WTF_MAKE_NONCOPYABLE(FloatPointGraph);
+public:
+ FloatPointGraph() { }
- if (!fromRect) {
- // For the first (top) rect:
+ class Node : public FloatPoint {
+ WTF_MAKE_NONCOPYABLE(Node);
+ public:
+ Node(FloatPoint point)
+ : FloatPoint(point)
+ { }
- path.moveTo(toRect->minXMinYCorner() + horizontalRadius);
+ const Vector<Node*>& nextPoints() const { return m_nextPoints; }
+ void addNextPoint(Node* node)
+ {
+ if (!m_nextPoints.contains(node))
+ m_nextPoints.append(node);
+ }
- // Across the top, towards the right.
- path.addLineTo(toRect->maxXMinYCorner() - horizontalRadius);
+ bool isVisited() const { return m_visited; }
+ void visit() { m_visited = true; }
- // Arc the top corner.
- path.addArcTo(toRect->maxXMinYCorner(), toRect->maxXMinYCorner() + verticalRadius, radius);
- } else if (!toRect) {
- // For the last rect:
+ void reset() { m_visited = false; m_nextPoints.clear(); }
- // Down the right.
- path.addLineTo(fromRect->maxXMaxYCorner() - verticalRadius);
+ private:
+ Vector<Node*> m_nextPoints;
+ bool m_visited { false };
+ };
- // Arc the bottom corner.
- path.addArcTo(fromRect->maxXMaxYCorner(), fromRect->maxXMaxYCorner() - horizontalRadius, radius);
- } else {
- // For middle rects:
+ typedef std::pair<Node*, Node*> Edge;
+ typedef Vector<Edge> Polygon;
- float rightEdgeDifference = toRect->maxX() - fromRect->maxX();
+ Node* findOrCreateNode(FloatPoint);
- // Skip over rects with equal edges, because we can't make
- // sensible curves between them.
- if (fabsf(rightEdgeDifference) < std::numeric_limits<float>::epsilon())
- return;
+ void reset()
+ {
+ for (auto& node : m_allNodes)
+ node->reset();
+ }
- if (rightEdgeDifference < 0) {
- float effectiveY = std::max(toRect->y(), fromRect->maxY());
- FloatPoint toRectMaxXMinYCorner = FloatPoint(toRect->maxX(), effectiveY);
+private:
+ Vector<std::unique_ptr<Node>> m_allNodes;
+};
- // Down the right.
- path.addLineTo(FloatPoint(fromRect->maxX(), effectiveY) - verticalRadius);
+FloatPointGraph::Node* FloatPointGraph::findOrCreateNode(FloatPoint point)
+{
+ for (auto& testNode : m_allNodes) {
+ if (areEssentiallyEqual(*testNode, point))
+ return testNode.get();
+ }
- // Arc the outer corner.
- path.addArcTo(FloatPoint(fromRect->maxX(), effectiveY), FloatPoint(fromRect->maxX(), effectiveY) - horizontalRadius, radius);
+ m_allNodes.append(std::make_unique<FloatPointGraph::Node>(point));
+ return m_allNodes.last().get();
+}
- // Across the bottom, towards the left.
- path.addLineTo(toRectMaxXMinYCorner + horizontalRadius);
+static bool findLineSegmentIntersection(const FloatPointGraph::Edge& edgeA, const FloatPointGraph::Edge& edgeB, FloatPoint& intersectionPoint)
+{
+ if (!findIntersection(*edgeA.first, *edgeA.second, *edgeB.first, *edgeB.second, intersectionPoint))
+ return false;
- // Arc the inner corner.
- path.addArcTo(toRectMaxXMinYCorner, toRectMaxXMinYCorner + verticalRadius, radius);
- } else {
- float effectiveY = std::min(toRect->y(), fromRect->maxY());
- FloatPoint toRectMaxXMinYCorner = FloatPoint(toRect->maxX(), effectiveY);
+ FloatPoint edgeAVec(*edgeA.second - *edgeA.first);
+ FloatPoint edgeBVec(*edgeB.second - *edgeB.first);
- // Down the right.
- path.addLineTo(FloatPoint(fromRect->maxX(), effectiveY) - verticalRadius);
+ float dotA = edgeAVec.dot(toFloatPoint(intersectionPoint - *edgeA.first));
+ if (dotA < 0 || dotA > edgeAVec.lengthSquared())
+ return false;
- // Arc the inner corner.
- path.addArcTo(FloatPoint(fromRect->maxX(), effectiveY), FloatPoint(fromRect->maxX(), effectiveY) + horizontalRadius, radius);
+ float dotB = edgeBVec.dot(toFloatPoint(intersectionPoint - *edgeB.first));
+ if (dotB < 0 || dotB > edgeBVec.lengthSquared())
+ return false;
- // Across the bottom, towards the right.
- path.addLineTo(toRectMaxXMinYCorner - horizontalRadius);
+ return true;
+}
- // Arc the outer corner.
- path.addArcTo(toRectMaxXMinYCorner, toRectMaxXMinYCorner + verticalRadius, radius);
+static bool addIntersectionPoints(Vector<FloatPointGraph::Polygon>& polys, FloatPointGraph& graph)
+{
+ bool foundAnyIntersections = false;
+
+ Vector<FloatPointGraph::Edge> allEdges;
+ for (auto& poly : polys)
+ allEdges.appendVector(poly);
+
+ for (const FloatPointGraph::Edge& edgeA : allEdges) {
+ Vector<FloatPointGraph::Node*> intersectionPoints({edgeA.first, edgeA.second});
+
+ for (const FloatPointGraph::Edge& edgeB : allEdges) {
+ if (&edgeA == &edgeB)
+ continue;
+
+ FloatPoint intersectionPoint;
+ if (!findLineSegmentIntersection(edgeA, edgeB, intersectionPoint))
+ continue;
+ foundAnyIntersections = true;
+ intersectionPoints.append(graph.findOrCreateNode(intersectionPoint));
}
+
+ std::sort(intersectionPoints.begin(), intersectionPoints.end(), [edgeA] (FloatPointGraph::Node* a, FloatPointGraph::Node* b) {
+ return FloatPoint(*edgeA.first - *b).lengthSquared() > FloatPoint(*edgeA.first - *a).lengthSquared();
+ });
+
+ for (unsigned pointIndex = 1; pointIndex < intersectionPoints.size(); pointIndex++)
+ intersectionPoints[pointIndex - 1]->addNextPoint(intersectionPoints[pointIndex]);
}
+
+ return foundAnyIntersections;
}
-static void addShrinkWrapLeftCorner(Path& path, const FloatRect* fromRect, const FloatRect* toRect, float radius)
+static FloatPointGraph::Polygon walkGraphAndExtractPolygon(FloatPointGraph::Node* startNode)
{
- FloatSize horizontalRadius(radius, 0);
- FloatSize verticalRadius(0, radius);
+ FloatPointGraph::Polygon outPoly;
- if (!fromRect) {
- // For the first (bottom) rect:
+ FloatPointGraph::Node* currentNode = startNode;
+ FloatPointGraph::Node* previousNode = startNode;
- // Across the bottom, towards the left.
- path.addLineTo(toRect->minXMaxYCorner() + horizontalRadius);
+ do {
+ currentNode->visit();
- // Arc the bottom corner.
- path.addArcTo(toRect->minXMaxYCorner(), toRect->minXMaxYCorner() - verticalRadius, radius);
+ FloatPoint currentVec(*previousNode - *currentNode);
+ currentVec.normalize();
- } else if (!toRect) {
- // For the last (top) rect:
+ // Walk the graph, at each node choosing the next non-visited
+ // point with the greatest internal angle.
+ FloatPointGraph::Node* nextNode = nullptr;
+ float nextNodeAngle = 0;
+ for (auto potentialNextNode : currentNode->nextPoints()) {
+ if (potentialNextNode == currentNode)
+ continue;
- // Up the left.
- path.addLineTo(fromRect->minXMinYCorner() + verticalRadius);
+ // If we can get back to the start, we should, ignoring the fact that we already visited it.
+ // Otherwise we'll head inside the shape.
+ if (potentialNextNode == startNode) {
+ nextNode = startNode;
+ break;
+ }
- // Arc the top corner.
- path.addArcTo(fromRect->minXMinYCorner(), fromRect->minXMinYCorner() + horizontalRadius, radius);
- } else {
- // For middle rects:
- float leftEdgeDifference = fromRect->x() - toRect->x();
+ if (potentialNextNode->isVisited())
+ continue;
- // Skip over rects with equal edges, because we can't make
- // sensible curves between them.
- if (fabsf(leftEdgeDifference) < std::numeric_limits<float>::epsilon())
- return;
+ FloatPoint nextVec(*potentialNextNode - *currentNode);
+ nextVec.normalize();
- if (leftEdgeDifference < 0) {
- float effectiveY = std::min(toRect->maxY(), fromRect->y());
- FloatPoint toRectMinXMaxYCorner = FloatPoint(toRect->x(), effectiveY);
+ float angle = acos(nextVec.dot(currentVec));
+ float crossZ = nextVec.x() * currentVec.y() - nextVec.y() * currentVec.x();
- // Up the right.
- path.addLineTo(FloatPoint(fromRect->x(), effectiveY) + verticalRadius);
+ if (crossZ < 0)
+ angle = (2 * M_PI) - angle;
- // Arc the inner corner.
- path.addArcTo(FloatPoint(fromRect->x(), effectiveY), FloatPoint(fromRect->x(), effectiveY) + horizontalRadius, radius);
+ if (!nextNode || angle > nextNodeAngle) {
+ nextNode = potentialNextNode;
+ nextNodeAngle = angle;
+ }
+ }
- // Across the bottom, towards the right.
- path.addLineTo(toRectMinXMaxYCorner - horizontalRadius);
+ // If we don't end up at a node adjacent to the starting node,
+ // something went wrong (there's probably a hole in the shape),
+ // so bail out. We'll use a bounding box instead.
+ if (!nextNode)
+ return FloatPointGraph::Polygon();
- // Arc the outer corner.
- path.addArcTo(toRectMinXMaxYCorner, toRectMinXMaxYCorner - verticalRadius, radius);
- } else {
- float effectiveY = std::max(toRect->maxY(), fromRect->y());
- FloatPoint toRectMinXMaxYCorner = FloatPoint(toRect->x(), effectiveY);
+ outPoly.append(std::make_pair(currentNode, nextNode));
- // Up the right.
- path.addLineTo(FloatPoint(fromRect->x(), effectiveY) + verticalRadius);
+ previousNode = currentNode;
+ currentNode = nextNode;
+ } while (currentNode != startNode);
- // Arc the outer corner.
- path.addArcTo(FloatPoint(fromRect->x(), effectiveY), FloatPoint(fromRect->x(), effectiveY) - horizontalRadius, radius);
+ return outPoly;
+}
- // Across the bottom, towards the left.
- path.addLineTo(toRectMinXMaxYCorner + horizontalRadius);
+static FloatPointGraph::Node* findUnvisitedPolygonStartPoint(Vector<FloatPointGraph::Polygon>& polys)
+{
+ for (auto& poly : polys) {
+ for (auto& edge : poly) {
+ if (edge.first->isVisited() || edge.second->isVisited())
+ goto nextPolygon;
+ }
- // Arc the inner corner.
- path.addArcTo(toRectMinXMaxYCorner, toRectMinXMaxYCorner - verticalRadius, radius);
- }
+ // FIXME: We should make sure we find an outside edge to start with.
+ return poly[0].first;
+ nextPolygon:
+ continue;
}
+ return nullptr;
}
-static void addShrinkWrappedPathForRects(Path& path, Vector<FloatRect>& rects, float radius)
+static Vector<FloatPointGraph::Polygon> unitePolygons(Vector<FloatPointGraph::Polygon>& polys, FloatPointGraph& graph)
{
- size_t rectCount = rects.size();
+ graph.reset();
- std::sort(rects.begin(), rects.end(), [](FloatRect a, FloatRect b) { return b.y() > a.y(); });
+ // There are no intersections, so the polygons are disjoint (we already removed wholly-contained rects in an earlier step).
+ if (!addIntersectionPoints(polys, graph))
+ return polys;
- for (size_t i = 0; i <= rectCount; ++i)
- addShrinkWrapRightCorner(path, i ? &rects[i - 1] : nullptr, i < rectCount ? &rects[i] : nullptr, radius);
+ Vector<FloatPointGraph::Polygon> unitedPolygons;
- for (size_t i = 0; i <= rectCount; ++i) {
- size_t reverseIndex = rectCount - i;
- addShrinkWrapLeftCorner(path, reverseIndex < rectCount ? &rects[reverseIndex] : nullptr, reverseIndex ? &rects[reverseIndex - 1] : nullptr, radius);
+ while (FloatPointGraph::Node* startNode = findUnvisitedPolygonStartPoint(polys)) {
+ FloatPointGraph::Polygon unitedPolygon = walkGraphAndExtractPolygon(startNode);
+ if (unitedPolygon.isEmpty())
+ return Vector<FloatPointGraph::Polygon>();
+ unitedPolygons.append(unitedPolygon);
}
- path.closeSubpath();
+ return unitedPolygons;
}
-static bool rectsIntersectOrTouch(const FloatRect& a, const FloatRect& b)
+static FloatPointGraph::Polygon edgesForRect(FloatRect rect, FloatPointGraph& graph)
{
- return !a.isEmpty() && !b.isEmpty()
- && a.x() <= b.maxX() && b.x() <= a.maxX()
- && a.y() <= b.maxY() && b.y() <= a.maxY();
+ auto minMin = graph.findOrCreateNode(rect.minXMinYCorner());
+ auto minMax = graph.findOrCreateNode(rect.minXMaxYCorner());
+ auto maxMax = graph.findOrCreateNode(rect.maxXMaxYCorner());
+ auto maxMin = graph.findOrCreateNode(rect.maxXMinYCorner());
+
+ return FloatPointGraph::Polygon({
+ std::make_pair(minMin, maxMin),
+ std::make_pair(maxMin, maxMax),
+ std::make_pair(maxMax, minMax),
+ std::make_pair(minMax, minMin)
+ });
}
-static Vector<FloatRect>* findSetContainingRect(Vector<Vector<FloatRect>>& sets, FloatRect rect)
+Path PathUtilities::pathWithShrinkWrappedRects(const Vector<FloatRect>& rects, float radius)
{
- for (auto& set : sets) {
- if (set.contains(rect))
- return &set;
+ Path path;
+
+ if (rects.isEmpty())
+ return path;
+
+ if (rects.size() > 20) {
+ path.addRoundedRect(unionRect(rects), FloatSize(radius, radius));
+ return path;
}
- return nullptr;
-}
+ Vector<FloatRect> sortedRects = rects;
-static Vector<Vector<FloatRect>> contiguousRectGroupsFromRects(const Vector<FloatRect>& rects)
-{
- Vector<std::pair<FloatRect, FloatRect>> intersections;
- Vector<FloatRect> soloRects = rects;
+ std::sort(sortedRects.begin(), sortedRects.end(), [](FloatRect a, FloatRect b) { return b.y() > a.y(); });
- for (auto& rectA : rects) {
- for (auto& rectB : rects) {
- if (rectA == rectB)
+ FloatPointGraph graph;
+ Vector<FloatPointGraph::Polygon> rectPolygons;
+ rectPolygons.reserveInitialCapacity(sortedRects.size());
+
+ for (auto& rect : sortedRects) {
+ bool isContained = false;
+ for (auto& otherRect : sortedRects) {
+ if (&rect == &otherRect)
continue;
-
- if (rectsIntersectOrTouch(rectA, rectB)) {
- intersections.append(std::make_pair(rectA, rectB));
- soloRects.removeAllMatching([rectA, rectB](FloatRect q) { return q == rectA || q == rectB; });
+ if (otherRect.contains(rect)) {
+ isContained = true;
+ break;
}
}
+
+ if (!isContained)
+ rectPolygons.append(edgesForRect(rect, graph));
}
- Vector<Vector<FloatRect>> rectSets;
+ Vector<FloatPointGraph::Polygon> polys = unitePolygons(rectPolygons, graph);
- for (auto& intersectingPair : intersections) {
- if (Vector<FloatRect>* rectContainingFirst = findSetContainingRect(rectSets, intersectingPair.first)) {
- if (!rectContainingFirst->contains(intersectingPair.second))
- rectContainingFirst->append(intersectingPair.second);
- continue;
- }
+ if (polys.isEmpty()) {
+ path.addRoundedRect(unionRect(sortedRects), FloatSize(radius, radius));
+ return path;
+ }
- if (Vector<FloatRect>* rectContainingSecond = findSetContainingRect(rectSets, intersectingPair.second)) {
- if (!rectContainingSecond->contains(intersectingPair.first))
- rectContainingSecond->append(intersectingPair.first);
- continue;
- }
+ for (auto& poly : polys) {
+ for (unsigned i = 0; i < poly.size(); i++) {
+ FloatPointGraph::Edge& toEdge = poly[i];
+ // Connect the first edge to the last.
+ FloatPointGraph::Edge& fromEdge = (i > 0) ? poly[i - 1] : poly[poly.size() - 1];
- // We didn't find a set including either of our rects, so start a new one.
- rectSets.append(Vector<FloatRect>({intersectingPair.first, intersectingPair.second}));
+ FloatPoint fromEdgeVec = toFloatPoint(*fromEdge.second - *fromEdge.first);
+ FloatPoint toEdgeVec = toFloatPoint(*toEdge.second - *toEdge.first);
- continue;
- }
+ // Clamp the radius to no more than half the length of either adjacent edge,
+ // because we want a smooth curve and don't want unequal radii.
+ float clampedRadius = std::min(radius, fabsf(fromEdgeVec.x() ? fromEdgeVec.x() : fromEdgeVec.y()) / 2);
+ clampedRadius = std::min(clampedRadius, fabsf(toEdgeVec.x() ? toEdgeVec.x() : toEdgeVec.y()) / 2);
- for (auto& rect : soloRects) {
- ASSERT(!findSetContainingRect(rectSets, rect));
- rectSets.append(Vector<FloatRect>({rect}));
- }
+ FloatPoint fromEdgeNorm = fromEdgeVec;
+ fromEdgeNorm.normalize();
+ FloatPoint toEdgeNorm = toEdgeVec;
+ toEdgeNorm.normalize();
- return rectSets;
-}
+ // Project the radius along the incoming and outgoing edge.
+ FloatSize fromOffset = clampedRadius * toFloatSize(fromEdgeNorm);
+ FloatSize toOffset = clampedRadius * toFloatSize(toEdgeNorm);
-Path PathUtilities::pathWithShrinkWrappedRects(const Vector<FloatRect>& rects, float radius)
-{
- Path path;
+ if (!i)
+ path.moveTo(*fromEdge.second - fromOffset);
+ else
+ path.addLineTo(*fromEdge.second - fromOffset);
+ path.addArcTo(*fromEdge.second, *toEdge.first + toOffset, clampedRadius);
+ }
- if (rects.isEmpty())
- return path;
+ path.closeSubpath();
+ }
- Vector<Vector<FloatRect>> rectSets = contiguousRectGroupsFromRects(rects);
-
- for (auto& set : rectSets)
- addShrinkWrappedPathForRects(path, set, radius);
-
return path;
}
