/usr/include/terralib/kernel/TeIntersector.h is in libterralib-dev 4.3.0+dfsg.2-10.
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 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 | /************************************************************************************
TerraLib - a library for developing GIS applications.
Copyright © 2001-2007 INPE and Tecgraf/PUC-Rio.
This code is part of the TerraLib library.
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.
You should have received a copy of the GNU Lesser General Public
License along with this library.
The authors reassure the license terms regarding the warranties.
They specifically disclaim any warranties, including, but not limited to,
the implied warranties of merchantability and fitness for a particular purpose.
The library provided hereunder is on an "as is" basis, and the authors have no
obligation to provide maintenance, support, updates, enhancements, or modifications.
In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
indirect, special, incidental, or consequential damages arising out of the use
of this library and its documentation.
*************************************************************************************/
/*! \file TeIntersector.h
\brief This file contains structures and definitions for line intersection algorithms.
\note These data structures and algorithms MUST BE USED ONLY BY TerraLib kernel and should NOT be used by anyone because
THIS IS FOR INTERNAL USE ONLY.
\author Gilberto Ribeiro de Queiroz <gribeiro@dpi.inpe.br>
*/
#ifndef __TERRALIB_INTERNAL_INTERSECTOR2_H
#define __TERRALIB_INTERNAL_INTERSECTOR2_H
//TerraLib's include
#include "TeCoord2D.h"
#include "TeRTree.h"
//STL's include
#include <vector>
using namespace std;
/*
* WARNING: These data structures and algorithms MUST BE USED ONLY BY TerraLib kernel and should NOT be used by anyone because
* the support and interfaces can be changed in future. THIS IS FOR INTERNAL USE ONLY.
*/
/*! \brief Contains structures and definitions needed by line intersection algorithms (FOR INTERNAL USE ONLY).
*/
namespace TeINTERSECTOR2
{
//! An epsilon value used to compare two real numbers
#define EPSILON_COMPARE 1.0e-15
/** @defgroup IntersectionAlgorithms Intersection Algorithms
* Intersection Algorithms and data structures, used internally.
* @{
*/
//! This struct is used to represent a point intersection between two segments on boundary of a TePolygon or TeLine2D.
struct TL_DLL TeBoundaryIP
{
vector<TeCoord2D> coords_; //!< Points of intersection ocurried along these two segments (red and blue).
unsigned int redSegNum_; //!< Red segment number.
unsigned int redPartNum_; //!< Line number in a polygon that a red segment belongs.
unsigned int redPolNum_; //!< Polygon number in a vector of polygons that a segment belongs.
unsigned int blueSegNum_; //!< Blue segment number.
unsigned int bluePartNum_; //!< Line number in a polygon that a blue segment belongs.
unsigned int bluePolNum_; //!< Polygon number in a vector of polygons that a segment belongs.
};
//! This is the type of intersection point list.
typedef vector<TeBoundaryIP> TeVectorBoundaryIP;
//! This struct represents an index to the right place of a segment in a TeLineSet, TeLine2D, TePolygon or TePolygonSet.
struct TL_DLL TeSegIdInPolygonSet
{
unsigned int polId_; //!< The polygon id, when used in a polygonset.
unsigned int lineId_; //!< The line id, when used in a lineset or in a polygon.
unsigned int segId_; //!< The segment id into a specified line.
};
//! This pair is used to index two segments that intersects.
typedef pair<TeSegIdInPolygonSet, TeSegIdInPolygonSet> TePairSegIdInPolygonSet;
//! This is the type used to index the segments in the boundary of a TeLine2D, TeLineSet, TePolygon or TePolygonSet.
typedef TeSAM::TeRTree<TeSegIdInPolygonSet, 8> TeSegmentRTree;
/** \brief Tells if three points makes a right turn, a left turn or are collinear.
\param c1 The first coordinate.
\param c2 The second coordinate.
\param c3 The coordinate to test the relative position.
\param between Tells if c3 is between c1 and c2.
\return The orientation: TeCLOCKWISE, TeCOUNTERCLOCKWISE or TeNOTURN.
*/
TL_DLL short TeCCW(const TeCoord2D& c1, const TeCoord2D& c2, const TeCoord2D& c3, bool& between);
/** \brief Returns the intersection point of the segments.
\param a The first coordinate of the first segment.
\param b The second coordinate of the first segment.
\param c The first coordinate of the second segment.
\param d The second coordinate of the second segment.
\param ips The intersection coordinates (0, 1 or 2).
\param intersectionType An intersection may be proper or improper.
\return Returns true if there is an intersection between segments defined by end coordinates.
*/
TL_DLL bool TeIntersection(const TeCoord2D& a, const TeCoord2D& b, const TeCoord2D& c, const TeCoord2D& d, TeBoundaryIP& ips, TeSegmentIntersectionType& intersectionType);
/** \brief Tells if two segments intersects.
\param a The first coordinate of the first segment.
\param b The second coordinate of the first segment.
\param c The first coordinate of the second segment.
\param d The second coordinate of the second segment.
\param intersectionType An intersection may be proper or improper.
\return Returns true if there is an intersection between segments defined by end coordinates.
*/
TL_DLL bool TeIntersects(const TeCoord2D& a, const TeCoord2D& b, const TeCoord2D& c, const TeCoord2D& d, TeSegmentIntersectionType& intersectionType);
/** \brief Verifies if there is an intersection between two given polygonsets.
\param redPols The first polygonset to test.
\param bluePols The second polygonset to test.
\param report A list with the intersection points.
\return Returns true if there is an intersection between segments of the polygons.
\note WARNING: this is deprecated and will be replaced by another function in near future.
This is a lazy algorithm. It can be used, for example, in intersections between a box and a line.
It is O(n*m) - where n and m are the numbers of segments in the first and second polygonsets.
*/
TL_DLL bool TeSafeIntersections(const TePolygonSet& redPols, const TePolygonSet& bluePols, TeVectorBoundaryIP& report);
/** \brief Verifies if there is an intersection between two given lines.
\param redLine The first line to test.
\param blueLine The second line to test.
\param report A list with the intersection points.
\param redObjId Red line object id.
\param blueObjId Blue line object id.
\return Returns true if there is an intersection between segments of the lines.
\note WARNING: this is deprecated and will be replaced by another function in near future.
This is a lazy algorithm. It can be used, for example, in intersections between a box and a line.
It is O(n*m) - where n and m are the numbers of segments in the first and second lines.
*/
TL_DLL bool TeSafeIntersections(const TeLine2D& redLine, const TeLine2D& blueLine, TeVectorBoundaryIP& report, const unsigned int& redObjId = 0, const unsigned int& blueObjId = 0);
/** \brief Returns true if the lines intersects.
\param redLine The line to test.
\param blueLine The line to test.
\return Returns true if there is an intersection between segments of the lines.
\note WARNING: this is deprecated and will be replaced by another function in near future.
*/
TL_DLL bool TeIntersects(const TeLine2D& redLine, const TeLine2D& blueLine);
/** \brief Reports intersections between segments of polygons in the polygonset list.
\param polygons A list of polygons to test self intersections.
\param tree The tree with all index segments, it WILL BE filled inside this method.
\param report A report list of intersection points.
\return Returns true if there is an intersection.
\note This function will not returns intersections between segments of the same polygon. It will only
report intersection between different polygons. The index tree MUST BE EMPTY, othewise, the
result is undefined. The result may have duplicated points because intersections are reported
twice: this will turn fragmentation easier.
*/
TL_DLL bool TeIntersection(const TePolygonSet& polygons, TeSegmentRTree& tree, TeVectorBoundaryIP& report);
/** \brief Reports intersections between segments of two diferent polygonsets.
\param redPolygons A list of polygons without self intersections.
\param redTree A tree with all red segment already indexed or not, if it is empty, so, it will be filled inside this method.
\param bluePolygons A list of polygons without self intersections.
\param report A report list of intersection points.
\return Returns true if there is an intersection between a red segment and a blue segment.
\note This function will not returns intersections between segments of the same polygon. It will only
report intersection between different polygons. The result may have duplicated points because intersections are reported
twice: this will turn fragmentation easier.
*/
TL_DLL bool TeIntersection(const TePolygonSet& redPolygons, TeSegmentRTree& redTree, const TePolygonSet& bluePolygons, TeINTERSECTOR2::TeVectorBoundaryIP& report);
/** \brief Reports intersections between segments of a lineset and a polygonset.
\param redLines A list of lines without self intersections.
\param bluePolygons A list of polygons without self intersections.
\param blueTree A tree with all segments from the polygonset already indexed or not, if it is empty, so, it will be filled inside this method.
\param report A report list of intersection points.
\return Returns true if there is an intersection between a red segment from the lineset and a blue segment from the polygonset.
\note This function will not returns intersections between segments of the same polygon or lineset. It will only
report intersection between segments from different sets.
*/
TL_DLL bool TeIntersection(const TeLineSet& redLines, const TePolygonSet& bluePolygons, TeSegmentRTree& blueTree, TeINTERSECTOR2::TeVectorBoundaryIP& report);
/** \brief Tells if there is a self-intersection between segments.
\param polygons A list of polygons to test self intersections.
\param selfIntersectionList A report list with all self-intersections.
\return Returns true if there is not a self-intersection.
*/
TL_DLL bool TeIsSimple(const TePolygonSet& polygons, vector<TePairSegIdInPolygonSet>& selfIntersectionList);
/** \brief Index polygon's segments.
\param polygons A list of polygons to index it segment's.
\param tree The tree if indexed segments.
*/
TL_DLL void TeIndexPolygonSet(const TePolygonSet& polygons, TeSegmentRTree& tree);
/** @} */
} // end namespace TeINTERSECTOR2
#endif //__TERRALIB_INTERNAL_INTERSECTOR2_H
|