← Back to branch summary

~ubuntu-branches/ubuntu/natty/jts/natty

« back to all changes in this revision

Viewing changes to src/com/vividsolutions/jts/geomgraph/EdgeIntersectionList.java

  • Committer: Bazaar Package Importer
  • Author(s): Wolfgang Baer
  • Date: 2005-08-07 14:12:35 UTC
  • Revision ID: james.westby@ubuntu.com-20050807141235-7hy3ll3xpq79djcb
Tags: upstream-1.6
Import upstream version 1.6

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/com/vividsolutions/jts/geomgraph/EdgeIntersectionList.java
 
1
 
 
2
 
 
3
 
 
4
/*
 
5
 * The JTS Topology Suite is a collection of Java classes that
 
6
 * implement the fundamental operations required to validate a given
 
7
 * geo-spatial data set to a known topological specification.
 
8
 *
 
9
 * Copyright (C) 2001 Vivid Solutions
 
10
 *
 
11
 * This library is free software; you can redistribute it and/or
 
12
 * modify it under the terms of the GNU Lesser General Public
 
13
 * License as published by the Free Software Foundation; either
 
14
 * version 2.1 of the License, or (at your option) any later version.
 
15
 *
 
16
 * This library is distributed in the hope that it will be useful,
 
17
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
18
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
19
 * Lesser General Public License for more details.
 
20
 *
 
21
 * You should have received a copy of the GNU Lesser General Public
 
22
 * License along with this library; if not, write to the Free Software
 
23
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
24
 *
 
25
 * For more information, contact:
 
26
 *
 
27
 *     Vivid Solutions
 
28
 *     Suite #1A
 
29
 *     2328 Government Street
 
30
 *     Victoria BC  V8T 5G5
 
31
 *     Canada
 
32
 *
 
33
 *     (250)385-6040
 
34
 *     www.vividsolutions.com
 
35
 */
 
36
package com.vividsolutions.jts.geomgraph;
 
37
 
 
38
import java.io.PrintStream;
 
39
import java.util.*;
 
40
import com.vividsolutions.jts.geom.Coordinate;
 
41
import com.vividsolutions.jts.util.Debug;
 
42
 
 
43
/**
 
44
 * A list of edge intersections along an Edge
 
45
 * @version 1.6
 
46
 */
 
47
public class EdgeIntersectionList
 
48
{
 
49
  // a List of EdgeIntersections
 
50
  //List list = new ArrayList();    // more efficient to use a LinkedList, but ArrayList is easier for debugging
 
51
  private Map nodeMap = new TreeMap();
 
52
  Edge edge;  // the parent edge
 
53
 
 
54
  public EdgeIntersectionList(Edge edge)
 
55
  {
 
56
    this.edge = edge;
 
57
  }
 
58
 
 
59
  /**
 
60
   * Adds an intersection into the list, if it isn't already there.
 
61
   * The input segmentIndex and dist are expected to be normalized.
 
62
   * @return the EdgeIntersection found or added
 
63
   */
 
64
  public EdgeIntersection add(Coordinate intPt, int segmentIndex, double dist)
 
65
  {
 
66
    EdgeIntersection eiNew = new EdgeIntersection(intPt, segmentIndex, dist);
 
67
    Object obj = nodeMap.get(eiNew);
 
68
    EdgeIntersection ei = (EdgeIntersection) nodeMap.get(eiNew);
 
69
    if (ei != null) {
 
70
      return ei;
 
71
    }
 
72
    nodeMap.put(eiNew, eiNew);
 
73
    return eiNew;
 
74
  }
 
75
  /*
 
76
  public EdgeIntersection add(Coordinate intPt, int segmentIndex, double dist)
 
77
  {
 
78
//Debug.println("adding edgeInt " + intPt + " " + segmentIndex + " " + dist);
 
79
    ListIterator insertIt = list.listIterator();
 
80
    boolean isInList = findInsertionPoint(segmentIndex, dist, insertIt);
 
81
    EdgeIntersection ei;
 
82
    if (! isInList) {
 
83
      ei = new EdgeIntersection(intPt, segmentIndex, dist);
 
84
      insertIt.add(ei);
 
85
    }
 
86
    else
 
87
      ei = (EdgeIntersection) insertIt.next();
 
88
    return ei;
 
89
  }
 
90
  */
 
91
  /**
 
92
   * returns an iterator of EdgeIntersections
 
93
   */
 
94
  public Iterator iterator() { return nodeMap.values().iterator(); }
 
95
/*
 
96
  public boolean isEmpty()
 
97
  {
 
98
    Iterator it = list.iterator();
 
99
    return ! it.hasNext();
 
100
  }
 
101
  */
 
102
  /**
 
103
   * This routine searches the list for the insertion point for the given intersection
 
104
   * (which must be in normalized form).
 
105
   * The intersection point may already be in the list - in this case, the intersection
 
106
   * is not inserted.
 
107
   * If the intersection is new, it is inserted into the list.
 
108
   * The insertIt iterator is left pointing at the correct place
 
109
   * to insert the intersection, if the intersection was not found.
 
110
   *
 
111
   * @return true if this intersection is already in the list
 
112
   */
 
113
  /*
 
114
  boolean findInsertionPoint(int segmentIndex, double dist, ListIterator insertIt)
 
115
  {
 
116
    // The insertIt position trails the findIt position by one
 
117
    ListIterator findIt = list.listIterator();
 
118
    boolean found = false;
 
119
    while (findIt.hasNext()) {
 
120
      EdgeIntersection ei = (EdgeIntersection) findIt.next();
 
121
      int compare = ei.compare(segmentIndex, dist);
 
122
 
 
123
      // intersection found - insertIt.next() will retrieve it
 
124
      if (compare == 0) return true;
 
125
 
 
126
      // this ei is past the intersection location, so intersection was not found
 
127
      if (compare > 0) return false;
 
128
 
 
129
      // this ei was before the intersection point, so move to next
 
130
      insertIt.next();
 
131
    }
 
132
    return false;
 
133
  }
 
134
  */
 
135
  public boolean isIntersection(Coordinate pt)
 
136
  {
 
137
    for (Iterator it = iterator(); it.hasNext(); ) {
 
138
      EdgeIntersection ei = (EdgeIntersection) it.next();
 
139
      if (ei.coord.equals(pt))
 
140
       return true;
 
141
    }
 
142
    return false;
 
143
  }
 
144
 
 
145
  /**
 
146
   * Adds entries for the first and last points of the edge to the list
 
147
   */
 
148
  public void addEndpoints()
 
149
  {
 
150
    int maxSegIndex = edge.pts.length - 1;
 
151
    add(edge.pts[0], 0, 0.0);
 
152
    add(edge.pts[maxSegIndex], maxSegIndex, 0.0);
 
153
  }
 
154
 
 
155
  /**
 
156
   * Creates new edges for all the edges that the intersections in this
 
157
   * list split the parent edge into.
 
158
   * Adds the edges to the input list (this is so a single list
 
159
   * can be used to accumulate all split edges for a Geometry).
 
160
   */
 
161
  public void addSplitEdges(List edgeList)
 
162
  {
 
163
    // ensure that the list has entries for the first and last point of the edge
 
164
    addEndpoints();
 
165
 
 
166
    Iterator it = iterator();
 
167
    // there should always be at least two entries in the list
 
168
    EdgeIntersection eiPrev = (EdgeIntersection) it.next();
 
169
    while (it.hasNext()) {
 
170
      EdgeIntersection ei = (EdgeIntersection) it.next();
 
171
      Edge newEdge = createSplitEdge(eiPrev, ei);
 
172
      edgeList.add(newEdge);
 
173
 
 
174
      eiPrev = ei;
 
175
    }
 
176
  }
 
177
  /**
 
178
   * Create a new "split edge" with the section of points between
 
179
   * (and including) the two intersections.
 
180
   * The label for the new edge is the same as the label for the parent edge.
 
181
   */
 
182
  Edge createSplitEdge(EdgeIntersection ei0, EdgeIntersection ei1)
 
183
  {
 
184
//Debug.print("\ncreateSplitEdge"); Debug.print(ei0); Debug.print(ei1);
 
185
    int npts = ei1.segmentIndex - ei0.segmentIndex + 2;
 
186
 
 
187
    Coordinate lastSegStartPt = edge.pts[ei1.segmentIndex];
 
188
    // if the last intersection point is not equal to the its segment start pt,
 
189
    // add it to the points list as well.
 
190
    // (This check is needed because the distance metric is not totally reliable!)
 
191
    // The check for point equality is 2D only - Z values are ignored
 
192
    boolean useIntPt1 = ei1.dist > 0.0 || ! ei1.coord.equals2D(lastSegStartPt);
 
193
    if (! useIntPt1) {
 
194
      npts--;
 
195
    }
 
196
 
 
197
    Coordinate[] pts = new Coordinate[npts];
 
198
    int ipt = 0;
 
199
    pts[ipt++] = new Coordinate(ei0.coord);
 
200
    for (int i = ei0.segmentIndex + 1; i <= ei1.segmentIndex; i++) {
 
201
      pts[ipt++] = edge.pts[i];
 
202
    }
 
203
    if (useIntPt1) pts[ipt] = ei1.coord;
 
204
    return new Edge(pts, new Label(edge.label));
 
205
  }
 
206
 
 
207
  public void print(PrintStream out)
 
208
  {
 
209
    out.println("Intersections:");
 
210
    for (Iterator it = iterator(); it.hasNext(); ) {
 
211
      EdgeIntersection ei = (EdgeIntersection) it.next();
 
212
      ei.print(out);
 
213
    }
 
214
  }
 
215
}