/usr/include/tulip/ConvexHull.h is in libtulip-dev 3.1.2-2.3ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 | //-*-c++-*-
/**
Authors: David Auber, Patrick Mary, Morgan Mathiaut
from the LaBRI Visualization Team
Email : auber@tulip-software.org
Last modification : 13/03/2009
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
*/
#ifndef TLP_GEO_CONVEX_HULL_H
#define TLP_GEO_CONVEX_HULL_H
#include <vector>
#include <tulip/Coord.h>
namespace tlp {
/**
* \addtogroup basic
*/
/*@{*/
/**
* \brief function for convex hull manipulation
*
* Contains functions for computing, merging, intersecting, and
* testing convex hulls.
*
* \author : Daniel Archambault archam@cs.ubc.ca,
*
* \version 0.0.3 26/06/2006
*/
/**
* Compute the convex hull and return a list of indexes for the
* points on the convex hull in counterclockwise order. The convexHull
* vector is automatically cleared. The algorithm runs in O(nlgn) time.
*/
TLP_SCOPE void convexHull (const std::vector<Coord> &points,
std::vector<unsigned int> &convexHull);
/**
* Merges two convex hulls hull1 and hull2 using the rotating calipers
* method of Pirzadeh and Touissaint. The mergedConvexHull
* vector is automatically cleared and the vertices of the hulls must
* be specified in counter clockwise order. Provide a full list of all
* points involved in the convex hull computation in the vector points.
* The vectors hull1 and hull2 contain a list of indexes into the
* points vector that define the vertices of the convex hull. The
* indexes into points of the verticies on the merged convex hull are
* returned in the vector mergedConvexHull.
*/
TLP_SCOPE void mergeHulls (const std::vector<Coord> &points,
const std::vector<unsigned int> &hull1,
const std::vector<unsigned int> &hull2,
std::vector<unsigned int> &mergedConvexHull);
/**
* Intersects two convex hulls using the algorithm of
* O'Rourke, Chien, Olson, and Naddor, 1982. Code inspired
* by Computational Geometry in C by Joseph O'Rourke pp 243 -- 251.
* and code on his website:
* http://maven.smith.edu/~orourke/books/compgeom.html
* Provide a full list of points involved in the convex hull computation
* in "points". The vectors hull1 and hull2 contain a list of indexes
* into the points vector that define the vertices of the convex hull.
* The indices corresponding to the points on the intersecting hull
* are returned in "intersection". Node that several points may
* be inserted into the "points" list. These points correspond to the
* points generated when edges of hull1 and hull2 intersect.
*/
TLP_SCOPE void intersectHulls (std::vector<Coord> &points,
const std::vector<unsigned int> &hull1,
const std::vector<unsigned int> &hull2,
std::vector<unsigned int> &intersection);
/**
* Computes the area of the convex "hull" which is a list of indexes
* into the vector of Coord "points".
*/
TLP_SCOPE double areaOfHull (const std::vector<Coord> &points,
const std::vector<unsigned int> &hull);
/**
* Returns true if "point" is inside "hull". Hull is a list of
* indexes into the vector of Coord "points."
*/
TLP_SCOPE bool insideHull (const std::vector<Coord> &points,
const std::vector<unsigned int> &hull,
const Coord &point);
/*@}*/
}
#endif
|