Class QuadEdge

java.lang.Object

Jcg.triangulations2D.QuadEdge

public class QuadEdge
extends Object

Quad-Edge data structure

Author:

Code by X.Philippeau - Structure by Guibas and Stolfi

See Also:

• invalid reference

  for the Manipulation of General Subdivisions
        and the Computation of Voronoi Diagrams (Leonidas Guibas,Jorge Stolfi)

Field Summary

Fields

Modifier and Type	Field	Description
boolean	cMark
private QuadEdge	dual
boolean	mark
private QuadEdge	next
private Point_2	orig

Constructor Summary

Constructors

Modifier	Constructor	Description
protected	QuadEdge(QuadEdge next, QuadEdge dual, Point_2 orig)	(private) constructor.

Method Summary

Modifier and Type	Method	Description
static QuadEdge	connect(QuadEdge e1, QuadEdge e2)	Creates a new QuadEdge that connects e1.dest() to e2.orig()
static void	deleteEdge(QuadEdge q)	Deletes a QuadEdge, that is, disconnects it from its cycle (same for its dual and its symmetric).
Point_2	dest()	Returns the destination vertex of the QuadEdge.
QuadEdge	dual()	Returns the dual QuadEdge, oriented at 90 degrees in direct order
QuadEdge	dualSym()	Returns the symmetric of the dual QuadEdge (which is also the dual of the symmetric QuadEdge).
boolean	equals(Object o)
static void	flipEdge(QuadEdge e)	Performs a flip of QuadEdge e.
int	hashCode()
QuadEdge	lnext()	Returns the next QuadEdge along the left cycle (lnext.orig() == this.dest())
QuadEdge	lprev()	Returns the previous QuadEdge along the left cycle (lprev.dest() == this.orig())
static QuadEdge	makeEdge(Point_2 orig, Point_2 dest)	Creates a new QuadEdge, setting next and dual fields to default null values.
QuadEdge	next()	Returns the next QuadEdge starting at orig() in direct order
Point_2	orig()	Returns the origin vertex of the QuadEdge.
QuadEdge	prev()	Returns the previous QuadEdge starting at orig() in direct order
QuadEdge	rnext()	Returns the next QuadEdge along the right cycle (rnext.orig() == this.dest())
QuadEdge	rprev()	Returns the previous QuadEdge along the right cycle (rprev.dest() == this.orig())
void	setDual(QuadEdge dual)	sets dual QuadEdge.
void	setNext(QuadEdge next)	Sets next QuadEdge starting from orig() in direct order.
void	setOrig(Point_2 p)	Sets origin vertex of QuadEdge.
static void	splice(QuadEdge a, QuadEdge b)	Merges/splits umbrella around q1.orig() with umbrella around q2.orig().
QuadEdge	sym()	Returns the symmetric QuadEdge, with origin and destination reversed.
String	toString()

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Field Details

next

private QuadEdge next

dual

private QuadEdge dual

orig

private Point_2 orig

mark

public boolean mark

cMark

public boolean cMark

Constructor Details

QuadEdge

protected QuadEdge(QuadEdge next,
 QuadEdge dual,
 Point_2 orig)

(private) constructor. Use makeEdge() to create a new QuadEdge

Parameters:

next - pointer to the next QuadEdge starting from orig in direct order

dual - pointer to the next (direct order) crossing edge

orig - Origin point

Method Details

toString

public String toString()

Overrides:

toString in class Object

next

public QuadEdge next()

Returns the next QuadEdge starting at orig() in direct order

dual

public QuadEdge dual()

Returns the dual QuadEdge, oriented at 90 degrees in direct order

orig

public Point_2 orig()

Returns the origin vertex of the QuadEdge.

setNext

public void setNext(QuadEdge next)

Sets next QuadEdge starting from orig() in direct order.

setDual

public void setDual(QuadEdge dual)

sets dual QuadEdge.

setOrig

public void setOrig(Point_2 p)

Sets origin vertex of QuadEdge.

sym

public QuadEdge sym()

Returns the symmetric QuadEdge, with origin and destination reversed.

dest

public Point_2 dest()

Returns the destination vertex of the QuadEdge.

dualSym

public QuadEdge dualSym()

Returns the symmetric of the dual QuadEdge (which is also the dual of the symmetric QuadEdge).

prev

public QuadEdge prev()

Returns the previous QuadEdge starting at orig() in direct order

rprev

public QuadEdge rprev()

Returns the previous QuadEdge along the right cycle (rprev.dest() == this.orig())

rnext

public QuadEdge rnext()

Returns the next QuadEdge along the right cycle (rnext.orig() == this.dest())

lnext

public QuadEdge lnext()

Returns the next QuadEdge along the left cycle (lnext.orig() == this.dest())

lprev

public QuadEdge lprev()

Returns the previous QuadEdge along the left cycle (lprev.dest() == this.orig())

makeEdge

public static QuadEdge makeEdge(Point_2 orig,
 Point_2 dest)

Creates a new QuadEdge, setting next and dual fields to default null values.

Parameters:

orig - origin of the segment

dest - end of the segment

Returns:

the QuadEdge of the origin point

splice

public static void splice(QuadEdge a,
 QuadEdge b)

Merges/splits umbrella around q1.orig() with umbrella around q2.orig(). In other words, connects/disconnects their dual cycles

Parameters:

q1 - ,q2 the 2 QuadEdge to attach/detach

connect

public static QuadEdge connect(QuadEdge e1,
 QuadEdge e2)

Creates a new QuadEdge that connects e1.dest() to e2.orig()

Parameters:

e1 - ,e2 the 2 QuadEdges to connect

Returns:

the new QuadEdge

flipEdge

public static void flipEdge(QuadEdge e)

Performs a flip of QuadEdge e.

Parameters:

e - the 2 QuadEdges to connect

deleteEdge

public static void deleteEdge(QuadEdge q)

Deletes a QuadEdge, that is, disconnects it from its cycle (same for its dual and its symmetric).

Parameters:

q - the QuadEdge to delete

equals

public boolean equals(Object o)

Overrides:

equals in class Object

hashCode

public int hashCode()

Overrides:

hashCode in class Object