00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033 #ifndef _ORIENTCURVES_H
00034 #define _ORIENTCURVES_H
00035
00036 namespace Go
00037 {
00040
00041
00042
00065 template <class PtrToCurveType>
00066 inline void orientCurves(const std::vector<PtrToCurveType>& curves,
00067 std::vector<int>& permutation,
00068 std::vector<bool>& reversed,
00069 double neighbour_tol,
00070 bool assume_manifold = true)
00071
00072 {
00073
00074 int i, num_seg = curves.size();
00075 std::vector<Point> endpoints(2 * num_seg);
00076 for (i = 0; i < num_seg; ++i) {
00077 curves[i]->point(endpoints[2 * i + 0], curves[i]->startparam());
00078 curves[i]->point(endpoints[2 * i + 1], curves[i]->endparam());
00079 }
00080
00081
00082 std::vector<int> connected_to(2 * num_seg, -1);
00083 for (i = 0; i < 2 * num_seg; ++i) {
00084 if (connected_to[i] == -1 || !assume_manifold) {
00085 Point& p1 = endpoints[i];
00086 bool found = (connected_to[i] != -1);
00087
00088 for (int j = i+1; j < 2 * num_seg; ++j) {
00089 if (connected_to[j] == -1) {
00090 if (p1.dist(endpoints[j]) < neighbour_tol) {
00091
00092 connected_to[i] = j;
00093 connected_to[j] = i;
00094 if (assume_manifold) {
00095 break;
00096 } else if (found == true) {
00097 THROW("Multiple connected points detected in "
00098 " orientCurves(). Not a 1-manifold!" );
00099 } else {
00100 found = true;
00101 }
00102 }
00103 }
00104 }
00105 }
00106 }
00107
00108
00109 permutation.clear();
00110 permutation.reserve(num_seg);
00111 reversed.clear();
00112 reversed.reserve(num_seg);
00113 std::vector<bool> visited(2*num_seg, false);
00114
00115 for (i = 0; i < 2*num_seg; ++i) {
00116 if (!visited[i] && connected_to[i] == -1) {
00117 int current = i;
00118 do {
00119 permutation.push_back(current/2);
00120 bool current_parity = (current%2 == 0);
00121 int partner = current_parity ? current + 1 : current - 1;
00122 reversed.push_back(!current_parity);
00123 visited[current] = true;
00124 visited[partner] = true;
00125 current = connected_to[partner];
00126 } while (current != -1);
00127 }
00128 }
00129
00130 for (i = 0; i < 2*num_seg; ++i) {
00131 if (!visited[i]) {
00132 int current = i;
00133 do {
00134 permutation.push_back(current/2);
00135 bool current_parity = (current%2 == 0);
00136 int partner = current_parity ? current + 1 : current - 1;
00137 reversed.push_back(!current_parity);
00138 visited[current] = true;
00139 visited[partner] = true;
00140 current = connected_to[partner];
00141 } while (current != i);
00142 }
00143 }
00144 }
00145
00146
00148 }
00149
00150 #endif // _ORIENTCURVES_H
00151
00152