Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <CGAL/Exact_predicates_exact_constructions_kernel.h>
- #include <CGAL/Delaunay_triangulation_2.h>
- #include <CGAL/Voronoi_diagram_2.h>
- #include <CGAL/Delaunay_triangulation_adaptation_traits_2.h>
- #include <CGAL/Delaunay_triangulation_adaptation_policies_2.h>
- #include <iostream>
- typedef CGAL::Exact_predicates_exact_constructions_kernel K;
- typedef CGAL::Delaunay_triangulation_2<K> Delaunay;
- typedef CGAL::Delaunay_triangulation_adaptation_traits_2<Delaunay> AT;
- typedef CGAL::Delaunay_triangulation_degeneracy_removal_policy_2<Delaunay> AP;
- typedef CGAL::Voronoi_diagram_2<Delaunay,AT,AP> Voronoi;
- typedef Voronoi::Vertex_iterator Iterator;
- typedef K::Point_2 Point;
- typedef K::Segment_2 Segment;
- typedef K::Ray_2 Ray;
- typedef Voronoi::Vertex_handle Vertex;
- typedef Voronoi::Vertex::Halfedge_around_vertex_circulator VCirc;
- typedef Voronoi::Face::Ccb_halfedge_circulator ECirc;
- using namespace std;
- #define SUCCESS "y"
- #define FAIL "n"
- #define HAS(set, x) ((set)->find(x) != (set)->end())
- bool is_route_r(Vertex pos, K::FT max_d, Voronoi* v, set<Vertex>* visited, vector<Point>* path){
- //check current this vertex with the closest infected
- if(CGAL::squared_distance(pos->point(),v->dual().nearest_vertex(pos->point())->point()) < max_d)
- return false;
- visited->insert(pos);
- VCirc crc = (pos)->incident_halfedges();
- do{
- if(HAS(visited, crc->source()))
- continue; // no point in going back to somewhere
- Segment s = v->dual().segment(crc->dual());
- //check if this edge can be taken.
- CGAL::Object o = v->dual().dual(crc->dual());
- if(const Ray* ray = CGAL::object_cast<Ray>(&o)){
- if(CGAL::squared_distance(*ray, s.source()) < max_d ){
- continue; // cannot use the edge
- }
- }else if(const Segment* seg = CGAL::object_cast<Segment>(&o)){
- if(CGAL::squared_distance(*seg, s.source()) < max_d){
- continue; // cannot use the edge
- }
- }
- //check if its an edge we can use to escape!
- if(crc->is_unbounded())
- return true;
- if(is_route_r(crc->source(), max_d, v, visited, path))
- return true;
- }while(++crc != (pos)->incident_halfedges());
- return false;
- }
- bool is_route(Point p, K::FT max_d, Voronoi* v, vector<Point>* pathV){
- K::FT distance = CGAL::squared_distance(p, v->dual().nearest_vertex(p)->point());
- if(distance < max_d)
- return false;
- set<Vertex> set;
- Voronoi::Locate_result l = v->locate(p);
- if (Vertex* vi = boost::get<Voronoi::Vertex_handle>(&l)) {
- return is_route_r((*vi), max_d, v, &set, pathV);
- } else if (Voronoi::Halfedge_handle* h = boost::get<Voronoi::Halfedge_handle>(&l)) {
- bool success = false;
- //see if it is an unbounded edge and try to make a quick escape
- Segment s = v->dual().segment((*h)->dual());
- if(!(*h)->has_source() || !(*h)->has_target()){
- //get the ray
- cout << (*h)->target()->point() << endl;
- CGAL::Object o = v->dual().dual((*h)->dual());
- const Ray* ray = CGAL::object_cast<Ray>(&o);
- Ray newRay = Ray(p, ray->direction());
- if(CGAL::squared_distance(newRay, s.source()) >= max_d )
- return true;
- }
- //see if traveling to the source is possible and try
- if((*h)->has_source()){
- Segment path(p, (*h)->source()->point());
- if(CGAL::squared_distance(path, s.source()) >= max_d )
- success = is_route_r((*h)->source(), max_d, v, &set, pathV);
- }
- //see if travelling to the target is possible and try
- if((*h)->has_target()){
- Segment path(p, (*h)->target()->point());
- if(CGAL::squared_distance(path, s.source()) >= max_d )
- success = success || is_route_r((*h)->target(), max_d, v, &set, pathV);
- }
- return success;
- } else if (Voronoi::Face_handle* f = boost::get<Voronoi::Face_handle>(&l)) {
- //lets move away orthogonaly from the dualPoint
- Ray moveRay = Ray(p, p - (*f)->dual()->point());
- //find the segment which intersects
- ECirc crc = (*f)->outer_ccb();
- do{
- CGAL::Object edge = v->dual().dual(crc->dual());
- if(const Ray* ray = CGAL::object_cast<Ray>(&edge)){
- if(do_intersect(moveRay, *ray)){
- CGAL::Object o = CGAL::intersection(moveRay,*ray);
- const Point* op = CGAL::object_cast<Point>(&o);
- if(op == 0)
- return true;
- else
- return is_route(*op, max_d, v, pathV);
- }
- }else if(const Segment* seg = CGAL::object_cast<Segment>(&edge)){
- if(do_intersect(moveRay, *seg)){
- CGAL::Object o = CGAL::intersection(moveRay,*seg);
- const Point* op = CGAL::object_cast<Point>(&o);
- if(op == 0)
- return true;
- else
- return is_route(*op, max_d, v,pathV);
- }
- }
- }while(++crc != (*f)->outer_ccb());
- }
- return true;
- }
- int main(){
- long n;
- for(;;){
- cin >> n;
- if(n == 0) break;
- //the Voronio graph
- Voronoi v;
- int x,y;
- for(long i = 0; i < n; ++i){
- cin >> x >> y;
- v.insert(Point(x,y));
- }
- long m;
- K::FT d;
- cin >> m;
- for(long i = 0; i < m; ++i){
- cin >> x >> y >> d;
- //??? assume the person is in a safe distance ???
- Point p(x,y);
- //is_route(p,d,&v);
- vector<Point> path;
- is_route(p,d,&v, &path);
- }
- cout << endl;
- }
- }
Add Comment
Please, Sign In to add comment