Don't import ogdf namespace
[TortoiseGit.git] / ext / OGDF / ogdf / graphalg / ConvexHull.h
blobf506167446ddabbc920508b3e515b60f9cc744b4
1 /*
2 * $Revision: 2523 $
4 * last checkin:
5 * $Author: gutwenger $
6 * $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
7 ***************************************************************/
9 /** \file
10 * \brief Declaration of doubly linked lists and iterators
12 * \author Gereon Bartel
14 * \par License:
15 * This file is part of the Open Graph Drawing Framework (OGDF).
17 * \par
18 * Copyright (C)<br>
19 * See README.txt in the root directory of the OGDF installation for details.
21 * \par
22 * This program is free software; you can redistribute it and/or
23 * modify it under the terms of the GNU General Public License
24 * Version 2 or 3 as published by the Free Software Foundation;
25 * see the file LICENSE.txt included in the packaging of this file
26 * for details.
28 * \par
29 * This program is distributed in the hope that it will be useful,
30 * but WITHOUT ANY WARRANTY; without even the implied warranty of
31 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
32 * GNU General Public License for more details.
34 * \par
35 * You should have received a copy of the GNU General Public
36 * License along with this program; if not, write to the Free
37 * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
38 * Boston, MA 02110-1301, USA.
40 * \see http://www.gnu.org/copyleft/gpl.html
41 ***************************************************************/
43 #ifdef _MSC_VER
44 #pragma once
45 #endif
47 #ifndef OGDF_CONVEX_HULL_H
48 #define OGDF_CONVEX_HULL_H
50 #include <ogdf/basic/GraphAttributes.h>
51 #include <ogdf/basic/geometry.h>
52 #include <ogdf/internal/energybased/MultilevelGraph.h>
53 #include <vector>
55 namespace ogdf {
57 // all returned Polygons are clockwise (cw)
58 class OGDF_EXPORT ConvexHull {
59 private:
60 bool sameDirection(const DPoint &start, const DPoint &end, const DPoint &s, const DPoint &e) const;
62 // calculates a convex hull very quickly but only works with cross-free Polygons!
63 DPolygon conv(const DPolygon &poly) const;
65 // Calculates the Part of the convex hull that is left of line start-end
66 // /a points should only contain points that really are left of the line.
67 void leftHull(std::vector<DPoint> points, DPoint &start, DPoint &end, DPolygon &hullPoly) const;
70 public:
71 ConvexHull();
72 ~ConvexHull();
74 DPoint calcNormal(const DPoint &start, const DPoint &end) const;
75 double leftOfLine(const DPoint &normal, const DPoint &point, const DPoint &pointOnLine) const;
77 DPolygon call(std::vector<DPoint> points) const;
78 DPolygon call(GraphAttributes &GA) const;
79 DPolygon call(MultilevelGraph &MLG) const;
83 } // namespace ogdf
85 #endif