diff options
author | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 16:29:01 +0000 |
---|---|---|
committer | Daniel Baumann <daniel.baumann@progress-linux.org> | 2024-04-27 16:29:01 +0000 |
commit | 35a96bde514a8897f6f0fcc41c5833bf63df2e2a (patch) | |
tree | 657d15a03cc46bd099fc2c6546a7a4ad43815d9f /src/3rdparty/adaptagrams/libavoid/vertices.h | |
parent | Initial commit. (diff) | |
download | inkscape-upstream.tar.xz inkscape-upstream.zip |
Adding upstream version 1.0.2.upstream/1.0.2upstream
Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
Diffstat (limited to '')
-rw-r--r-- | src/3rdparty/adaptagrams/libavoid/vertices.h | 226 |
1 files changed, 226 insertions, 0 deletions
diff --git a/src/3rdparty/adaptagrams/libavoid/vertices.h b/src/3rdparty/adaptagrams/libavoid/vertices.h new file mode 100644 index 0000000..aac43bb --- /dev/null +++ b/src/3rdparty/adaptagrams/libavoid/vertices.h @@ -0,0 +1,226 @@ +/* + * vim: ts=4 sw=4 et tw=0 wm=0 + * + * libavoid - Fast, Incremental, Object-avoiding Line Router + * + * Copyright (C) 2004-2013 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_VERTICES_H +#define AVOID_VERTICES_H + +#include <list> +#include <set> +#include <map> +#include <iostream> +#include <cstdio> +#include <utility> + +#include "libavoid/geomtypes.h" + +namespace Avoid { + +class EdgeInf; +class VertInf; +class Router; + +typedef std::list<EdgeInf *> EdgeInfList; +typedef std::pair<VertInf *, VertInf *> VertexPair; + +typedef unsigned int ConnDirFlags; +typedef unsigned short VertIDProps; + + +class VertID +{ + public: + unsigned int objID; + unsigned short vn; + // Properties: + VertIDProps props; + + static const unsigned short src; + static const unsigned short tar; + + static const VertIDProps PROP_ConnPoint; + static const VertIDProps PROP_OrthShapeEdge; + static const VertIDProps PROP_ConnectionPin; + static const VertIDProps PROP_ConnCheckpoint; + static const VertIDProps PROP_DummyPinHelper; + + VertID(); + VertID(unsigned int id, unsigned short n, VertIDProps p = 0); + VertID(const VertID& other); + VertID& operator= (const VertID& rhs); + bool operator==(const VertID& rhs) const; + bool operator!=(const VertID& rhs) const; + bool operator<(const VertID& rhs) const; + VertID operator+(const int& rhs) const; + VertID operator-(const int& rhs) const; + VertID& operator++(int); + void print(FILE *file = stdout) const; + void db_print(void) const; + friend std::ostream& operator<<(std::ostream& os, const VertID& vID); + + // Property tests: + inline bool isOrthShapeEdge(void) const + { + return (props & PROP_OrthShapeEdge) ? true : false; + } + inline bool isConnPt(void) const + { + return (props & PROP_ConnPoint) ? true : false; + } + inline bool isConnectionPin(void) const + { + return (props & PROP_ConnectionPin) ? true : false; + } + inline bool isConnCheckpoint(void) const + { + return (props & PROP_ConnCheckpoint) ? true : false; + } + inline bool isDummyPinHelper(void) const + { + return (props & PROP_DummyPinHelper) ? true : false; + } +}; + + +// An ID given to all dummy vertices inserted to allow creation of the +// orthogonal visibility graph since the vertices in the orthogonal graph +// mostly do not correspond to shape corners or connector endpoints. +// +static const VertID dummyOrthogID(0, 0); +static const VertID dummyOrthogShapeID(0, 0, VertID::PROP_OrthShapeEdge); + +class ANode; + +class VertInf +{ + public: + VertInf(Router *router, const VertID& vid, const Point& vpoint, + const bool addToRouter = true); + ~VertInf(); + void Reset(const VertID& vid, const Point& vpoint); + void Reset(const Point& vpoint); + void removeFromGraph(const bool isConnVert = true); + bool orphaned(void); + + unsigned int pathLeadsBackTo(const VertInf *start) const; + void setVisibleDirections(const ConnDirFlags directions); + ConnDirFlags directionFrom(const VertInf *other) const; + // Checks if this vertex has the target as a visibility neighbour. + EdgeInf *hasNeighbour(VertInf *target, bool orthogonal) const; + void orphan(void); + + VertInf **makeTreeRootPointer(VertInf *root); + VertInf *treeRoot(void) const; + VertInf **treeRootPointer(void) const; + void setTreeRootPointer(VertInf **pointer); + void clearTreeRootPointer(void); + + void setSPTFRoot(VertInf *root); + VertInf *sptfRoot(void) const; + + Router *_router; + VertID id; + Point point; + VertInf *lstPrev; + VertInf *lstNext; + VertInf *shPrev; + VertInf *shNext; + EdgeInfList visList; + unsigned int visListSize; + EdgeInfList orthogVisList; + unsigned int orthogVisListSize; + EdgeInfList invisList; + unsigned int invisListSize; + VertInf *pathNext; + + // The tree root and distance value used when computing MTSTs. + // XXX: Maybe these should be allocated as a separate struct + // and referenced via a pointer. This would be slower due + // to memory allocation, but would save 2 x 8 = 24 bytes per + // VertInf on 64-bit machines. + VertInf *m_orthogonalPartner; + VertInf **m_treeRoot; + double sptfDist; + + ConnDirFlags visDirections; + std::list<ANode *> aStarDoneNodes; + std::list<ANode *> aStarPendingNodes; + // Flags for orthogonal visibility properties, i.e., whether the + // line points to a shape edge, connection point or an obstacle. + unsigned int orthogVisPropFlags; +}; + + +// Orthogonal visibility property flags +static const unsigned int XL_EDGE = 1; +static const unsigned int XL_CONN = 2; +static const unsigned int XH_EDGE = 4; +static const unsigned int XH_CONN = 8; +static const unsigned int YL_EDGE = 16; +static const unsigned int YL_CONN = 32; +static const unsigned int YH_EDGE = 64; +static const unsigned int YH_CONN = 128; + + +bool directVis(VertInf *src, VertInf *dst); + + +// A linked list of all the vertices in the router instance. All the +// connector endpoints are listed first, then all the shape vertices. +// Dummy vertices inserted for orthogonal routing are classed as shape +// vertices but have VertID(0, 0). +// +class VertInfList +{ + public: + VertInfList(); + void addVertex(VertInf *vert); + VertInf *removeVertex(VertInf *vert); + VertInf *getVertexByID(const VertID& id); + VertInf *getVertexByPos(const Point& p); + VertInf *shapesBegin(void); + VertInf *connsBegin(void); + VertInf *end(void); + unsigned int connsSize(void) const; + unsigned int shapesSize(void) const; + private: + VertInf *_firstShapeVert; + VertInf *_firstConnVert; + VertInf *_lastShapeVert; + VertInf *_lastConnVert; + unsigned int _shapeVertices; + unsigned int _connVertices; +}; + + +typedef std::set<unsigned int> ShapeSet; +typedef std::map<VertID, ShapeSet> ContainsMap; + + +} + + +#endif + + |