quadedge.h

关于限制性四叉树实现算法的

/*****************************************************************************
**
** quadedge.h: an include file for the Edge, QuadEdge, and Mesh classes.
**
** Copyright (C) 1995 by Dani Lischinski 
**
** This program is free software; you can redistribute it and/or modify
** it under the terms of the GNU General Public License as published by
** the Free Software Foundation; either version 2 of the License, or
** (at your option) any later version.
**
** This program 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 General Public License for more details.
**
** You should have received a copy of the GNU General Public License
** along with this program; if not, write to the Free Software
** Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
**
******************************************************************************/

#ifndef QUADEDGE_H
#define QUADEDGE_H

#include "geom2d.h"
#include "dllist.h"

class QuadEdge;
class Mesh;

class Edge {
	friend QuadEdge;
	friend Mesh;
	friend void Splice(Edge*, Edge*);
  private:
	char num, mark;
	Edge *next;
	Point2d *data;
  public:
	Edge()	{ data = 0; }
	Edge* Rot();
	Edge* invRot();
	Edge* Sym();
	Edge* Onext();
	Edge* Oprev();
	Edge* Dnext();
	Edge* Dprev();
	Edge* Lnext();	
	Edge* Lprev();
	Edge* Rnext();	
	Edge* Rprev();
	Point2d* Org();
	Point2d* Dest();
	const Point2d& Org2d() const;
	const Point2d& Dest2d() const;
	void  EndPoints(Point2d*, Point2d*);
	void Constrain();
	Boolean isConstrained();
	QuadEdge* QEdge() const    { return (QuadEdge *)(this - num); }
};

class QuadEdge {
	friend Mesh;
  private:
	Edge e[4];
	Boolean c;
	LlistPos p;
  public:
	QuadEdge(Boolean);
	Edge *edges()           { return e; }
	Boolean isConstrained() { return c; }
	void Constrain()        { c = TRUE; }
	~QuadEdge();
};

class Mesh {
  private:
	Edge *startingEdge;
	Llist edges;
	void DeleteEdge(Edge*);
	Edge *MakeEdge(Boolean);
	Edge *MakeEdge(Point2d*, Point2d*, Boolean);
	Edge *Connect(Edge*, Edge*);
	Edge *Locate(const Point2d&);
	Edge *BruteForceLocate(const Point2d&);
	void SplitEdge(Edge*, const Point2d&);
	void Triangulate(Edge*);
	void MarkEdges(Edge*);
  public:
	Mesh(const Point2d&, const Point2d&, const Point2d&);
	Mesh(const Point2d&, const Point2d&, const Point2d&, const Point2d&);
	Mesh(int numVertices, double *bdryVertices);
	Edge *InsertSite(const Point2d&, Real dist = EPS);
	void InsertEdge(const Point2d&, const Point2d&);
	int  numEdges() const { return edges.length(); }
	void ApplyVertices( void (*f)( void *, void * ), void * );
	void ApplyEdges( void (*f)( void *, void *, Boolean ), void * );
	~Mesh();
};

inline QuadEdge::QuadEdge(Boolean constrained = FALSE)
{
	e[0].num = 0, e[1].num = 1, e[2].num = 2, e[3].num = 3;
	e[0].mark = 0, e[1].mark = 0, e[2].mark = 0, e[3].mark = 0;
	e[0].next = &(e[0]); e[1].next = &(e[3]);
	e[2].next = &(e[2]); e[3].next = &(e[1]);
	c = constrained;
}

/************************* Edge Algebra *************************************/

inline Edge* Edge::Rot()
// Return the dual of the current edge, directed from its right to its left. 
{
	return (num < 3) ? this + 1 : this - 3;
}

inline Edge* Edge::invRot()
// Return the dual of the current edge, directed from its left to its right. 
{
	return (num > 0) ? this - 1 : this + 3;
}

inline Edge* Edge::Sym()
// Return the edge from the destination to the origin of the current edge.
{
	return (num < 2) ? this + 2 : this - 2;
}
	
inline Edge* Edge::Onext()
// Return the next ccw edge around (from) the origin of the current edge.
{
	return next;
}

inline Edge* Edge::Oprev()
// Return the next cw edge around (from) the origin of the current edge.
{
	return Rot()->Onext()->Rot();
}

inline Edge* Edge::Dnext()
// Return the next ccw edge around (into) the destination of the current edge.
{
	return Sym()->Onext()->Sym();
}

inline Edge* Edge::Dprev()
// Return the next cw edge around (into) the destination of the current edge.
{
	return invRot()->Onext()->invRot();
}

inline Edge* Edge::Lnext()
// Return the ccw edge around the left face following the current edge.
{
	return invRot()->Onext()->Rot();
}

inline Edge* Edge::Lprev()
// Return the ccw edge around the left face before the current edge.
{
	return Onext()->Sym();
}

inline Edge* Edge::Rnext()
// Return the edge around the right face ccw following the current edge.
{
	return Rot()->Onext()->invRot();
}

inline Edge* Edge::Rprev()
// Return the edge around the right face ccw before the current edge.
{
	return Sym()->Onext();
}

/************** Access to non-topological info ******************************/

inline Point2d* Edge::Org()
{
	return data;
}

inline Point2d* Edge::Dest()
{
	return Sym()->data;
}

inline const Point2d& Edge::Org2d() const
{
	return *data;
}

inline const Point2d& Edge::Dest2d() const
{
	return (num < 2) ? *((this + 2)->data) : *((this - 2)->data);
}

inline void Edge::EndPoints(Point2d* or, Point2d* de)
{
	data = or;
	Sym()->data = de;
}

inline Boolean Edge::isConstrained()
{
	return QEdge()->isConstrained();
}

inline void Edge::Constrain()
{
	QEdge()->Constrain();
}

#endif /* QUADEDGE_H */