Raw File
#pragma once
#include "pch.h"
#include "ArrangementFunctions.h"
#include "Convex_expansion_visibility_2_temp.h"
#include "IOHandling.h"
#include "IPSolver.h"

typedef Convex_expansion_visibility_2 CEV;


class Visibility {
public:
	TEV pointVisibility;
	CEV weakVisibility;
	Arrangement_2 polygonBoundary;
	vector<shared_ptr<WeakVisNode>> weakVisNodes;
	int verticesCount = 0;
	int facesCount = 0;
	int weakvisLookups = 0;
	int constantLookups = 0;
	int faceVisibilitiesComputed = 0;
	int pointVisibilitiesComputed = 0;
	vector<Vertex_handle> allVertices; //lookup array
	vector<Face_handle> allFaces; //lookup array

	Landmarks_pl vertexLocation;
	Arrangement_2 thePolygon;

	//2000 max we allow!
	//Arrangement_2 emptyArr;
	//vector<Arrangement_2> pointvisPolygons = std::vector<Arrangement_2>(2000, emptyArr);
	//vector<Arrangement_2> facevisPolygons = std::vector<Arrangement_2>(2000, emptyArr);

	vector<Polygon_2> pointvisPolygons; 
	vector<Polygon_2> facevisPolygons; 

	//vector<Landmarks_pl> pointPLs = std::vector<Landmarks_pl>(2000, Landmarks_pl());
	//vector<Landmarks_pl> facePLs = std::vector<Landmarks_pl>(2000, Landmarks_pl());

	IPSolver* IP;
	int critProbability;

	//default constructors
	Visibility() {};
	void attach(IPSolver* IP, int critProbability) {
		this->IP = IP;
		this->critProbability = critProbability;
		weakVisibility.attach(polygonBoundary);//only once, otherwise there will be convex decompositions
		pointVisibility.attach(polygonBoundary); //only once, otherwise there will be unecessary triangulations
		vertexLocation.attach(polygonBoundary);



	};

	bool faceSeesWitness(Face_handle faceguard, Vertex_handle witness) {
		if (seesWitness(witness, faceguard)) //if he sees us then we see him
			return true;


		auto eit = faceguard->outer_ccb();
		do{
			if (seesWitness(eit->source(), witness))
				return true;
		} while (++eit != faceguard->outer_ccb());

		faceVisibilitiesComputed++;

		
		CGAL::Bounded_side bside = facevisPolygons[faceguard->data().id].bounded_side(witness->point());
		return bside == CGAL::ON_BOUNDED_SIDE || bside == CGAL::ON_BOUNDARY;

		/*vector<Point_2> facePoly = faceToPolygonP(faceguard);
		list<Point_2> pointVispts = pointvisPolygons[witness->data().id].container();
		return do_intersect(Polygon_2(facePoly.begin(), facePoly.end()), pointvisPolygons[witness->data().id]);*/
		//faceToPolygon(faceGuard);

		eit = faceguard->outer_ccb();
		do {
			for (auto pedge = pointvisPolygons[witness->data().id].edges_begin(); pedge != pointvisPolygons[witness->data().id].edges_end(); pedge++)					
				if (CGAL::do_intersect(Segment_2(pedge->source(), pedge->target()), Segment_2(eit->source()->point(), eit->target()->point())))
					return true;			
		} while (++eit != faceguard->outer_ccb());

		return false;
	}

	template <typename T>
	bool seesWitness(T const& guard, Vertex_handle witness) {	
		int guardID = guard->data().id;
		int witnessID = witness->data().id;

		if (guard->data().seenVertices.find(witnessID) != guard->data().seenVertices.end()){
			//if (is_same<T, Vertex_handle>::value) 
				//witness->data().seenVertices[guardID] = true; //symmetry		
			
			constantLookups++;
			return true;
		}
		if (guard->data().unseenVertices.find(witnessID) != guard->data().unseenVertices.end()) {
			//if (is_same<T, Vertex_handle>::value)
				//witness->data().unseenVertices[guardID] = true; //symmetry	

			constantLookups++;
			return false;
		}

		//first check weakvis decomp
		bool visible = false;
		
		if (guard->data().pweakNodeIds.empty() || witness->data().pweakNodeIds.empty()) {
			cout << "u";
			visible = true;
		}
		for (auto wvit = guard->data().pweakNodeIds.begin();!visible && wvit != guard->data().pweakNodeIds.end();wvit++) {
			for (auto wvit2 = witness->data().pweakNodeIds.begin(); !visible && wvit2 != witness->data().pweakNodeIds.end();wvit2++) {
				visible = weakVisNodes[*wvit]->canSeeDecomp(weakVisNodes[*wvit2]);
			}
		}				
		
		//According to the decomp, it is possible for us to see the witness: go and check
		if (visible) {

			//Check visibility
			CGAL::Bounded_side bside;

			if constexpr (std::is_same<T, Face_handle>::value)
				visible = faceSeesWitness(guard, witness);
			else {
				pointVisibilitiesComputed++;
				bside = pointvisPolygons[guardID].bounded_side(witness->point());
				visible = bside == CGAL::ON_BOUNDED_SIDE || bside == CGAL::ON_BOUNDARY;
			}		
		}
		else {
			weakvisLookups++;
			return false; //don't save in constant lookup!
		}
		if (visible) {
			guard->data().seenVertices[witnessID] = true;

			if (is_same<T, Vertex_handle>::value) 
				witness->data().seenVertices[guardID] = true; //symmetry			
		}
		else {
			guard->data().unseenVertices[witnessID] = true;
			if (is_same<T, Vertex_handle>::value) 
				witness->data().unseenVertices[guardID] = true; //symmetry		
		}

		return visible;
	}
	
	
	template <typename T>
	bool seesWitness(T const& guard, Face_handle witness) {
		bool seen = true;

		//We need to see all vertices!
		auto eit = witness->outer_ccb();
		do {
			if (!seesWitness(guard, eit->source())) {
				seen = false;
				break;
			}	
		} while (++eit != witness->outer_ccb());

			//if (uncreated == verticesNum)
				//cout << "That is really bad \n";

		return seen;
	}

	template <typename T>
	void updateVisibilities(T const& guard, bool onlyUs = false) {
		//Go through all vertices
		for (auto vit = thePolygon.vertices_begin(); vit != thePolygon.vertices_end(); ++vit) {
			if (vit->data().created) {
				if (!onlyUs && vit->data().isCritical && seesWitness(guard, vit)) {
					if (is_same<T, Vertex_handle>::value)
						IP->pointExpr[vit->data().id] += IP->pointguardVar[guard->data().id];
					else
						IP->pointExpr[vit->data().id] += IP->faceguardVar[guard->data().id];
				}
				if (guard->data().isCritical && seesWitness(vit, guard))
					if (is_same<T, Vertex_handle>::value)
						IP->pointExpr[guard->data().id] += IP->pointguardVar[vit->data().id];
					else
						IP->faceExpr[guard->data().id] += IP->pointguardVar[vit->data().id];

			}
		}

		//Go through all faces
		for (auto fit = thePolygon.faces_begin(); fit != thePolygon.faces_end(); ++fit) {
			if (fit->data().created) { //only after preprocessing!
				//check us-them visibility
				if (!onlyUs && fit->data().isCritical && seesWitness(guard, fit))
					if (is_same<T, Vertex_handle>::value)
						IP->faceExpr[fit->data().id] += IP->pointguardVar[guard->data().id];
					else
						IP->faceExpr[fit->data().id] += IP->faceguardVar[guard->data().id];
				if (guard->data().isCritical && seesWitness(fit, guard))
					if (is_same<T, Vertex_handle>::value)
						IP->pointExpr[guard->data().id] += IP->faceguardVar[fit->data().id];
					else
						IP->faceExpr[guard->data().id] += IP->faceguardVar[fit->data().id];
			}
		}
	}

	void prepareGuard(Vertex_handle v, FaceGuard papa) {
		if (v->data().id > -1)
			int cirsb = 15; //shouldnt get doubles

		v->data().id = verticesCount;
		verticesCount++;

		allVertices.push_back(v);

		if (papa.id > -1) {
			v->data().unseenVertices = papa.unseenVertices; //copy unseen table

			//don't copy all of papa's weaknodes, try to locate point inside every weak note
			for (auto& weaknodeId : papa.pweakNodeIds)
			{
				CGAL::Bounded_side bside = weakVisNodes[weaknodeId]->boundary.bounded_side(v->point());
				if (bside == CGAL::ON_BOUNDARY || bside == CGAL::ON_BOUNDED_SIDE)
					v->data().pweakNodeIds.insert(weaknodeId);
			}

		}

		//Part of the initialization... fine, we'll just find the nodes manually
		if (v->data().pweakNodeIds.empty()) {
			for (auto wvit = weakVisNodes.begin(); wvit != weakVisNodes.end(); wvit++)
			{
				CGAL::Bounded_side bside = (*wvit)->boundary.bounded_side(v->point());
				if (bside == CGAL::ON_BOUNDARY || bside == CGAL::ON_BOUNDED_SIDE)
					v->data().pweakNodeIds.insert((*wvit)->id);
			}
		}

		if (v->data().pweakNodeIds.empty())
			cout << "a vertex";

		IP->pointExpr.add(IloExpr(IP->env));
		IP->pointConstraints.add(IloRange(IP->env ,1, IloGetInfinity()));
		IP->pointguardVar.add(IloIntVar(IP->env, 0, 1));


		//Locate vertex (face or halfedge handle)
		//Set up visibility polygon
		CGAL::Arr_point_location_result<Arrangement_2>::Type obj =
			vertexLocation.locate(v->point());
		Arrangement_2::Face_const_handle fLoc;
		Halfedge_const_handle heLoc;
		Arrangement_2::Vertex_const_handle vLoc;
		Arrangement_2 visPoly;

		if (CGAL::assign(fLoc, obj))
		{
			//we are in middle of the main face...
			pointVisibility.compute_visibility(v->point(), fLoc, visPoly);
		}
		else if (CGAL::assign(heLoc, obj)) {
			if (!heLoc->face()->has_outer_ccb())
				heLoc = heLoc->twin();
			//we are in a half-edge
			pointVisibility.compute_visibility(v->point(), heLoc, visPoly);
		}
		else if (CGAL::assign(vLoc, obj)) {
			Halfedge_const_handle he = vLoc->incident_halfedges();
			if (!he->face()->has_outer_ccb())
				he = he->twin()->prev();
			//we are in a vertex
			pointVisibility.compute_visibility(v->point(), he, visPoly);
		}		
		pointvisPolygons.push_back(arrangementToPolygon(visPoly));


		//pointPLs[v->data().id].attach(pointvisPolygons[v->data().id]);

		//Throw dice for critical marking
		int dice = rand() % 100 + 1; //100 sided dice
		if (dice <= critProbability || v->data().id == 1) {
			v->data().isCritical = true;
		}

	}

	void prepareGuard(Face_handle f, FaceGuard papa) {
		f->data().id = facesCount;
		facesCount++;

		allFaces.push_back(f);

		//never copy weaknodes
		//f->data().fweakNodeIds = papa.fweakNodeIds;
		//f->data().pweakNodeIds = papa.pweakNodeIds;
	
		//if our vertices can see it, so can we!
		auto eit = f->outer_ccb();
		do {
			auto vertexWeaknodes = eit->source()->data().pweakNodeIds;
			f->data().pweakNodeIds.insert(vertexWeaknodes.begin(), vertexWeaknodes.end());

			for (auto itr = eit->source()->data().seenVertices.begin(); itr != eit->source()->data().seenVertices.end(); itr++)
			{
				f->data().seenVertices[itr->first] = itr->second;
			}
		} while (++eit != f->outer_ccb());


		//If the papa face cannot see it, then the new ones cannot either!
		f->data().unseenVertices = papa.unseenVertices;

		//initialize vars
		IP->faceExpr.add(IloExpr(IP->env));
		IP->faceguardVar.add(IloIntVar(IP->env, 0, 1));
		IP->facewitnessVar.add(IloIntVar(IP->env, 0, 1));
		IP->faceConstraints.add(IloRange(IP->env, 1, IloGetInfinity()));
		
		//allow us to be critical
		IP->faceExpr[f->data().id] += IP->facewitnessVar[f->data().id];

		//cout << "FaceID " << f->data().id << "\n";

		Arrangement_2 visPoly;
		weakVisibility.compute_visibility(faceToPolygon(f), visPoly);
		facevisPolygons.push_back(arrangementToPolygon(visPoly));
		
		//for (int i = 0; i < weakVisibility.vis_polygons.size(); i++)
			//IOHandling::DrawWeakVis(weakVisibility, "P3/intermediate" + to_string(f->data().id - 1) + "-" + to_string(i),
				//faceToPolygon(f), {}, i);

		//Throw dice for critical marking
		if (rand() % 100 + 1 <= critProbability || f->data().id == 1) {
			f->data().isCritical = true;

			////mark all vertices as critical too, they're free of charge anyway...
			auto eit = f->outer_ccb();
			do {
				if (!eit->source()->data().isCritical) {
					eit->source()->data().isCritical = true;
					updateVisibilities(eit->source(), true); //update the point visibilities too because it is critical now!
				}
			} while (++eit != f->outer_ccb());
		}
		updateVisibilities(f);
	}

	bool verifySolution() {
		bool allVerticesSeen = true;
		bool allFacesSeen = true;

		//Go through all vertices
		for (auto vit = thePolygon.vertices_begin(); vit != thePolygon.vertices_end(); ++vit) {		
			bool vertexSeen = false;

			if (!vit->data().isCritical) {
				//Go through solution vertices
				for (auto solVit = IP->vertexSolution.begin(); solVit != IP->vertexSolution.end(); ++solVit) {
					if (seesWitness(*solVit, vit)) {
						vertexSeen = true;
						break;
					}
				}

				//Go through solution faces
				if (!vertexSeen) {
					for (auto solFit = IP->faceSolution.begin(); solFit != IP->faceSolution.end(); ++solFit) {
						if (seesWitness(*solFit, vit)) {
							vertexSeen = true;
							break;
						}
					}
				}

				if (!vertexSeen) {
					//mark as critical and break
					vit->data().isCritical = true;

					updateVisibilities(vit, true);
					allVerticesSeen = false;
					break;
				}
			}
		}

		//Go through all faces
		for (auto fit = thePolygon.faces_begin(); fit != thePolygon.faces_end(); ++fit) {
			if (fit->has_outer_ccb() && !fit->data().isCritical) {

				bool faceSeen = false;
				//Go through solution vertices
				for (auto solVit = IP->vertexSolution.begin(); solVit != IP->vertexSolution.end(); ++solVit) {
					if (seesWitness(*solVit, fit)) {
						faceSeen = true;
						break;
					}
				}

				//Go through solution faces
				if (!faceSeen) {
					for (auto solFit = IP->faceSolution.begin(); solFit != IP->faceSolution.end(); ++solFit) {
						if (seesWitness(*solFit, fit)) {
							faceSeen = true;
							break;
						}
					}
				}

				if (!faceSeen) {
					//mark all vertices as critical too, they're free of charge anyway...
					auto eit = fit->outer_ccb();
					do {
						eit->source()->data().isCritical = true;
						updateVisibilities(eit->source(), true); //update the point visibilities too because it is critical now!

					} while (++eit != fit->outer_ccb());


					//mark as critical and break
					fit->data().isCritical = true;
					updateVisibilities(fit, true); //make sure onlyUs is on so we don't compute useless visibilities again
					
					
					
					
					allFacesSeen = false;
					break;
				}
			}
		}

		return (allVerticesSeen && allFacesSeen);
	}
};
back to top