From cca66b9ec4e494c1d919bff0f71a820d8afab1fa Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 20:24:48 +0200 Subject: Adding upstream version 1.2.2. Signed-off-by: Daniel Baumann --- .../adaptagrams/libavoid/hyperedgeimprover.h | 159 +++++++++++++++++++++ 1 file changed, 159 insertions(+) create mode 100644 src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.h (limited to 'src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.h') diff --git a/src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.h b/src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.h new file mode 100644 index 0000000..958c877 --- /dev/null +++ b/src/3rdparty/adaptagrams/libavoid/hyperedgeimprover.h @@ -0,0 +1,159 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * + * Copyright (C) 2011-2014 Monash University + * + * 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. + * See the file LICENSE.LGPL distributed with the library. + * + * Licensees holding a valid commercial license may use this file in + * accordance with the commercial license agreement provided with the + * library. + * + * 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. + * + * Author(s): Michael Wybrow +*/ + +#ifndef AVOID_IMPROVEHYPEREDGES_H +#define AVOID_IMPROVEHYPEREDGES_H + +#include +#include +#include + + +namespace Avoid { + +struct HyperedgeTreeNode; +struct HyperedgeTreeEdge; +class HyperedgeShiftSegment; +class ConnRef; +class JunctionRef; +class ShiftSegment; +class VertInf; + +typedef std::list ShiftSegmentList; +typedef std::map RootSegmentsMap; +typedef std::map + JunctionHyperedgeTreeNodeMap; +typedef std::set JunctionSet; +typedef std::list ConnRefList; +typedef std::list JunctionRefList; + +class HyperedgeImprover +{ +public: + // Constructor. + HyperedgeImprover(); + + void clear(void); + + // Set the router that this HyperedgeImprover will act upon. + void setRouter(Router *router); + + // Returns lists of junctions and connectors created and deleted during + // hyperedge improvement. + HyperedgeNewAndDeletedObjectLists newAndDeletedObjectLists(void) const; + + // Execute local improvement process. + void execute(bool canMakeMajorChanges); + +private: + // Helper method for buildHyperedgeSegments() for hyperedge tree nodes. + void createShiftSegmentsForDimensionExcluding(HyperedgeTreeNode *node, + const size_t dim, HyperedgeTreeEdge *ignore, + ShiftSegmentList& segments); + + // Helper method for buildHyperedgeSegments() for hyperedge tree edges. + void createShiftSegmentsForDimensionExcluding(HyperedgeTreeEdge *edge, + const size_t dim, HyperedgeTreeNode *ignore, + ShiftSegmentList& segments); + + // During creation and nudging of shift segments it is often necessary + // to merge collinear or overlapping segments. This method does the + // merging for these cases. Effectively merging is done by adding + // additional vertex pointers to the shift segment. + void mergeOverlappingSegments(ShiftSegmentList& segments); + + // Given a hyperedge tree and a dimension, this method creates shift + // segments for all edges in that orientation. These segments are the + // objects on which the local improvement nudging operates, and they + // in turn make changes back to the hyperedge tree. + void buildHyperedgeSegments(const size_t dim); + + // This method looks for and corrects situations where the middle section + // of a zigzag is optimised away by bringing the outside segments in line + // and leading to the middle segment being zero length. These zero length + // edges are removed. + void removeZeroLengthEdges(void); + + // This method looks for and correct situations where multiple overlapping + // edges lead to a junction and one or more of these segments could be + // removed by moving the junction (and thus divergence point) along the + // edge. + void moveJunctionsAlongCommonEdges(void); + + // Given a set of hyperedge shift segments in a particular dimension, + // with limits and balance values precomputed, this method shifts and + // merges segments to improve the overall cost (length + bend penalties) + // for the hyperedge. + void nudgeHyperedgeSegments(size_t dimension, unsigned int& versionNumber); + + // Write the paths from an improved hyperedgetree object back as routes + // to the component connectors that form the hyperedge. + void writeHyperedgeSegmentsBackToConnPaths(void); + + // Output the hyperedge tree to an SVG file, optionally highlighting + // a segment of interest (usually the segment being moved). + void outputHyperedgesToSVG(unsigned int pass, + HyperedgeShiftSegment *activeSegment = nullptr); + + // Given a junction, this method follows the attached connectors and + // junctions to determine a hyperedge and returns the set of vertices + // representing its endpoints. + void getEndpoints(JunctionRef *junction, JunctionRef *ignore, + std::set& endpoints); + + // This method moves the junction at the given node along any shared paths + // (so long as this action would not create any additional shared paths), + // while also removing and freeing merged edges and nodes in the process. + // It returns the new node where the junction is now located. + HyperedgeTreeNode *moveJunctionAlongCommonEdge(HyperedgeTreeNode *self, + bool& nodeMapHasChanged); + + // This method traverses the hyperedge tree removing zero length edges. + // + void removeZeroLengthEdges(HyperedgeTreeNode *self, + HyperedgeTreeEdge *ignored); + + // This method traverses the hyperedge tree removing zero length edges. + // + void removeZeroLengthEdges(HyperedgeTreeEdge *self, + HyperedgeTreeNode *ignored); + + Router *m_router; + JunctionHyperedgeTreeNodeMap m_hyperedge_tree_junctions; + JunctionSet m_hyperedge_tree_roots; + RootSegmentsMap m_root_shift_segments; + ShiftSegmentList m_all_shift_segments; + JunctionRefList m_new_junctions; + JunctionRefList m_deleted_junctions; + ConnRefList m_new_connectors; + ConnRefList m_deleted_connectors; + ConnRefList m_changed_connectors; + int m_debug_count; + bool m_can_make_major_changes; +}; + + +} +#endif + -- cgit v1.2.3