diff options
Diffstat (limited to 'src/object/algorithms')
-rw-r--r-- | src/object/algorithms/CMakeLists.txt | 16 | ||||
-rw-r--r-- | src/object/algorithms/bboxsort.h | 54 | ||||
-rw-r--r-- | src/object/algorithms/graphlayout.cpp | 216 | ||||
-rw-r--r-- | src/object/algorithms/graphlayout.h | 29 | ||||
-rw-r--r-- | src/object/algorithms/removeoverlap.cpp | 85 | ||||
-rw-r--r-- | src/object/algorithms/removeoverlap.h | 23 | ||||
-rw-r--r-- | src/object/algorithms/unclump.cpp | 397 | ||||
-rw-r--r-- | src/object/algorithms/unclump.h | 32 |
8 files changed, 852 insertions, 0 deletions
diff --git a/src/object/algorithms/CMakeLists.txt b/src/object/algorithms/CMakeLists.txt new file mode 100644 index 0000000..3101ab2 --- /dev/null +++ b/src/object/algorithms/CMakeLists.txt @@ -0,0 +1,16 @@ +# SPDX-License-Identifier: GPL-2.0-or-later + +set(object_algorithms_SRC + graphlayout.cpp + removeoverlap.cpp + unclump.cpp + + # ------- + # Headers + bboxsort.h + graphlayout.h + removeoverlap.h + unclump.h +) + +add_inkscape_source("${object_algorithms_SRC}") diff --git a/src/object/algorithms/bboxsort.h b/src/object/algorithms/bboxsort.h new file mode 100644 index 0000000..6d15c12 --- /dev/null +++ b/src/object/algorithms/bboxsort.h @@ -0,0 +1,54 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +#ifndef SEEN_BBOXSORT_H +#define SEEN_BBOXSORT_H + +/** @file + * @brief Simple helper class for sorting objects based on their bounding boxes. + */ +/* Authors: + * MenTaLguY + * Dmitry Kirsanov + * Krzysztof KosiĆski + * + * Copyright (C) 2007-2012 Authors + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ +/* + * Previously part of the Align and Distribute dialog. + */ + +class BBoxSort { + +public: + BBoxSort(SPItem *item, Geom::Rect const &bounds, Geom::Dim2 orientation, double begin, double end) + : item(item) + , bbox(bounds) + { + anchor = begin * bbox.min()[orientation] + end * bbox.max()[orientation]; + } + + BBoxSort(const BBoxSort &rhs) = default; // Should really be vector of pointers to avoid copying class when sorting. + ~BBoxSort() = default; + + double anchor = 0.0; + SPItem* item = nullptr; + Geom::Rect bbox; +}; + +static bool operator< (const BBoxSort &a, const BBoxSort &b) { + return a.anchor < b.anchor; +} + +#endif // SEEN_BBOXSORT_H + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4 : diff --git a/src/object/algorithms/graphlayout.cpp b/src/object/algorithms/graphlayout.cpp new file mode 100644 index 0000000..b31454f --- /dev/null +++ b/src/object/algorithms/graphlayout.cpp @@ -0,0 +1,216 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** + * @file + * Interface between Inkscape code (SPItem) and graphlayout functions. + */ +/* + * Authors: + * Tim Dwyer <Tim.Dwyer@infotech.monash.edu.au> + * Abhishek Sharma + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#include <algorithm> +#include <cstring> +#include <iostream> +#include <list> +#include <map> +#include <string> +#include <valarray> +#include <vector> + +#include <2geom/transforms.h> + +#include "conn-avoid-ref.h" +#include "desktop.h" +#include "graphlayout.h" +#include "inkscape.h" + +#include "3rdparty/adaptagrams/libavoid/router.h" + +#include "3rdparty/adaptagrams/libcola/cola.h" +#include "3rdparty/adaptagrams/libcola/connected_components.h" + +#include "object/sp-item-transform.h" +#include "object/sp-namedview.h" +#include "object/sp-path.h" +#include "style.h" + +using namespace cola; +using namespace vpsc; + +/** + * Returns true if item is a connector + */ +bool isConnector(SPItem const * const item) { + auto path = dynamic_cast<SPPath const *>(item); + return path && path->connEndPair.isAutoRoutingConn(); +} + +struct CheckProgress: TestConvergence { + CheckProgress(double d, unsigned i, std::list<SPItem*> & selected, Rectangles & rs, + std::map<std::string, unsigned> & nodelookup) + : TestConvergence(d, i) + , selected(selected) + , rs(rs) + , nodelookup(nodelookup) + {} + bool operator()(const double new_stress, std::valarray<double> & X, std::valarray<double> & Y) override { + /* This is where, if we wanted to animate the layout, we would need to update + * the positions of all objects and redraw the canvas and maybe sleep a bit + cout << "stress="<<new_stress<<endl; + cout << "x[0]="<<rs[0]->getMinX()<<endl; + for (std::list<SPItem *>::iterator it(selected.begin()); + it != selected.end(); + ++it) + { + SPItem *u=*it; + if(!isConnector(u)) { + Rectangle* r=rs[nodelookup[u->id]]; + Geom::Rect const item_box(sp_item_bbox_desktop(u)); + Geom::Point const curr(item_box.midpoint()); + Geom::Point const dest(r->getCentreX(),r->getCentreY()); + u->move_rel(Geom::Translate(dest - curr)); + } + } + */ + return TestConvergence::operator()(new_stress, X, Y); + } + std::list<SPItem*> & selected; + Rectangles & rs; + std::map<std::string, unsigned> & nodelookup; +}; + +/** + * Scans the items list and places those items that are + * not connectors in filtered + */ +void filterConnectors(std::vector<SPItem*> const & items, std::list<SPItem*> & filtered) { + for (SPItem * item: items) { + if (!isConnector(item)) { + filtered.push_back(item); + } + } +} + +/** + * Takes a list of inkscape items, extracts the graph defined by + * connectors between them, and uses graph layout techniques to find + * a nice layout + */ +void graphlayout(std::vector<SPItem*> const & items) { + if (items.empty()) return; + + std::list<SPItem*> selected; + filterConnectors(items, selected); + std::vector<SPItem*> connectors; + std::copy_if(items.begin(), items.end(), std::back_inserter(connectors), [](SPItem* item){return isConnector(item); }); + + if (selected.size() < 2) return; + + // add the connector spacing to the size of node bounding boxes + // so that connectors can always be routed between shapes + SPDesktop * desktop = SP_ACTIVE_DESKTOP; + double spacing = 0; + if (desktop) spacing = desktop->namedview->connector_spacing + 0.1; + + std::map<std::string, unsigned> nodelookup; + Rectangles rs; + std::vector<Edge> es; + for (SPItem * item: selected) { + Geom::OptRect const item_box = item->desktopVisualBounds(); + if (item_box) { + Geom::Point ll(item_box->min()); + Geom::Point ur(item_box->max()); + nodelookup[item->getId()] = rs.size(); + rs.push_back(new Rectangle(ll[0] - spacing, ur[0] + spacing, + ll[1] - spacing, ur[1] + spacing)); + } else { + // I'm not actually sure if it's possible for something with a + // NULL item-box to be attached to a connector in which case we + // should never get to here... but if such a null box can occur it's + // probably pretty safe to simply ignore + //fprintf(stderr, "NULL item_box found in graphlayout, ignoring!\n"); + } + } + + Inkscape::Preferences * prefs = Inkscape::Preferences::get(); + CompoundConstraints constraints; + double ideal_connector_length = prefs->getDouble("/tools/connector/length", 100.0); + double directed_edge_height_modifier = 1.0; + + bool directed = prefs->getBool("/tools/connector/directedlayout"); + bool avoid_overlaps = prefs->getBool("/tools/connector/avoidoverlaplayout"); + + for (SPItem* conn: connectors) { + SPPath* path = SP_PATH(conn); + std::array<SPItem*, 2> attachedItems; + path->connEndPair.getAttachedItems(attachedItems.data()); + if (attachedItems[0] == nullptr) continue; + if (attachedItems[1] == nullptr) continue; + std::map<std::string, unsigned>::iterator i_iter=nodelookup.find(attachedItems[0]->getId()); + if (i_iter == nodelookup.end()) continue; + unsigned rect_index_first = i_iter->second; + i_iter = nodelookup.find(attachedItems[1]->getId()); + if (i_iter == nodelookup.end()) continue; + unsigned rect_index_second = i_iter->second; + es.emplace_back(rect_index_first, rect_index_second); + + if (conn->style->marker_end.set) { + if (directed && strcmp(conn->style->marker_end.value(), "none")) { + constraints.push_back(new SeparationConstraint(YDIM, rect_index_first, rect_index_second, + ideal_connector_length * directed_edge_height_modifier)); + } + } + } + + EdgeLengths elengths(es.size(), 1); + std::vector<Component*> cs; + connectedComponents(rs, es, cs); + for (Component * c: cs) { + if (c->edges.size() < 2) continue; + CheckProgress test(0.0001, 100, selected, rs, nodelookup); + ConstrainedMajorizationLayout alg(c->rects, c->edges, nullptr, ideal_connector_length, elengths, &test); + if (avoid_overlaps) alg.setAvoidOverlaps(); + alg.setConstraints(&constraints); + alg.run(); + } + separateComponents(cs); + + for (SPItem * item: selected) { + if (!isConnector(item)) { + std::map<std::string, unsigned>::iterator i = nodelookup.find(item->getId()); + if (i != nodelookup.end()) { + Rectangle * r = rs[i->second]; + Geom::OptRect item_box = item->desktopVisualBounds(); + if (item_box) { + Geom::Point const curr(item_box->midpoint()); + Geom::Point const dest(r->getCentreX(),r->getCentreY()); + item->move_rel(Geom::Translate(dest - curr)); + } + } + } + } + for (CompoundConstraint * c: constraints) { + delete c; + } + for (Rectangle * r: rs) { + delete r; + } +} +// vim: set cindent +// vim: ts=4 sw=4 et tw=0 wm=0 + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : diff --git a/src/object/algorithms/graphlayout.h b/src/object/algorithms/graphlayout.h new file mode 100644 index 0000000..6c6b601 --- /dev/null +++ b/src/object/algorithms/graphlayout.h @@ -0,0 +1,29 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** + * @file + * graph layout functions. + */ +/* + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#ifndef SEEN_GRAPHLAYOUT_H +#define SEEN_GRAPHLAYOUT_H + +#include <list> +#include <vector> + +class SPItem; + +void graphlayout(std::vector<SPItem*> const &items); + +bool isConnector(SPItem const *const item); + +void filterConnectors(std::vector<SPItem*> const &items, std::list<SPItem *> &filtered); + +#endif // SEEN_GRAPHLAYOUT_H diff --git a/src/object/algorithms/removeoverlap.cpp b/src/object/algorithms/removeoverlap.cpp new file mode 100644 index 0000000..8b3064b --- /dev/null +++ b/src/object/algorithms/removeoverlap.cpp @@ -0,0 +1,85 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** \file + * Interface between Inkscape code (SPItem) and remove-overlaps function. + */ +/* + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * Abhishek Sharma + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#include <utility> + +#include <2geom/transforms.h> + +#include "removeoverlap.h" + +#include "libvpsc/rectangle.h" + +#include "object/sp-item.h" +#include "object/sp-item-transform.h" + + +using vpsc::Rectangle; + +namespace { + +struct Record { + SPItem * item; + Geom::Point midpoint; + Rectangle * vspc_rect; + + Record() : item(nullptr), vspc_rect(nullptr) {} + Record(SPItem * i, Geom::Point m, Rectangle * r) + : item(i), midpoint(m), vspc_rect(r) {} +}; + +} + +/** +* Takes a list of inkscape items and moves them as little as possible +* such that rectangular bounding boxes are separated by at least xGap +* horizontally and yGap vertically +*/ +void removeoverlap(std::vector<SPItem*> const & items, double const xGap, double const yGap) { + std::vector<SPItem*> selected = items; + std::vector<Record> records; + std::vector<Rectangle*> rs; + + Geom::Point const gap(xGap, yGap); + for (SPItem * item: selected) { + using Geom::X; using Geom::Y; + Geom::OptRect item_box(item->desktopVisualBounds()); + if (item_box) { + Geom::Point min(item_box->min() - .5 * gap); + Geom::Point max(item_box->max() + .5 * gap); + // A negative gap is allowed, but will lead to problems when the gap is larger than + // the bounding box (in either X or Y direction, or both); min will have become max + // now, which cannot be handled by Rectangle() which is called below. And how will + // removeRectangleOverlap handle such a case? + // That's why we will enforce some boundaries on min and max here: + if (max[X] < min[X]) { + min[X] = max[X] = (min[X] + max[X]) / 2.; + } + if (max[Y] < min[Y]) { + min[Y] = max[Y] = (min[Y] + max[Y]) / 2.; + } + Rectangle * vspc_rect = new Rectangle(min[X], max[X], min[Y], max[Y]); + records.emplace_back(item, item_box->midpoint(), vspc_rect); + rs.push_back(vspc_rect); + } + } + if (!rs.empty()) { + removeoverlaps(rs); + } + for (Record & rec: records) { + Geom::Point const curr = rec.midpoint; + Geom::Point const dest(rec.vspc_rect->getCentreX(), rec.vspc_rect->getCentreY()); + rec.item->move_rel(Geom::Translate(dest - curr)); + delete rec.vspc_rect; + } +} diff --git a/src/object/algorithms/removeoverlap.h b/src/object/algorithms/removeoverlap.h new file mode 100644 index 0000000..619b091 --- /dev/null +++ b/src/object/algorithms/removeoverlap.h @@ -0,0 +1,23 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** \file + * \brief Remove overlaps function + */ +/* + * Authors: + * Tim Dwyer <tgdwyer@gmail.com> + * + * Copyright (C) 2005 Authors + * + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#ifndef SEEN_REMOVEOVERLAP_H +#define SEEN_REMOVEOVERLAP_H + +#include <vector> + +class SPItem; + +void removeoverlap(std::vector<SPItem*> const &items, double xGap, double yGap); + +#endif // SEEN_REMOVEOVERLAP_H diff --git a/src/object/algorithms/unclump.cpp b/src/object/algorithms/unclump.cpp new file mode 100644 index 0000000..df59f88 --- /dev/null +++ b/src/object/algorithms/unclump.cpp @@ -0,0 +1,397 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** + * @file + * Unclumping objects. + */ +/* Authors: + * bulia byak + * Jon A. Cruz <jon@joncruz.org> + * Abhishek Sharma + * + * Copyright (C) 2005 Authors + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#include "unclump.h" + +#include <2geom/transforms.h> +#include <algorithm> +#include <map> + +#include "object/sp-item.h" + +class Unclump +{ +public: + double dist(SPItem *item1, SPItem *item2); + double average(SPItem *item, std::list<SPItem *> &others); + SPItem *closest(SPItem *item, std::list<SPItem *> &others); + SPItem *farthest(SPItem *item, std::list<SPItem *> &others); + std::vector<SPItem *> unclump_remove_behind(SPItem *item, SPItem *closest, std::list<SPItem *> &rest); + void push(SPItem *from, SPItem *what, double dist); + void pull(SPItem *to, SPItem *what, double dist); + +private: + Geom::Point unclump_center(SPItem *item); + Geom::Point unclump_wh(SPItem *item); + + // Taking bbox of an item is an expensive operation, and we need to do it many times, so here we + // cache the centers, widths, and heights of items + + std::map<const gchar *, Geom::Point> c_cache; + std::map<const gchar *, Geom::Point> wh_cache; +}; + +/** +Center of bbox of item +*/ +Geom::Point Unclump::unclump_center(SPItem *item) +{ + std::map<const gchar *, Geom::Point>::iterator i = c_cache.find(item->getId()); + if (i != c_cache.end()) { + return i->second; + } + + Geom::OptRect r = item->desktopVisualBounds(); + if (r) { + Geom::Point const c = r->midpoint(); + c_cache[item->getId()] = c; + return c; + } else { + // FIXME + return Geom::Point(0, 0); + } +} + +Geom::Point Unclump::unclump_wh(SPItem *item) +{ + Geom::Point wh; + std::map<const gchar *, Geom::Point>::iterator i = wh_cache.find(item->getId()); + if (i != wh_cache.end()) { + wh = i->second; + } else { + Geom::OptRect r = item->desktopVisualBounds(); + if (r) { + wh = r->dimensions(); + wh_cache[item->getId()] = wh; + } else { + wh = Geom::Point(0, 0); + } + } + + return wh; +} + +/** +Distance between "edges" of item1 and item2. An item is considered to be an ellipse inscribed into its w/h, +so its radius (distance from center to edge) depends on the w/h and the angle towards the other item. +May be negative if the edge of item1 is between the center and the edge of item2. +*/ +double Unclump::dist(SPItem *item1, SPItem *item2) +{ + Geom::Point c1 = unclump_center(item1); + Geom::Point c2 = unclump_center(item2); + + Geom::Point wh1 = unclump_wh(item1); + Geom::Point wh2 = unclump_wh(item2); + + // angle from each item's center to the other's, unsqueezed by its w/h, normalized to 0..pi/2 + double a1 = atan2((c2 - c1)[Geom::Y], (c2 - c1)[Geom::X] * wh1[Geom::Y] / wh1[Geom::X]); + a1 = fabs(a1); + if (a1 > M_PI / 2) + a1 = M_PI - a1; + + double a2 = atan2((c1 - c2)[Geom::Y], (c1 - c2)[Geom::X] * wh2[Geom::Y] / wh2[Geom::X]); + a2 = fabs(a2); + if (a2 > M_PI / 2) + a2 = M_PI - a2; + + // get the radius of each item for the given angle + double r1 = 0.5 * (wh1[Geom::X] + (wh1[Geom::Y] - wh1[Geom::X]) * (a1 / (M_PI / 2))); + double r2 = 0.5 * (wh2[Geom::X] + (wh2[Geom::Y] - wh2[Geom::X]) * (a2 / (M_PI / 2))); + + // dist between centers minus angle-adjusted radii + double dist_r = (Geom::L2(c2 - c1) - r1 - r2); + + double stretch1 = wh1[Geom::Y] / wh1[Geom::X]; + double stretch2 = wh2[Geom::Y] / wh2[Geom::X]; + + if ((stretch1 > 1.5 || stretch1 < 0.66) && (stretch2 > 1.5 || stretch2 < 0.66)) { + std::vector<double> dists; + dists.push_back(dist_r); + + // If both objects are not circle-like, find dists between four corners + std::vector<Geom::Point> c1_points(2); + { + double y_closest; + if (c2[Geom::Y] > c1[Geom::Y] + wh1[Geom::Y] / 2) { + y_closest = c1[Geom::Y] + wh1[Geom::Y] / 2; + } else if (c2[Geom::Y] < c1[Geom::Y] - wh1[Geom::Y] / 2) { + y_closest = c1[Geom::Y] - wh1[Geom::Y] / 2; + } else { + y_closest = c2[Geom::Y]; + } + c1_points[0] = Geom::Point(c1[Geom::X], y_closest); + double x_closest; + if (c2[Geom::X] > c1[Geom::X] + wh1[Geom::X] / 2) { + x_closest = c1[Geom::X] + wh1[Geom::X] / 2; + } else if (c2[Geom::X] < c1[Geom::X] - wh1[Geom::X] / 2) { + x_closest = c1[Geom::X] - wh1[Geom::X] / 2; + } else { + x_closest = c2[Geom::X]; + } + c1_points[1] = Geom::Point(x_closest, c1[Geom::Y]); + } + + std::vector<Geom::Point> c2_points(2); + { + double y_closest; + if (c1[Geom::Y] > c2[Geom::Y] + wh2[Geom::Y] / 2) { + y_closest = c2[Geom::Y] + wh2[Geom::Y] / 2; + } else if (c1[Geom::Y] < c2[Geom::Y] - wh2[Geom::Y] / 2) { + y_closest = c2[Geom::Y] - wh2[Geom::Y] / 2; + } else { + y_closest = c1[Geom::Y]; + } + c2_points[0] = Geom::Point(c2[Geom::X], y_closest); + double x_closest; + if (c1[Geom::X] > c2[Geom::X] + wh2[Geom::X] / 2) { + x_closest = c2[Geom::X] + wh2[Geom::X] / 2; + } else if (c1[Geom::X] < c2[Geom::X] - wh2[Geom::X] / 2) { + x_closest = c2[Geom::X] - wh2[Geom::X] / 2; + } else { + x_closest = c1[Geom::X]; + } + c2_points[1] = Geom::Point(x_closest, c2[Geom::Y]); + } + + for (int i = 0; i < 2; i++) { + for (int j = 0; j < 2; j++) { + dists.push_back(Geom::L2(c1_points[i] - c2_points[j])); + } + } + + // return the minimum of all dists + return *std::min_element(dists.begin(), dists.end()); + } else { + return dist_r; + } +} + +/** +Average dist from item to others +*/ +double Unclump::average(SPItem *item, std::list<SPItem *> &others) +{ + int n = 0; + double sum = 0; + for (SPItem *other : others) { + if (other == item) + continue; + + n++; + sum += dist(item, other); + } + + if (n != 0) + return sum / n; + else + return 0; +} + +/** +Closest to item among others + */ +SPItem *Unclump::closest(SPItem *item, std::list<SPItem *> &others) +{ + double min = HUGE_VAL; + SPItem *closest = nullptr; + + for (SPItem *other : others) { + if (other == item) + continue; + + double dist = this->dist(item, other); + if (dist < min && fabs(dist) < 1e6) { + min = dist; + closest = other; + } + } + + return closest; +} + +/** +Most distant from item among others + */ +SPItem *Unclump::farthest(SPItem *item, std::list<SPItem *> &others) +{ + double max = -HUGE_VAL; + SPItem *farthest = nullptr; + + for (SPItem *other : others) { + if (other == item) + continue; + + double dist = this->dist(item, other); + if (dist > max && fabs(dist) < 1e6) { + max = dist; + farthest = other; + } + } + + return farthest; +} + +/** +Removes from the \a rest list those items that are "behind" \a closest as seen from \a item, +i.e. those on the other side of the line through \a closest perpendicular to the direction from \a +item to \a closest. Returns a newly created list which must be freed. + */ +std::vector<SPItem *> Unclump::unclump_remove_behind(SPItem *item, SPItem *closest, std::list<SPItem *> &rest) +{ + Geom::Point it = unclump_center(item); + Geom::Point p1 = unclump_center(closest); + + // perpendicular through closest to the direction to item: + Geom::Point perp = Geom::rot90(it - p1); + Geom::Point p2 = p1 + perp; + + // get the standard Ax + By + C = 0 form for p1-p2: + double A = p1[Geom::Y] - p2[Geom::Y]; + double B = p2[Geom::X] - p1[Geom::X]; + double C = p2[Geom::Y] * p1[Geom::X] - p1[Geom::Y] * p2[Geom::X]; + + // substitute the item into it: + double val_item = A * it[Geom::X] + B * it[Geom::Y] + C; + + std::vector<SPItem *> out; + for (SPItem *other : rest) { + if (other == item) + continue; + + Geom::Point o = unclump_center(other); + double val_other = A * o[Geom::X] + B * o[Geom::Y] + C; + + if (val_item * val_other <= 1e-6) { + // different signs, which means item and other are on the different sides of p1-p2 line; skip + } else { + out.push_back(other); + } + } + + return out; +} + +/** +Moves \a what away from \a from by \a dist + */ +void Unclump::push(SPItem *from, SPItem *what, double dist) +{ + Geom::Point it = unclump_center(what); + Geom::Point p = unclump_center(from); + Geom::Point by = dist * Geom::unit_vector(-(p - it)); + + Geom::Affine move = Geom::Translate(by); + + std::map<const gchar *, Geom::Point>::iterator i = c_cache.find(what->getId()); + if (i != c_cache.end()) { + i->second *= move; + } + + // g_print ("push %s at %g,%g from %g,%g by %g,%g, dist %g\n", what->getId(), it[Geom::X],it[Geom::Y], + // p[Geom::X],p[Geom::Y], by[Geom::X],by[Geom::Y], dist); + + what->set_i2d_affine(what->i2dt_affine() * move); + what->doWriteTransform(what->transform); +} + +/** +Moves \a what towards \a to by \a dist + */ +void Unclump::pull(SPItem *to, SPItem *what, double dist) +{ + Geom::Point it = unclump_center(what); + Geom::Point p = unclump_center(to); + Geom::Point by = dist * Geom::unit_vector(p - it); + + Geom::Affine move = Geom::Translate(by); + + std::map<const gchar *, Geom::Point>::iterator i = c_cache.find(what->getId()); + if (i != c_cache.end()) { + i->second *= move; + } + + // g_print ("pull %s at %g,%g to %g,%g by %g,%g, dist %g\n", what->getId(), it[Geom::X],it[Geom::Y], + // p[Geom::X],p[Geom::Y], by[Geom::X],by[Geom::Y], dist); + + what->set_i2d_affine(what->i2dt_affine() * move); + what->doWriteTransform(what->transform); +} + +/** +Unclumps the items in \a items, reducing local unevenness in their distribution. Produces an effect +similar to "engraver dots". The only distribution which is unchanged by unclumping is a hexagonal +grid. May be called repeatedly for stronger effect. + */ +void unclump(std::vector<SPItem *> &items) +{ + Unclump unclump; + + for (SPItem *item : items) { // for each original/clone x: + std::list<SPItem *> nei; + + std::list<SPItem *> rest; + for (size_t i = 0; i < items.size(); i++) { + rest.push_front(items[items.size() - i - 1]); + } + rest.remove(item); + + while (!rest.empty()) { + SPItem *closest = unclump.closest(item, rest); + if (closest) { + nei.push_front(closest); + rest.remove(closest); + std::vector<SPItem *> new_rest = unclump.unclump_remove_behind(item, closest, rest); + rest.clear(); + for (size_t i = 0; i < new_rest.size(); i++) { + rest.push_front(new_rest[new_rest.size() - i - 1]); + } + } else { + break; + } + } + + if ((nei.size()) >= 2) { + double ave = unclump.average(item, nei); + + SPItem *closest = unclump.closest(item, nei); + SPItem *farthest = unclump.farthest(item, nei); + + double dist_closest = unclump.dist(closest, item); + double dist_farthest = unclump.dist(farthest, item); + + // g_print ("NEI %d for item %s closest %s at %g farthest %s at %g ave %g\n", g_slist_length(nei), + // item->getId(), closest->getId(), dist_closest, farthest->getId(), dist_farthest, ave); + + if (fabs(ave) < 1e6 && fabs(dist_closest) < 1e6 && fabs(dist_farthest) < 1e6) { // otherwise the items are + // bogus + // increase these coefficients to make unclumping more aggressive and less stable + // the pull coefficient is a bit bigger to counteract the long-term expansion trend + unclump.push(closest, item, 0.3 * (ave - dist_closest)); + unclump.pull(farthest, item, 0.35 * (dist_farthest - ave)); + } + } + } +} + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : diff --git a/src/object/algorithms/unclump.h b/src/object/algorithms/unclump.h new file mode 100644 index 0000000..313e12d --- /dev/null +++ b/src/object/algorithms/unclump.h @@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/** @file + * @brief Unclumping objects + */ +/* Authors: + * bulia byak + * + * Copyright (C) 2005 Authors + * Released under GNU GPL v2+, read the file 'COPYING' for more information. + */ + +#ifndef SEEN_DIALOGS_UNCLUMP_H +#define SEEN_DIALOGS_UNCLUMP_H + +#include <vector> + +class SPItem; + +void unclump(std::vector<SPItem *> &items); + +#endif /* !UNCLUMP_H_SEEN */ + +/* + Local Variables: + mode:c++ + c-file-style:"stroustrup" + c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +)) + indent-tabs-mode:nil + fill-column:99 + End: +*/ +// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 : |