|
BWAPI
|
00001 // Copyright (c) 2002-2004 INRIA Sophia-Antipolis (France). 00002 // All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or 00005 // modify it under the terms of the GNU Lesser General Public License as 00006 // published by the Free Software Foundation; version 2.1 of the License. 00007 // See the file LICENSE.LGPL distributed with CGAL. 00008 // 00009 // Licensees holding a valid commercial license may use this file in 00010 // accordance with the commercial license agreement provided with the software. 00011 // 00012 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00013 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00014 // 00015 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Intersections_2/include/CGAL/Triangle_2_Iso_rectangle_2_intersection.h $ 00016 // $Id: Triangle_2_Iso_rectangle_2_intersection.h 41387 2008-01-01 16:50:33Z spion $ 00017 // 00018 // 00019 // Author(s) : Radu Ursu 00020 00021 #ifndef CGAL_TRIANGLE_2_ISO_RECTANGLE_2_INTERSECTION_H 00022 #define CGAL_TRIANGLE_2_ISO_RECTANGLE_2_INTERSECTION_H 00023 00024 #include "CGAL/Point_2.h" 00025 #include "CGAL/Segment_2.h" 00026 #include "CGAL/Triangle_2.h" 00027 #include "CGAL/Iso_rectangle_2.h" 00028 #include "CGAL/Segment_2_Segment_2_intersection.h" 00029 00030 #include <vector> 00031 #include <list> 00032 00033 namespace CGAL{ 00034 template <class R> 00035 Object 00036 intersection(const Triangle_2<R> &t, const Iso_rectangle_2<R> &r) 00037 { 00038 typedef typename R::FT FT; 00039 typedef Segment_2<R> Segment; 00040 typedef Point_2<R> Point; 00041 00042 FT xr1, yr1, xr2, yr2; 00043 bool position[3][4] = {{0, 0, 0, 0}, {0, 0, 0, 0}, {0, 0, 0, 0}}; 00044 bool is_inside[3] = {false, false, false}; //true when a vertex is inside rectangle 00045 00046 xr1 = r.xmin(); xr2 = r.xmax(); 00047 yr1 = r.ymax(); yr2 = r.ymin(); 00048 00049 Point upper_left, lower_right; 00050 Point p[3]; //the vertices of triangle 00051 00052 upper_left = Point(xr1, yr1); //upper left 00053 lower_right = Point(xr2, yr2); //lower right 00054 00055 p[0] = t.vertex(0); 00056 p[1] = t.vertex(1); 00057 p[2] = t.vertex(2); 00058 00059 //check the points of the triangle 00060 for(int i=0; i<3; i++){ 00061 if(!(compare_x(p[i], upper_left) == SMALLER)) 00062 if(!(compare_x(p[i], lower_right) == LARGER)) 00063 if(!(compare_y(p[i], upper_left) == LARGER)) 00064 if(!(compare_y(p[i], lower_right) == SMALLER)) 00065 is_inside[i] = true; //the point is inside 00066 else 00067 position[i][2] = true; //South 00068 else 00069 position[i][0] = true; //North 00070 else 00071 { 00072 position[i][3] = true; //East 00073 if(compare_y(p[i], upper_left) == LARGER) 00074 position[i][0] = true; //North 00075 else if(compare_y(p[i], lower_right) == SMALLER) 00076 position[i][2] = true; //South 00077 } 00078 else 00079 { 00080 position[i][1] = true; //West 00081 if(compare_y(p[i], upper_left) == LARGER) 00082 position[i][0] = true; //North 00083 else if(compare_y(p[i], lower_right) == SMALLER) 00084 position[i][2] = true; //South 00085 00086 } 00087 } 00088 00089 //test if the triangle is completely to the left, right, below or above the rectangle 00090 bool intersection = true; //true if it could be a intersection with the rectangle 00091 for(int j=0; j<4; j++) 00092 if(position[0][j] && position[1][j] && position[2][j] ){ 00093 intersection = false; 00094 break; 00095 } 00096 00097 if(intersection){ 00098 Segment s[4]; //the segments that identify the N, W, S, E 00099 bool outside = false; 00100 bool status_in_list[3] = {false, false, false}; //true if the triangle's points are in the result vector 00101 std::list<int> last_intersected; 00102 int last_intersected_segment = 5; //could be 0=N, 1=W, 2=S, 3=E 00103 last_intersected.push_back(5); 00104 int status_intersected[4] = {0, 0, 0, 0}; //the number of intersections for each segment 00105 CGAL::Object obj; 00106 std::vector<Point> result; //the vector containing the result vertices 00107 int next; //the index of the next vertex 00108 00109 s[0] = Segment(Point(xr2, yr1), Point(xr1, yr1)); //N 00110 s[1] = Segment(Point(xr1, yr1), Point(xr1, yr2)); //W 00111 s[2] = Segment(Point(xr1, yr2), Point(xr2, yr2)); //S 00112 s[3] = Segment(Point(xr2, yr2), Point(xr2, yr1)); //E 00113 00114 //assign to p[i] the vertices of the triangle in ccw order 00115 if(t.orientation() == CGAL::CLOCKWISE) 00116 { 00117 p[0] = t.vertex(2); 00118 p[2] = t.vertex(0); 00119 00120 is_inside[0] = is_inside[2] ^ is_inside[0]; 00121 is_inside[2] = is_inside[2] ^ is_inside[0]; 00122 is_inside[0] = is_inside[0] ^ is_inside[2]; 00123 00124 for(int i=0; i<4; i++){ 00125 position[0][i] = position[2][i] ^ position[0][i]; 00126 position[2][i] = position[2][i] ^ position[0][i]; 00127 position[0][i] = position[0][i] ^ position[2][i]; 00128 } 00129 } 00130 00131 for(int index=0; index<3; index++) //for each vertex 00132 { 00133 next=(index+1)%3; 00134 if(is_inside[index]){ // true if first is inside 00135 if(!status_in_list[index]){ //if is not yet in the list 00136 result.push_back(p[index]); 00137 status_in_list[index] = true; 00138 } 00139 if(is_inside[next]){ //true if second is inside 00140 //add the points in the vector 00141 if(!status_in_list[next]){ // if is not yet in the list 00142 result.push_back(p[next]); 00143 status_in_list[next] = true; 00144 } 00145 } else { //I'm going out, the second is outside 00146 for(int j=0; j<4; j++) // for all directions 00147 if(position[next][j]) // if it's a second point direction 00148 { 00149 //test for intersection 00150 obj = CGAL::intersection(Segment(p[index], p[next]), s[j]); 00151 if(const Point *p_obj = object_cast<Point>(&obj)) 00152 { 00153 //intersection found 00154 outside = true; 00155 result.push_back(*p_obj); //add the intersection point 00156 if(last_intersected.back()!=j) 00157 last_intersected.push_back(j); 00158 status_intersected[j]++; 00159 } 00160 } 00161 } 00162 } else { //the first point is outside 00163 for(int j=0; j<4; j++) // for all directions 00164 if(position[index][j]) //watch only the first point directions 00165 { 00166 //test for intersection 00167 obj = CGAL::intersection(Segment(p[index], p[next]), s[j]); 00168 if(const Point *p_obj = object_cast<Point>(&obj)) 00169 { 00170 //intersection found 00171 outside = false; 00172 last_intersected_segment = last_intersected.back(); 00173 if(last_intersected_segment != 5 && last_intersected_segment != j && status_intersected[j] == 0){ 00174 //add the target of each rectangle segment in the list 00175 if(last_intersected_segment < j) 00176 while(last_intersected_segment < j){ 00177 result.push_back(s[last_intersected_segment].target()); 00178 last_intersected_segment++; 00179 } 00180 else{ 00181 while(last_intersected_segment < 4){ 00182 result.push_back(s[last_intersected_segment].target()); 00183 last_intersected_segment++; 00184 } 00185 last_intersected_segment = 0; 00186 while(last_intersected_segment < j){ 00187 result.push_back(s[last_intersected_segment].target()); 00188 last_intersected_segment++; 00189 } 00190 } 00191 } 00192 result.push_back(*p_obj); //add the intersection point in the list 00193 if(last_intersected.back()!=j) 00194 last_intersected.push_back(j); 00195 status_intersected[j]++; 00196 if(!is_inside[next]){ //if the second point is not inside search a second intersection point 00197 for(j=0; j<4; j++) // for all directions 00198 if(position[next][j]) 00199 { 00200 //test for intersection 00201 obj = CGAL::intersection(Segment(p[index], p[next]), s[j]); 00202 if(const Point *p_obj = object_cast<Point>(&obj)) 00203 //found the second intersection 00204 { 00205 outside = true; 00206 result.push_back(*p_obj); 00207 if(last_intersected.back()!=j) 00208 last_intersected.push_back(j); 00209 status_intersected[j]++; 00210 } 00211 } 00212 }//end if the second point is not inside 00213 } 00214 } 00215 }//end else (the first point is outside) 00216 }//endfor 00217 if(outside){ 00218 std::list<int>::const_iterator it = last_intersected.begin(); 00219 while(*it == 5) 00220 it++; 00221 last_intersected_segment = *it; 00222 int j = last_intersected.back(); 00223 if(last_intersected_segment != 5 && last_intersected_segment != j){ 00224 //add the target of each rectangle segment in the list 00225 if(last_intersected_segment > j) 00226 while(last_intersected_segment > j){ 00227 result.push_back(s[j].target()); 00228 j++; 00229 } 00230 else{ 00231 while(j<4){ 00232 result.push_back(s[j].target()); 00233 j++; 00234 } 00235 j = 0; 00236 while(j<last_intersected_segment){ 00237 result.push_back(s[j].target()); 00238 j++; 00239 } 00240 } 00241 } 00242 }//end if(outside) 00243 00244 //test if were not intersections 00245 //between the triangle and the rectangle 00246 if(status_intersected[0] == 0 && status_intersected[1] == 0 && 00247 status_intersected[2] == 0 && status_intersected[3] == 0) 00248 { 00249 //should test if the rectangle is inside the triangle 00250 if(t.bounded_side(upper_left) == CGAL::ON_BOUNDED_SIDE){ 00251 for(int k=0; k<4; k++) 00252 result.push_back(s[k].source()); 00253 } 00254 } 00255 00256 switch(result.size()){ 00257 case 0: 00258 return Object(); 00259 case 1: 00260 return make_object(result[0]); 00261 case 2: 00262 return make_object(Segment(result[0], result[1])); 00263 case 3: 00264 return make_object(Triangle_2<R>(result[0], result[1], result[2])); 00265 default: 00266 return make_object(result); 00267 } 00268 00269 }//end if(intersection) 00270 return Object(); 00271 }//end intersection 00272 }//end namespace 00273 00274 #endif
1.7.6.1
