pgraph.h

source code to compute the visibility polygon of a point in a polygon.

/* Brian O'Connor
 * pgraph.h: classes for pursuer graph construction & traversal.
 */

#include "input.h"
#include "bitmap.h"

class PGNode;
class SortedList;


/* info common to a set of PGArcs, related to cell adjacencies */
class PGAdjInfo {

public:

  PGAdjInfo(Cell *newStart, Cell *newEnd);
  Cell *Start(void) { return start; }
  Cell *End(void) { return end; }
  CellEdge *Border(void) { return border; }
  Bitmap TransitionEntry(int i) { return transitions[i]; }

  void BuildTransitions(void);/* translates start states to end states*/
  void BuildArcs(PursuerGraph *pg);
  void BuildArc(PGNode *node, int nTransitions, PursuerGraph *pg);
private:

  Cell *start;
  Cell *end;

  Line *path; /* line connecting two cell midpoints */
  CellEdge *border; /* line dividing the two cells */

  Bitmap *transitions;


};

/* a directed arc connecting to graph states */
class PGArc {

public:
  PGArc(PGNode *newStart, PGNode *newEnd, PGAdjInfo *newAdjInfo);
  PGNode *Start(void) { return(start); }
  PGNode *End(void) { return(end); }

private:

  PGNode *start;
  PGNode *end;
  PGAdjInfo *adjInfo;

};

/* a node in the Pursuer Graph */
class PGNode {

public:
  PGNode(Cell *cell, Bitmap newState, int newNumStates);

  Cell *NodeCell(void) { return(c); }
  Bitmap NodeState(void) { return(state); }
  int NodeGaps(void) { return(c->nGapEdges); }

  Point *NodePoint(void) { return(c->pt); }
  void SetDist(float d) { dist = d; }
  float Dist(void) { return(dist); }
  PGNode *Predecessor(void) { return(pre); }
  void SetPre(PGNode *p) { pre = p; }
  void Reset(void) { dist = INFINITY; pre = NULL; }

  int NumArcs(void) { return(nArcs); }
  PGNode *Dest(int i) { return( arcs[i]->End() ); }
  void AddTransition(PGNode *dest, PGAdjInfo *adjInfo);

private:

  Cell *c;

  Bitmap state;
  int nStates;

  PGArc **arcs;
  int nArcs;
  double dist;
  PGNode *pre; /* predecessor in search */

  int CountPossibleStates(int newNumStates, Cell *cell);
};


/* the state graph */
class PursuerGraph {

public:
  PursuerGraph(CellInfo *cellInfo, int startCell);
  void Print(void);
  void PrintSolution(PGNode *end);

  PGNode *AddNode(Cell *cell, Bitmap state);
  PGNode *FindNode(Cell *cell, Bitmap state);
  PGNode *Search(void);
  void SetSearchStart(Cell *c) { start = c; }
  PGNode *Best(void) { return best; }

private:

  PGNode **nodes;
  int nNodes;

  PGAdjInfo **adjInfoArr;
  int nAdj;
  Cell *start;
  PGNode *best; // where to continue from if we need to restart.
  Bitmap bestNum; // number of gaps in best state

  void BuildAdjInfoArr(CellInfo *cellInfo);
  void BuildNodeArr(CellInfo *cellInfo);
  SortedList *InitSearch(void);
  int Relax(PGNode *u, PGNode *v, SortedList *list);
  int FindAdjInfo(Cell *c1, Cell *c2); 
  int IsBest(PGNode *n);
};