Guest User

Untitled

a guest
Jul 23rd, 2018
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.32 KB | None | 0 0
  1. #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
  2. #include <CGAL/Delaunay_triangulation_2.h>
  3. #include <CGAL/Voronoi_diagram_2.h>
  4. #include <CGAL/Delaunay_triangulation_adaptation_traits_2.h>
  5. #include <CGAL/Delaunay_triangulation_adaptation_policies_2.h>
  6.  
  7.  
  8. #include <iostream>
  9.  
  10. typedef CGAL::Exact_predicates_exact_constructions_kernel K;
  11. typedef CGAL::Delaunay_triangulation_2<K> Delaunay;
  12. typedef CGAL::Delaunay_triangulation_adaptation_traits_2<Delaunay> AT;
  13. typedef CGAL::Delaunay_triangulation_degeneracy_removal_policy_2<Delaunay> AP;
  14. typedef CGAL::Voronoi_diagram_2<Delaunay,AT,AP> Voronoi;
  15. typedef Voronoi::Vertex_iterator Iterator;
  16. typedef K::Point_2 Point;
  17. typedef K::Segment_2 Segment;
  18. typedef K::Ray_2 Ray;
  19.  
  20. typedef Voronoi::Vertex_handle Vertex;
  21. typedef Voronoi::Vertex::Halfedge_around_vertex_circulator VCirc;
  22. typedef Voronoi::Face::Ccb_halfedge_circulator ECirc;
  23.  
  24. using namespace std;
  25.  
  26. #define SUCCESS "y"
  27. #define FAIL "n"
  28.  
  29. #define HAS(set, x) ((set)->find(x) != (set)->end())
  30.  
  31. bool is_route_r(Vertex pos, K::FT max_d, Voronoi* v, set<Vertex>* visited, vector<Point>* path){
  32.  
  33. //check current this vertex with the closest infected
  34. if(CGAL::squared_distance(pos->point(),v->dual().nearest_vertex(pos->point())->point()) < max_d)
  35. return false;
  36.  
  37. visited->insert(pos);
  38. VCirc crc = (pos)->incident_halfedges();
  39. do{
  40. if(HAS(visited, crc->source()))
  41. continue; // no point in going back to somewhere
  42.  
  43.  
  44. Segment s = v->dual().segment(crc->dual());
  45. //check if this edge can be taken.
  46. CGAL::Object o = v->dual().dual(crc->dual());
  47. if(const Ray* ray = CGAL::object_cast<Ray>(&o)){
  48. if(CGAL::squared_distance(*ray, s.source()) < max_d ){
  49. continue; // cannot use the edge
  50. }
  51. }else if(const Segment* seg = CGAL::object_cast<Segment>(&o)){
  52. if(CGAL::squared_distance(*seg, s.source()) < max_d){
  53. continue; // cannot use the edge
  54. }
  55. }
  56.  
  57. //check if its an edge we can use to escape!
  58. if(crc->is_unbounded())
  59. return true;
  60.  
  61. if(is_route_r(crc->source(), max_d, v, visited, path))
  62. return true;
  63.  
  64. }while(++crc != (pos)->incident_halfedges());
  65.  
  66. return false;
  67. }
  68.  
  69. bool is_route(Point p, K::FT max_d, Voronoi* v, vector<Point>* pathV){
  70.  
  71. K::FT distance = CGAL::squared_distance(p, v->dual().nearest_vertex(p)->point());
  72.  
  73. if(distance < max_d)
  74. return false;
  75.  
  76. set<Vertex> set;
  77. Voronoi::Locate_result l = v->locate(p);
  78. if (Vertex* vi = boost::get<Voronoi::Vertex_handle>(&l)) {
  79. return is_route_r((*vi), max_d, v, &set, pathV);
  80.  
  81. } else if (Voronoi::Halfedge_handle* h = boost::get<Voronoi::Halfedge_handle>(&l)) {
  82. bool success = false;
  83. //see if it is an unbounded edge and try to make a quick escape
  84. Segment s = v->dual().segment((*h)->dual());
  85.  
  86. if(!(*h)->has_source() || !(*h)->has_target()){
  87. //get the ray
  88. cout << (*h)->target()->point() << endl;
  89. CGAL::Object o = v->dual().dual((*h)->dual());
  90. const Ray* ray = CGAL::object_cast<Ray>(&o);
  91. Ray newRay = Ray(p, ray->direction());
  92.  
  93. if(CGAL::squared_distance(newRay, s.source()) >= max_d )
  94. return true;
  95. }
  96.  
  97. //see if traveling to the source is possible and try
  98. if((*h)->has_source()){
  99. Segment path(p, (*h)->source()->point());
  100. if(CGAL::squared_distance(path, s.source()) >= max_d )
  101. success = is_route_r((*h)->source(), max_d, v, &set, pathV);
  102. }
  103.  
  104. //see if travelling to the target is possible and try
  105. if((*h)->has_target()){
  106. Segment path(p, (*h)->target()->point());
  107. if(CGAL::squared_distance(path, s.source()) >= max_d )
  108. success = success || is_route_r((*h)->target(), max_d, v, &set, pathV);
  109. }
  110.  
  111. return success;
  112. } else if (Voronoi::Face_handle* f = boost::get<Voronoi::Face_handle>(&l)) {
  113. //lets move away orthogonaly from the dualPoint
  114.  
  115. Ray moveRay = Ray(p, p - (*f)->dual()->point());
  116.  
  117. //find the segment which intersects
  118. ECirc crc = (*f)->outer_ccb();
  119. do{
  120.  
  121. CGAL::Object edge = v->dual().dual(crc->dual());
  122.  
  123. if(const Ray* ray = CGAL::object_cast<Ray>(&edge)){
  124. if(do_intersect(moveRay, *ray)){
  125. CGAL::Object o = CGAL::intersection(moveRay,*ray);
  126. const Point* op = CGAL::object_cast<Point>(&o);
  127. if(op == 0)
  128. return true;
  129. else
  130. return is_route(*op, max_d, v, pathV);
  131. }
  132. }else if(const Segment* seg = CGAL::object_cast<Segment>(&edge)){
  133. if(do_intersect(moveRay, *seg)){
  134. CGAL::Object o = CGAL::intersection(moveRay,*seg);
  135. const Point* op = CGAL::object_cast<Point>(&o);
  136. if(op == 0)
  137. return true;
  138. else
  139. return is_route(*op, max_d, v,pathV);
  140. }
  141. }
  142.  
  143.  
  144. }while(++crc != (*f)->outer_ccb());
  145. }
  146. return true;
  147. }
  148.  
  149.  
  150.  
  151. int main(){
  152.  
  153. long n;
  154. for(;;){
  155.  
  156. cin >> n;
  157.  
  158. if(n == 0) break;
  159.  
  160. //the Voronio graph
  161. Voronoi v;
  162.  
  163. int x,y;
  164. for(long i = 0; i < n; ++i){
  165. cin >> x >> y;
  166. v.insert(Point(x,y));
  167. }
  168.  
  169. long m;
  170. K::FT d;
  171. cin >> m;
  172.  
  173. for(long i = 0; i < m; ++i){
  174. cin >> x >> y >> d;
  175. //??? assume the person is in a safe distance ???
  176. Point p(x,y);
  177. //is_route(p,d,&v);
  178. vector<Point> path;
  179. is_route(p,d,&v, &path);
  180. }
  181. cout << endl;
  182. }
  183. }
Add Comment
Please, Sign In to add comment