visibility.cpp revision e800991baacdaf989464de712ef462863d379687
/*
* vim: ts=4 sw=4 et tw=0 wm=0
*
* libavoid - Fast, Incremental, Object-avoiding Line Router
* Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net>
*
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2.1 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#include <cfloat>
#include "libavoid/visibility.h"
#include "libavoid/vertices.h"
#include "libavoid/geometry.h"
#include <math.h>
#ifdef LINEDEBUG
#include "SDL_gfxPrimitives.h"
#endif
namespace Avoid {
bool UseAStarSearch = true;
bool IgnoreRegions = true;
bool SelectiveReroute = true;
bool IncludeEndpoints = true;
bool UseLeesAlgorithm = false;
bool InvisibilityGrph = true;
bool PartialFeedback = false;
bool PartialTime = false;
void computeCompleteVis(void)
{
{
db_printf("-- CONSIDERING --\n");
{
bool knownNew = true;
}
}
}
{
if (!InvisibilityGrph)
{
// Clear shape from graph.
shape->removeFromGraph();
}
if (IncludeEndpoints)
{
}
else
{
}
{
bool knownNew = true;
db_printf("-- CONSIDERING --\n");
db_printf("\tFirst Half:\n");
{
}
db_printf("\tSecond Half:\n");
{
}
}
}
{
if (!InvisibilityGrph)
{
// Clear shape from graph.
shape->removeFromGraph();
}
{
vertexSweep(i);
}
}
const bool gen_contains)
{
// Make sure we're only doing ptVis for endpoints.
if (!InvisibilityGrph)
{
point->removeFromGraph();
}
{
}
if (UseLeesAlgorithm)
{
}
else
{
k = k->lstNext)
{
}
if (IncludeEndpoints && partner)
{
}
}
}
//============================================================================
// SWEEP CODE
//
static Point centerPoint;
static double centerAngle;
#ifdef LINEDEBUG
#endif
class PointPair
{
public:
{
angle = pos_to_angle(x, y);
}
{
{
return true;
}
return false;
}
static double pos_to_angle(double x, double y)
{
if (x < 0)
{
ang += 180;
}
else if (y < 0)
{
ang += 360;
}
return ang;
}
double angle;
};
class EdgePair
{
public:
{
}
{
{
// TODO: This is a bit of a hack, should be
// set by the call to the constructor.
}
}
{
{
return true;
}
return false;
}
{
{
return false;
}
return true;
}
void SetObsAng(double a)
{
//db_printf("SetObsAng: %.2f (from init %.2f, a %.2f)\n",
// obsAngle, initangle, a);
}
double initdist;
double initangle;
double currdist;
double currangle;
double obsAngle;
};
{
{
// If the points are colinear, then order them in increasing
// distance from the point we are sweeping around.
}
}
#define AHEAD 1
#define BEHIND -1
class isBoundingShape
{
public:
// constructor remembers the value provided
{ }
// the following is an overloading of the function call operator
{
{
return true;
}
return false;
}
private:
};
{
{
// Nothing before it on the current ray
{
{
return false;
}
else
{
return true;
}
}
else
{
return true;
}
}
else
{
// There was another point before this on the ray (lastInf)
if (!lastVisible)
{
*blocker = -1;
return false;
}
else
{
// Check if there is an edge in T that blocks the ray
// between lastInf and currInf.
{
{
return false;
}
}
return true;
}
}
}
{
centerAngle = -1;
// List of shape (and maybe endpt) vertices, except p
// Sort list, around
VertList v;
// Initialise the vertex list
{
{
// Don't include the center point
continue;
}
{
// Add shape vertex
}
else
{
if (IncludeEndpoints)
{
{
// Add endpoint vertex
}
else
{
// Center is an endpoint, so only include the other
// endpoint from the matching connector.
{
}
}
}
}
}
// TODO: This should be done with a sorted data type and insertion sort.
EdgeSet e;
// And edge to T that intersect the initial ray.
{
{
db_printf("Center is inside shape %u so ignore shape edges.\n",
shapeID);
// One of the endpoints is inside this shape so ignore it.
{
// And skip the other vertices from this shape.
k = k->lstNext;
}
continue;
}
{
k = k->lstNext;
continue;
}
{
double distance;
{
}
else
{
}
}
k = k->lstNext;
}
// Start the actual sweep.
double lastAngle = 0;
bool lastVisible = false;
int lastBlocker = 0;
{
centerAngle = (*t).angle;
#ifdef LINEDEBUG
#endif
{
}
// Ignore vertices from bounding shapes, if sweeping round an endpoint.
{
if (InvisibilityGrph)
{
// if p and t can't see each other, add blank edge
db_printf("\tSkipping visibility edge... \n\t\t");
}
continue;
}
{
}
{
}
{
if (InvisibilityGrph)
{
db_printf("\tSetting invisibility edge... \n\t\t");
edge->addBlocker(0);
}
}
else
{
int blocker = 0;
// Check visibility.
if (blocker == -1)
{
}
if (currVisible)
{
#ifdef LINEDEBUG
#endif
db_printf("\tSetting visibility edge... \n\t\t");
}
else if (InvisibilityGrph)
{
db_printf("\tSetting invisibility edge... \n\t\t");
}
}
{
// This is a shape edge
{
// XXX: Strangely e.find does not return the correct results.
// ePtr = e.find(prevPair);
{
}
}
{
}
{
// XXX: Strangely e.find does not return the correct results.
// ePtr = e.find(nextPair);
{
}
}
{
}
}
#ifdef LINEDEBUG
#endif
}
}
}