Class DirectedEdge

1
2	/*
3	* Copyright (c) 2016 Vivid Solutions.
4	*
5	* All rights reserved. This program and the accompanying materials
6	* are made available under the terms of the Eclipse Public License 2.0
7	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
8	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
9	* and the Eclipse Distribution License is available at
10	*
11	* http://www.eclipse.org/org/documents/edl-v10.php.
12	*/
13	package org.locationtech.jts.planargraph;
14
15	import java.io.PrintStream;
16	import java.util.ArrayList;
17	import java.util.Collection;
18	import java.util.Iterator;
19	import java.util.List;
20
21	import org.locationtech.jts.algorithm.Orientation;
22	import org.locationtech.jts.geom.Coordinate;
23	import org.locationtech.jts.geomgraph.Quadrant;
24
25	/**
26	* Represents a directed edge in a {@link PlanarGraph}. A DirectedEdge may or
27	* may not have a reference to a parent {@link Edge} (some applications of
28	* planar graphs may not require explicit Edge objects to be created). Usually
29	* a client using a <code>PlanarGraph</code> will subclass <code>DirectedEdge</code>
30	* to add its own application-specific data and methods.
31	*
32	* @version 1.7
33	*/
34	public class DirectedEdge
35	extends GraphComponent
36	implements Comparable
37	{
38	/**
39	* Returns a List containing the parent Edge (possibly null) for each of the given
40	* DirectedEdges.
41	*/
42	public static List toEdges(Collection dirEdges)
43	{
44	List edges = new ArrayList();
45	for (Iterator i = dirEdges.iterator(); i.hasNext(); ) {
46	edges.add( ((DirectedEdge) i.next()).parentEdge);
47	}
48	return edges;
49	}
50
51	protected Edge parentEdge;
52	protected Node from;
53	protected Node to;
54	protected Coordinate p0, p1;
55	protected DirectedEdge sym = null; // optional
56	protected boolean edgeDirection;
57	protected int quadrant;
58	protected double angle;
59
60	/**
61	* Constructs a DirectedEdge connecting the <code>from</code> node to the
62	* <code>to</code> node.
63	*
64	* @param directionPt
65	* specifies this DirectedEdge's direction vector
66	* (determined by the vector from the <code>from</code> node
67	* to <code>directionPt</code>)
68	* @param edgeDirection
69	* whether this DirectedEdge's direction is the same as or
70	* opposite to that of the parent Edge (if any)
71	*/
72	public DirectedEdge(Node from, Node to, Coordinate directionPt, boolean edgeDirection)
73	{
74	this.from = from;
75	this.to = to;
76	this.edgeDirection = edgeDirection;
77	p0 = from.getCoordinate();
78	p1 = directionPt;
79	double dx = p1.x - p0.x;
80	double dy = p1.y - p0.y;
81	quadrant = Quadrant.quadrant(dx, dy);
82	angle = Math.atan2(dy, dx);
83	//Assert.isTrue(! (dx == 0 && dy == 0), "EdgeEnd with identical endpoints found");
84	}
85
86	/**
87	* Returns this DirectedEdge's parent Edge, or null if it has none.
88	*/
89	public Edge getEdge() { return parentEdge; }
90	/**
91	* Associates this DirectedEdge with an Edge (possibly null, indicating no associated
92	* Edge).
93	*/
94	public void setEdge(Edge parentEdge) { this.parentEdge = parentEdge; }
95	/**
96	* Returns 0, 1, 2, or 3, indicating the quadrant in which this DirectedEdge's
97	* orientation lies.
98	*/
99	public int getQuadrant() { return quadrant; }
100	/**
101	* Returns a point to which an imaginary line is drawn from the from-node to
102	* specify this DirectedEdge's orientation.
103	*/
104	public Coordinate getDirectionPt() { return p1; }
105	/**
106	* Returns whether the direction of the parent Edge (if any) is the same as that
107	* of this Directed Edge.
108	*/
109	public boolean getEdgeDirection() { return edgeDirection; }
110	/**
111	* Returns the node from which this DirectedEdge leaves.
112	*/
113	public Node getFromNode() { return from; }
114	/**
115	* Returns the node to which this DirectedEdge goes.
116	*/
117	public Node getToNode() { return to; }
118	/**
119	* Returns the coordinate of the from-node.
120	*/
121	public Coordinate getCoordinate() { return from.getCoordinate(); }
122	/**
123	* Returns the angle that the start of this DirectedEdge makes with the
124	* positive x-axis, in radians.
125	*/
126	public double getAngle() { return angle; }
127	/**
128	* Returns the symmetric DirectedEdge -- the other DirectedEdge associated with
129	* this DirectedEdge's parent Edge.
130	*/
131	public DirectedEdge getSym() { return sym; }
132	/**
133	* Sets this DirectedEdge's symmetric DirectedEdge, which runs in the opposite
134	* direction.
135	*/
136	public void setSym(DirectedEdge sym) { this.sym = sym; }
137
138	/**
139	* Removes this directed edge from its containing graph.
140	*/
141	void remove() {
142	this.sym = null;
143	this.parentEdge = null;
144	}
145
146	/**
147	* Tests whether this directed edge has been removed from its containing graph
148	*
149	* @return <code>true</code> if this directed edge is removed
150	*/
151	public boolean isRemoved()
152	{
153	return parentEdge == null;
154	}
155
156	/**
157	* Returns 1 if this DirectedEdge has a greater angle with the
158	* positive x-axis than b", 0 if the DirectedEdges are collinear, and -1 otherwise.
159	* <p>
160	* Using the obvious algorithm of simply computing the angle is not robust,
161	* since the angle calculation is susceptible to roundoff. A robust algorithm
162	* is:
163	* <ul>
164	* <li>first compare the quadrants. If the quadrants are different, it it
165	* trivial to determine which vector is "greater".
166	* <li>if the vectors lie in the same quadrant, the robust
167	* {@link Orientation#computeOrientation(Coordinate, Coordinate, Coordinate)}
168	* function can be used to decide the relative orientation of the vectors.
169	* </ul>
170	*/
171	public int compareTo(Object obj)
172	{
173	DirectedEdge de = (DirectedEdge) obj;
174	return compareDirection(de);
175	}
176
177	/**
178	* Returns 1 if this DirectedEdge has a greater angle with the
179	* positive x-axis than b", 0 if the DirectedEdges are collinear, and -1 otherwise.
180	* <p>
181	* Using the obvious algorithm of simply computing the angle is not robust,
182	* since the angle calculation is susceptible to roundoff. A robust algorithm
183	* is:
184	* <ul>
185	* <li>first compare the quadrants. If the quadrants are different, it it
186	* trivial to determine which vector is "greater".
187	* <li>if the vectors lie in the same quadrant, the robust
188	* {@link Orientation#computeOrientation(Coordinate, Coordinate, Coordinate)}
189	* function can be used to decide the relative orientation of the vectors.
190	* </ul>
191	*/
192	public int compareDirection(DirectedEdge e)
193	{
194	// if the rays are in different quadrants, determining the ordering is trivial
195	if (quadrant > e.quadrant) return 1;
196	if (quadrant < e.quadrant) return -1;
197	// vectors are in the same quadrant - check relative orientation of direction vectors
198	// this is > e if it is CCW of e
199	return Orientation.index(e.p0, e.p1, p1);
200	}
201
202	/**
203	* Prints a detailed string representation of this DirectedEdge to the given PrintStream.
204	*/
205	public void print(PrintStream out)
206	{
207	String className = getClass().getName();
208	int lastDotPos = className.lastIndexOf('.');
209	String name = className.substring(lastDotPos + 1);
210	out.print(" " + name + ": " + p0 + " - " + p1 + " " + quadrant + ":" + angle);
211	}
212
213	}
214