//=========================================================================== // GoTools Core - SINTEF Geometry Tools Core library, version 2.0.1 // // Copyright (C) 2000-2007, 2010 SINTEF ICT, Applied Mathematics, Norway. // // 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 version 2 of the License. // // This program 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. See the // GNU General Public License for more details. // // You should have received a copy of the GNU General Public License // along with this program; if not, write to the Free Software // Foundation, Inc., // 59 Temple Place - Suite 330, // Boston, MA 02111-1307, USA. // // Contact information: E-mail: tor.dokken@sintef.no // SINTEF ICT, Department of Applied Mathematics, // P.O. Box 124 Blindern, // 0314 Oslo, Norway. // // Other licenses are also available for this software, notably licenses // for: // - Building commercial software. // - Building software whose source code you wish to keep private. //=========================================================================== 00013 #ifndef _ORIENTCURVES_H 00014 #define _ORIENTCURVES_H 00015 00016 namespace Go 00017 { 00018 00019 //=========================================================================== 00042 template <class PtrToCurveType> 00043 inline void orientCurves(const std::vector<PtrToCurveType>& curves, 00044 std::vector<int>& permutation, 00045 std::vector<bool>& reversed, 00046 double neighbour_tol, 00047 bool assume_manifold = true) 00048 //=========================================================================== 00049 { 00050 // registering all points 00051 int i, num_seg = curves.size(); 00052 std::vector<Point> endpoints(2 * num_seg); 00053 for (i = 0; i < num_seg; ++i) { 00054 curves[i]->point(endpoints[2 * i + 0], curves[i]->startparam()); 00055 curves[i]->point(endpoints[2 * i + 1], curves[i]->endparam()); 00056 } 00057 00058 // detecting connections 00059 std::vector<int> connected_to(2 * num_seg, -1); 00060 for (i = 0; i < 2 * num_seg; ++i) { 00061 if (connected_to[i] == -1 || !assume_manifold) { 00062 Point& p1 = endpoints[i]; 00063 bool found = (connected_to[i] != -1); 00064 // this point has not been checked for connections yet 00065 for (int j = i+1; j < 2 * num_seg; ++j) { 00066 if (connected_to[j] == -1) { 00067 if (p1.dist(endpoints[j]) < neighbour_tol) { 00068 // we consider these points to be connected 00069 connected_to[i] = j; 00070 connected_to[j] = i; 00071 if (assume_manifold) { 00072 break; 00073 } else if (found == true) { 00074 THROW("Multiple connected points detected in " 00075 " orientCurves(). Not a 1-manifold!" ); 00076 } else { 00077 found = true; 00078 } 00079 } 00080 } 00081 } 00082 } 00083 } 00084 00085 // Making the permutation std::vector 00086 permutation.clear(); 00087 permutation.reserve(num_seg); 00088 reversed.clear(); 00089 reversed.reserve(num_seg); 00090 std::vector<bool> visited(2*num_seg, false); 00091 // First handle all open chains 00092 for (i = 0; i < 2*num_seg; ++i) { 00093 if (!visited[i] && connected_to[i] == -1) { 00094 int current = i; 00095 do { 00096 permutation.push_back(current/2); 00097 bool current_parity = (current%2 == 0); 00098 int partner = current_parity ? current + 1 : current - 1; 00099 reversed.push_back(!current_parity); 00100 visited[current] = true; 00101 visited[partner] = true; 00102 current = connected_to[partner]; 00103 } while (current != -1); 00104 } 00105 } 00106 // Then all closed chains (loops) 00107 for (i = 0; i < 2*num_seg; ++i) { 00108 if (!visited[i]) { 00109 int current = i; 00110 do { 00111 permutation.push_back(current/2); 00112 bool current_parity = (current%2 == 0); 00113 int partner = current_parity ? current + 1 : current - 1; 00114 reversed.push_back(!current_parity); 00115 visited[current] = true; 00116 visited[partner] = true; 00117 current = connected_to[partner]; 00118 } while (current != i); 00119 } 00120 } 00121 } 00122 00123 00124 } // namespace Go 00125 00126 #endif // _ORIENTCURVES_H 00127