svn-gvsig-desktop / tags / J2ME_compat_v1_2_Build_1209 / libraries / libFMap / src / com / vividsolutions / jts / geomgraph / index / SnapSimpleMCSweepLineIntersector.java @ 19509
History | View | Annotate | Download (5.13 KB)
1 | 19509 | jcarrasco | /*
|
---|---|---|---|
2 | * Created on 02-oct-2006
|
||
3 | *
|
||
4 | * gvSIG. Sistema de Informaci?n Geogr?fica de la Generalitat Valenciana
|
||
5 | *
|
||
6 | * Copyright (C) 2004 IVER T.I. and Generalitat Valenciana.
|
||
7 | *
|
||
8 | * This program is free software; you can redistribute it and/or
|
||
9 | * modify it under the terms of the GNU General Public License
|
||
10 | * as published by the Free Software Foundation; either version 2
|
||
11 | * of the License, or (at your option) any later version.
|
||
12 | *
|
||
13 | * This program is distributed in the hope that it will be useful,
|
||
14 | * but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
15 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
16 | * GNU General Public License for more details.
|
||
17 | *
|
||
18 | * You should have received a copy of the GNU General Public License
|
||
19 | * along with this program; if not, write to the Free Software
|
||
20 | * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,USA.
|
||
21 | *
|
||
22 | * For more information, contact:
|
||
23 | *
|
||
24 | * Generalitat Valenciana
|
||
25 | * Conselleria d'Infraestructures i Transport
|
||
26 | * Av. Blasco Ib??ez, 50
|
||
27 | * 46010 VALENCIA
|
||
28 | * SPAIN
|
||
29 | *
|
||
30 | * +34 963862235
|
||
31 | * gvsig@gva.es
|
||
32 | * www.gvsig.gva.es
|
||
33 | *
|
||
34 | * or
|
||
35 | *
|
||
36 | * IVER T.I. S.A
|
||
37 | * Salamanca 50
|
||
38 | * 46005 Valencia
|
||
39 | * Spain
|
||
40 | *
|
||
41 | * +34 963163400
|
||
42 | * dac@iver.es
|
||
43 | */
|
||
44 | /* CVS MESSAGES:
|
||
45 | *
|
||
46 | * $Id: SnapSimpleMCSweepLineIntersector.java 10627 2007-03-06 17:10:21Z caballero $
|
||
47 | * $Log$
|
||
48 | * Revision 1.4 2007-03-06 17:08:56 caballero
|
||
49 | * Exceptions
|
||
50 | *
|
||
51 | * Revision 1.3 2006/12/04 19:30:23 azabala
|
||
52 | * *** empty log message ***
|
||
53 | *
|
||
54 | * Revision 1.1 2006/10/05 19:20:57 azabala
|
||
55 | * first version in cvs
|
||
56 | *
|
||
57 | * Revision 1.1 2006/10/02 19:06:26 azabala
|
||
58 | * First version in CVS
|
||
59 | *
|
||
60 | *
|
||
61 | */
|
||
62 | package com.vividsolutions.jts.geomgraph.index; |
||
63 | |||
64 | import java.util.ArrayList; |
||
65 | import java.util.Collections; |
||
66 | import java.util.Iterator; |
||
67 | import java.util.List; |
||
68 | |||
69 | import com.vividsolutions.jts.geomgraph.Edge; |
||
70 | |||
71 | public class SnapSimpleMCSweepLineIntersector extends |
||
72 | SimpleMCSweepLineIntersector { |
||
73 | |||
74 | List events = new ArrayList(); |
||
75 | // statistics information
|
||
76 | int nOverlaps;
|
||
77 | |||
78 | |||
79 | public SnapSimpleMCSweepLineIntersector() {
|
||
80 | } |
||
81 | |||
82 | |||
83 | public void computeIntersections(List edges, |
||
84 | SegmentIntersector si, |
||
85 | boolean testAllSegments)
|
||
86 | { |
||
87 | if (testAllSegments)
|
||
88 | add(edges, null);
|
||
89 | else
|
||
90 | add(edges); |
||
91 | computeIntersections(si); |
||
92 | } |
||
93 | |||
94 | public void computeIntersections(List edges0, List edges1, SegmentIntersector si) |
||
95 | { |
||
96 | add(edges0, edges0); |
||
97 | add(edges1, edges1); |
||
98 | computeIntersections(si); |
||
99 | } |
||
100 | |||
101 | private void add(List edges) |
||
102 | { |
||
103 | for (Iterator i = edges.iterator(); i.hasNext(); ) { |
||
104 | Edge edge = (Edge) i.next(); |
||
105 | // edge is its own group
|
||
106 | add(edge, edge); |
||
107 | } |
||
108 | } |
||
109 | private void add(List edges, Object edgeSet) |
||
110 | { |
||
111 | for (Iterator i = edges.iterator(); i.hasNext(); ) { |
||
112 | Edge edge = (Edge) i.next(); |
||
113 | add(edge, edgeSet); |
||
114 | } |
||
115 | } |
||
116 | |||
117 | private void add(Edge edge, Object edgeSet) |
||
118 | { |
||
119 | MonotoneChainEdge mce = edge.getMonotoneChainEdge(); |
||
120 | int[] startIndex = mce.getStartIndexes(); |
||
121 | for (int i = 0; i < startIndex.length - 1; i++) { |
||
122 | MonotoneChain mc = new MonotoneChain(mce, i);
|
||
123 | SweepLineEvent insertEvent = new SweepLineEvent(edgeSet,
|
||
124 | mce.getMinX(i), |
||
125 | null, mc);
|
||
126 | events.add(insertEvent); |
||
127 | events.add(new SweepLineEvent(edgeSet, mce.getMaxX(i), insertEvent, mc));
|
||
128 | } |
||
129 | } |
||
130 | |||
131 | /**
|
||
132 | * Because Delete Events have a link to their corresponding Insert event,
|
||
133 | * it is possible to compute exactly the range of events which must be
|
||
134 | * compared to a given Insert event object.
|
||
135 | */
|
||
136 | private void prepareEvents() |
||
137 | { |
||
138 | Collections.sort(events);
|
||
139 | for (int i = 0; i < events.size(); i++ ) |
||
140 | { |
||
141 | SweepLineEvent ev = (SweepLineEvent) events.get(i); |
||
142 | if (ev.isDelete()) {
|
||
143 | ev.getInsertEvent().setDeleteEventIndex(i); |
||
144 | } |
||
145 | } |
||
146 | } |
||
147 | |||
148 | private void computeIntersections(SegmentIntersector si) |
||
149 | { |
||
150 | nOverlaps = 0;
|
||
151 | prepareEvents(); |
||
152 | |||
153 | for (int i = 0; i < events.size(); i++ ) |
||
154 | { |
||
155 | SweepLineEvent ev = (SweepLineEvent) events.get(i); |
||
156 | if (ev.isInsert()) {
|
||
157 | processOverlaps(i, ev.getDeleteEventIndex(), ev, si); |
||
158 | } |
||
159 | } |
||
160 | } |
||
161 | |||
162 | private void processOverlaps(int start, int end, SweepLineEvent ev0, SegmentIntersector si) |
||
163 | { |
||
164 | MonotoneChain mc0 = (MonotoneChain) ev0.getObject(); |
||
165 | /**
|
||
166 | * Since we might need to test for self-intersections,
|
||
167 | * include current insert event object in list of event objects to test.
|
||
168 | * Last index can be skipped, because it must be a Delete event.
|
||
169 | */
|
||
170 | for (int i = start; i < end; i++ ) { |
||
171 | SweepLineEvent ev1 = (SweepLineEvent) events.get(i); |
||
172 | if (ev1.isInsert()) {
|
||
173 | MonotoneChain mc1 = (MonotoneChain) ev1.getObject(); |
||
174 | // don't compare edges in same group
|
||
175 | // null group indicates that edges should be compared
|
||
176 | if (ev0.edgeSet == null || (ev0.edgeSet != ev1.edgeSet)) { |
||
177 | mc0.computeIntersections(mc1, si); |
||
178 | nOverlaps++; |
||
179 | } |
||
180 | } |
||
181 | } |
||
182 | } |
||
183 | |||
184 | } |