diff --git a/libs/widgetutils/CMakeLists.txt b/libs/widgetutils/CMakeLists.txt --- a/libs/widgetutils/CMakeLists.txt +++ b/libs/widgetutils/CMakeLists.txt @@ -17,6 +17,7 @@ KoProperties.cpp KoFileDialog.cpp KoResourcePaths.cpp + KisConvexHullAlgorithm.cpp config/kcolorscheme.cpp config/kcolorschememanager.cpp diff --git a/libs/widgetutils/KisConvexHullAlgorithm.h b/libs/widgetutils/KisConvexHullAlgorithm.h new file mode 100644 --- /dev/null +++ b/libs/widgetutils/KisConvexHullAlgorithm.h @@ -0,0 +1,46 @@ +/* + * Copyright (c) 2016 Stefano Bonicatti + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + * Boston, MA 02110-1301, USA. + * + * Algorithm based on the article and code at + * http://www.codeproject.com/Articles/775753/A-Convex-Hull-Algorithm-and-its-implementation-in +*/ +#include + +class QPointF; +struct HullPoint; +struct ConvexHull; + +class KisConvexHullAlgorithm +{ +public: + static QPolygonF generateConvexHull(QPolygonF &points, qreal bias); +private: + static void buildQuadrants(QPolygonF &points, ConvexHull &q1, ConvexHull &q2, ConvexHull &q3, ConvexHull &q4); + static void buildHulls(QPolygonF &points, ConvexHull &q1Hull, ConvexHull &q2Hull, ConvexHull &q3Hull, ConvexHull &q4Hull); + static qreal slope(const qreal &startX, const qreal &startY, const qreal &endX, const qreal &endY); + static void buildQ1Hull(QPolygonF &points, ConvexHull &hull); + static void buildQ2Hull(QPolygonF &points, ConvexHull &hull); + static void buildQ3Hull(QPolygonF &points, ConvexHull &hull); + static void buildQ4Hull(QPolygonF &points, ConvexHull &hull); + static void addPointToHull(const QPointF &point, qreal slopeToNext, int indexLow, int indexHigh, int indexMax, + int indexLowToRemove, int indexHighToRemove, ConvexHull &hull); + static bool isConvexToQ1Point(const QPointF &point, const HullPoint &reference); + static bool isConvexToQ2Point(const QPointF &point, const HullPoint &reference); + static bool isConvexToQ3Point(const QPointF &point, const HullPoint &reference); + static bool isConvexToQ4Point(const QPointF &point, const HullPoint &reference); +}; diff --git a/libs/widgetutils/KisConvexHullAlgorithm.cpp b/libs/widgetutils/KisConvexHullAlgorithm.cpp new file mode 100644 --- /dev/null +++ b/libs/widgetutils/KisConvexHullAlgorithm.cpp @@ -0,0 +1,595 @@ +/* + * Copyright (c) 2016 Stefano Bonicatti + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public License + * along with this library; see the file COPYING.LIB. If not, write to + * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + * Boston, MA 02110-1301, USA. + * + * Algorithm based on the article and code at + * http://www.codeproject.com/Articles/775753/A-Convex-Hull-Algorithm-and-its-implementation-in +*/ +#include "KisConvexHullAlgorithm.h" + +#include + +typedef struct HullPoint +{ + qreal x; + qreal y; + qreal slopeToNext; +}HullPoint; + +typedef struct ConvexHull +{ + QVector points; + QPointF rootPoint; + +}ConvexHull; + +QPolygonF KisConvexHullAlgorithm::generateConvexHull(QPolygonF &points, qreal bias) +{ + if (points.count() == 0) return QPolygonF(); + + ConvexHull q1; + ConvexHull q2; + ConvexHull q3; + ConvexHull q4; + + HullPoint basePoint = {points[0].x(), points[0].y(), 0}; + q1.points.append(basePoint); + q1.points.append(basePoint); + q2.points.append(basePoint); + q2.points.append(basePoint); + q3.points.append(basePoint); + q3.points.append(basePoint); + q4.points.append(basePoint); + q4.points.append(basePoint); + + buildQuadrants(points, q1, q2, q3, q4); + buildHulls(points, q1, q2, q3, q4); + + QPolygonF finalHull; + Q_FOREACH(const HullPoint &hullPoint, q1.points) { + finalHull << QPointF(hullPoint.x, hullPoint.y); + } + + Q_FOREACH(const HullPoint &hullPoint, q2.points) { + finalHull << QPointF(hullPoint.x, hullPoint.y); + } + + Q_FOREACH(const HullPoint &hullPoint, q3.points) { + finalHull << QPointF(hullPoint.x, hullPoint.y); + } + + Q_FOREACH(const HullPoint &hullPoint, q4.points) { + finalHull << QPointF(hullPoint.x, hullPoint.y); + } + + + return finalHull; +} + +void KisConvexHullAlgorithm::buildQuadrants(QPolygonF &points, ConvexHull &q1, ConvexHull &q2, ConvexHull &q3, ConvexHull &q4) +{ + HullPoint &q1FirstPoint = q1.points[0]; + HullPoint &q1LastPoint = q1.points[1]; + HullPoint &q2FirstPoint = q2.points[0]; + HullPoint &q2LastPoint = q2.points[1]; + HullPoint &q3FirstPoint = q3.points[0]; + HullPoint &q3LastPoint = q3.points[1]; + HullPoint &q4FirstPoint = q4.points[0]; + HullPoint &q4LastPoint = q4.points[1]; + + Q_FOREACH(const QPointF &point, points) { + + // Q1 Quadrant + if (point.x() == q1FirstPoint.x) { + if (point.y() > q1FirstPoint.y) { + q1FirstPoint.y = point.y(); + } + } + else if (point.x() > q1FirstPoint.x) { + q1FirstPoint.x = point.x(); + q1FirstPoint.y = point.y(); + } + + if (point.y() == q1LastPoint.y) { + if (point.x() > q1LastPoint.x) { + q1LastPoint.x = point.x(); + } + } + else if (point.y() > q1LastPoint.y) { + q1LastPoint.x = point.x(); + q1LastPoint.y = point.y(); + } + + // Q2 Quadrant + if (point.y() == q2FirstPoint.y) { + if (point.x() < q2FirstPoint.x) { + q2FirstPoint.x = point.x(); + } + } + else if (point.y() > q2FirstPoint.y) { + q2FirstPoint.x = point.x(); + q2FirstPoint.y = point.y(); + } + + if (point.x() == q2LastPoint.x) { + if (point.y() > q2LastPoint.y) { + q2LastPoint.y = point.y(); + } + } + else if (point.x() < q2LastPoint.x) { + q2LastPoint.x = point.x(); + q2LastPoint.y = point.y(); + } + + + // Q3 Quadrant + if (point.x() == q3FirstPoint.x) { + if (point.y() < q3FirstPoint.y) { + q3FirstPoint.y = point.y(); + } + } + else if (point.x() < q3FirstPoint.x) { + q3FirstPoint.x = point.x(); + q3FirstPoint.y = point.y(); + } + + if (point.y() == q3LastPoint.y) { + if (point.x() < q3LastPoint.x) { + q3LastPoint.x = point.x(); + } + } + else if (point.y() < q3LastPoint.y) { + q3LastPoint.x = point.x(); + q3LastPoint.y = point.y(); + } + + + // Q4 Quadrant + if (point.y() == q4FirstPoint.y) { + if (point.x() < q4FirstPoint.x) { + q4FirstPoint.x = point.x(); + } + } + else if (point.y() < q4FirstPoint.y) { + q4FirstPoint.x = point.x(); + q4FirstPoint.y = point.y(); + } + + if (point.x() == q4LastPoint.x) { + if (point.y() < q4LastPoint.y) { + q4LastPoint.y = point.y(); + } + } + else if (point.x() > q4LastPoint.x) { + q4LastPoint.x = point.x(); + q4LastPoint.y = point.y(); + } + } + + + q1.rootPoint.setX(q1LastPoint.x); + q1.rootPoint.setY(q1FirstPoint.y); + + q2.rootPoint.setX(q2FirstPoint.x); + q2.rootPoint.setY(q2LastPoint.y); + + q3.rootPoint.setX(q3LastPoint.x); + q3.rootPoint.setY(q3FirstPoint.y); + + q4.rootPoint.setX(q4FirstPoint.x); + q4.rootPoint.setY(q4LastPoint.y); +} + +void KisConvexHullAlgorithm::buildHulls(QPolygonF &points, ConvexHull &q1Hull, ConvexHull &q2Hull, ConvexHull &q3Hull, ConvexHull &q4Hull) +{ + if (q1Hull.points[0].x != q1Hull.points[1].x && q1Hull.points[0].y != q1Hull.points[1].y) { + q1Hull.points[0].slopeToNext = slope(q1Hull.points[0].x, q1Hull.points[0].y, q1Hull.points[1].x, q1Hull.points[1].y); + q1Hull.points[1].slopeToNext = 0; + buildQ1Hull(points, q1Hull); + } + + if (q2Hull.points[0].x != q2Hull.points[1].x && q2Hull.points[0].y != q2Hull.points[1].y) { + q2Hull.points[0].slopeToNext = slope(q2Hull.points[0].x, q2Hull.points[0].y, q2Hull.points[1].x, q2Hull.points[1].y); + q2Hull.points[1].slopeToNext = std::numeric_limits::max(); + buildQ2Hull(points, q2Hull); + } + + if (q3Hull.points[0].x != q3Hull.points[1].x && q3Hull.points[0].y != q3Hull.points[1].y) { + q3Hull.points[0].slopeToNext = slope(q3Hull.points[0].x, q3Hull.points[0].y, q3Hull.points[1].x, q3Hull.points[1].y); + q3Hull.points[1].slopeToNext = 0; + buildQ3Hull(points, q3Hull); + } + + if (q4Hull.points[0].x != q4Hull.points[1].x && q4Hull.points[0].y != q4Hull.points[1].y) { + q4Hull.points[0].slopeToNext = slope(q4Hull.points[0].x, q4Hull.points[0].y, q4Hull.points[1].x, q4Hull.points[1].y); + q4Hull.points[1].slopeToNext = std::numeric_limits::max(); + buildQ4Hull(points, q4Hull); + } +} + +void KisConvexHullAlgorithm::buildQ1Hull(QPolygonF &points, ConvexHull &hull) +{ + + Q_FOREACH(const QPointF &point, points) { + // The point is inside this quadrant + if (point.x() > hull.rootPoint.x() && point.y() > hull.rootPoint.y()) { + int indexLow = 0; + int indexMax = hull.points.count() - 1; + int indexHigh = indexMax; + bool validPoint = true; + + // We have have atleast 1 point between low and high + while (indexLow != (indexHigh - 1)) { + int index = ((indexHigh - indexLow) >> 1) + indexLow; + + if (validPoint = isConvexToQ1Point(point, hull.points[index])) { + + if (point.x() > hull.points[index].x) { + indexHigh = index; + continue; + } + + if (point.x() < hull.points[index].x) { + indexLow = index; + continue; + } + + if (point.x() == hull.points[index].x) { + indexLow = index; + indexHigh = index + 1; + } + } + + break; + } + + if (validPoint) { + HullPoint &previousPoint = hull.points[indexLow]; + + // Quick elimination without checking the slope + if (point.y() <= previousPoint.y) { + continue; + } + + HullPoint &nextPoint = hull.points[indexHigh]; + qreal slopeToNext = slope(point.x(), point.y(), nextPoint.x, nextPoint.y); + + if (slopeToNext > previousPoint.slopeToNext) { + int indexLowToRemove = indexHigh; + int indexHighToRemove = indexLow; + + if (hull.points[indexHigh].y < point.y()) { // We can remove 1 or more points without slope calc + indexHighToRemove = indexHigh; + while (hull.points[indexHighToRemove + 1].y < point.y()) { + ++indexHighToRemove; + } + } + + addPointToHull(point, slopeToNext, indexLow, indexHigh, indexMax, indexLowToRemove, indexHighToRemove, hull); + } + } + } + } +} + +void KisConvexHullAlgorithm::buildQ2Hull(QPolygonF &points, ConvexHull &hull) +{ + + Q_FOREACH(const QPointF &point, points) { + // The point is inside this quadrant + + if (point.x() < hull.rootPoint.x() && point.y() > hull.rootPoint.y()) { + int indexLow = 0; + int indexMax = hull.points.count() - 1; + int indexHigh = indexMax; + bool validPoint = true; + + // We have have atleast 1 point between low and high + while (indexLow != (indexHigh - 1)) { + int index = ((indexHigh - indexLow) >> 1) + indexLow; + + if (validPoint = isConvexToQ2Point(point, hull.points[index])) { + + if (point.x() > hull.points[index].x) { + indexHigh = index; + continue; + } + + if (point.x() < hull.points[index].x) { + indexLow = index; + continue; + } + + if (point.x() == hull.points[index].x) { + indexHigh = index; + indexLow = index + 1; + } + } + + break; + } + + if (validPoint) { + + HullPoint &nextPoint = hull.points[indexHigh]; + + // Quick elimination without checking the slope + if (point.y() <= nextPoint.y) { + continue; + } + + HullPoint &previousPoint = hull.points[indexLow]; + qreal slopeToNext = slope(point.x(), point.y(), nextPoint.x, nextPoint.y); + + if (slopeToNext > previousPoint.slopeToNext) { + int indexLowToRemove = indexHigh; + int indexHighToRemove = indexLow; + + if (hull.points[indexLow].y < point.y()) { // We can remove 1 or more points without slope calc + indexLowToRemove = indexLow; + while (hull.points[indexLowToRemove - 1].y < point.y()) { + --indexLowToRemove; + } + } + + addPointToHull(point, slopeToNext, indexLow, indexHigh, indexMax, indexLowToRemove, indexHighToRemove, hull); + } + } + } + } +} + +void KisConvexHullAlgorithm::buildQ3Hull(QPolygonF &points, ConvexHull &hull) +{ + + Q_FOREACH(const QPointF &point, points) { + // The point is inside this quadrant + if (point.x() < hull.rootPoint.x() && point.y() < hull.rootPoint.y()) { + int indexLow = 0; + int indexMax = hull.points.count() - 1; + int indexHigh = indexMax; + bool validPoint = true; + + // We have have atleast 1 point between low and high + while (indexLow != (indexHigh - 1)) { + int index = ((indexHigh - indexLow) >> 1) + indexLow; + + if (validPoint = isConvexToQ3Point(point, hull.points[index])) { + + if (point.x() > hull.points[index].x) { + indexLow = index; + continue; + } + + if (point.x() < hull.points[index].x) { + indexHigh = index; + continue; + } + + if (point.x() == hull.points[index].x) { + indexLow = index; + indexHigh = index + 1; + } + } + + break; + } + + if (validPoint) { + HullPoint &previousPoint = hull.points[indexLow]; + + // Quick elimination without checking the slope + if (point.y() >= previousPoint.y) { + continue; + } + + HullPoint &nextPoint = hull.points[indexHigh]; + qreal slopeToNext = slope(point.x(), point.y(), nextPoint.x, nextPoint.y); + + if (slopeToNext > previousPoint.slopeToNext) { + int indexLowToRemove = indexHigh; + int indexHighToRemove = indexLow; + + if (hull.points[indexHigh].y > point.y()) { // We can remove 1 or more points without slope calc + indexHighToRemove = indexHigh; + while (hull.points[indexHighToRemove + 1].y > point.y()) { + ++indexHighToRemove; + } + } + + addPointToHull(point, slopeToNext, indexLow, indexHigh, indexMax, indexLowToRemove, indexHighToRemove, hull); + } + } + } + } +} + +void KisConvexHullAlgorithm::buildQ4Hull(QPolygonF &points, ConvexHull &hull) +{ + + Q_FOREACH(const QPointF &point, points) { + // The point is inside this quadrant + if (point.x() > hull.rootPoint.x() && point.y() < hull.rootPoint.y()) { + int indexLow = 0; + int indexMax = hull.points.count() - 1; + int indexHigh = indexMax; + bool validPoint = true; + + // We have have atleast 1 point between low and high + while (indexLow != (indexHigh - 1)) { + int index = ((indexHigh - indexLow) >> 1) + indexLow; + + if (validPoint = isConvexToQ4Point(point, hull.points[index])) { + + if (point.x() > hull.points[index].x) { + indexLow = index; + continue; + } + + if (point.x() < hull.points[index].x) { + indexHigh = index; + continue; + } + + if (point.x() == hull.points[index].x) { + indexLow = index; + indexHigh = index + 1; + } + } + + break; + } + + if (validPoint) { + HullPoint &nextPoint = hull.points[indexHigh]; + + // Quick elimination without checking the slope + if (point.y() >= nextPoint.y) { + continue; + } + + HullPoint &previousPoint = hull.points[indexLow]; + qreal slopeToNext = slope(point.x(), point.y(), nextPoint.x, nextPoint.y); + + if (slopeToNext > previousPoint.slopeToNext) { + int indexLowToRemove = indexHigh; + int indexHighToRemove = indexLow; + + if (hull.points[indexLow].y > point.y()) { // We can remove 1 or more points without slope calc + indexLowToRemove = indexLow; + while (hull.points[indexLowToRemove - 1].y > point.y()) { + --indexLowToRemove; + } + } + + addPointToHull(point, slopeToNext, indexLow, indexHigh, indexMax, indexLowToRemove, indexHighToRemove, hull); + } + } + } + } +} + +void KisConvexHullAlgorithm::addPointToHull(const QPointF &point, qreal slopeToNext, int indexLow, int indexHigh, int indexMax, + int indexLowToRemove, int indexHighToRemove, ConvexHull &hull) +{ + while (indexHighToRemove + 1 < indexMax) { + qreal slopeToNewIndexHighToRemovePlus1 = slope(point.x(), point.y(), hull.points[indexHighToRemove + 1].x, + hull.points[indexHighToRemove + 1].y); + + qreal slopeToNewIndexHighToRemovePlus2 = slope(point.x(), point.y(), hull.points[indexHighToRemove + 2].x, + hull.points[indexHighToRemove + 2].y); + + if (slopeToNewIndexHighToRemovePlus2 > slopeToNewIndexHighToRemovePlus1) { + break; + } + + ++indexHighToRemove; + } + + while (indexLowToRemove - 1 > 0) { + qreal slopeToNewIndexLowToRemoveMinus1 = slope(point.x(), point.y(), hull.points[indexLowToRemove - 1].x, + hull.points[indexLowToRemove - 1].y); + + qreal slopeToNewIndexLowToRemoveMinus2 = slope(point.x(), point.y(), hull.points[indexLowToRemove - 2].x, + hull.points[indexLowToRemove - 2].y); + + if (slopeToNewIndexLowToRemoveMinus2 < slopeToNewIndexLowToRemoveMinus1) { + break; + } + + --indexLowToRemove; + } + + HullPoint newPoint; + if (indexHighToRemove == indexLow) { // No point to invalidate after, already calculated slope to next is still valid + newPoint.x = point.x(); + newPoint.y = point.y(); + newPoint.slopeToNext = slopeToNext; + } + else { + newPoint.x = point.x(); + newPoint.y = point.y(); + newPoint.slopeToNext = slope(point.x(), point.y(), hull.points[indexHighToRemove + 1].x, hull.points[indexHighToRemove + 1].y); + } + + if (indexHighToRemove >= indexLowToRemove) { // Any existing hull point become invalid ? + hull.points[indexLowToRemove] = newPoint; + + if (indexHighToRemove > indexLowToRemove) { + hull.points.remove(indexLowToRemove + 1, indexHighToRemove - indexLowToRemove); + } + } + else { + hull.points.insert(indexHigh, newPoint); + } + + hull.points[indexLowToRemove - 1].slopeToNext = slope(point.x(), point.y(), hull.points[indexLowToRemove - 1].x, + hull.points[indexLowToRemove - 1].y); +} + +qreal KisConvexHullAlgorithm::slope(const qreal &startX, const qreal &startY, const qreal &endX, const qreal &endY) +{ + return (endY - startY) / (endX - startX); +} + +bool KisConvexHullAlgorithm::isConvexToQ1Point(const QPointF &point, const HullPoint &reference) +{ + if (point.x() < reference.x && point.y() <= reference.y) { + return false; + } + else if(point.y() < reference.y && point.x() <= reference.x) { + return false; + } + + return true; +} + +bool KisConvexHullAlgorithm::isConvexToQ2Point(const QPointF &point, const HullPoint &reference) +{ + if (point.x() > reference.x && point.y() <= reference.y) { + return false; + } + else if(point.y() < reference.y && point.x() >= reference.x) { + return false; + } + + return true; +} + +bool KisConvexHullAlgorithm::isConvexToQ3Point(const QPointF &point, const HullPoint &reference) +{ + if (point.x() > reference.x && point.y() >= reference.y) { + return false; + } + else if(point.y() > reference.y && point.x() >= reference.x) { + return false; + } + + return true; +} + +bool KisConvexHullAlgorithm::isConvexToQ4Point(const QPointF &point, const HullPoint &reference) +{ + if (point.x() < reference.x && point.y() >= reference.y) { + return false; + } + else if(point.y() > reference.y && point.x() <= reference.x) { + return false; + } + + return true; +}