← Back to branch summary

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

« back to all changes in this revision

Viewing changes to src/com/vividsolutions/jts/operation/valid/SweeplineNestedRingTester.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/operation/valid/SweeplineNestedRingTester.java
 
1
 
 
2
/*
 
3
 * The JTS Topology Suite is a collection of Java classes that
 
4
 * implement the fundamental operations required to validate a given
 
5
 * geo-spatial data set to a known topological specification.
 
6
 *
 
7
 * Copyright (C) 2001 Vivid Solutions
 
8
 *
 
9
 * This library is free software; you can redistribute it and/or
 
10
 * modify it under the terms of the GNU Lesser General Public
 
11
 * License as published by the Free Software Foundation; either
 
12
 * version 2.1 of the License, or (at your option) any later version.
 
13
 *
 
14
 * This library is distributed in the hope that it will be useful,
 
15
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
16
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
17
 * Lesser General Public License for more details.
 
18
 *
 
19
 * You should have received a copy of the GNU Lesser General Public
 
20
 * License along with this library; if not, write to the Free Software
 
21
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
22
 *
 
23
 * For more information, contact:
 
24
 *
 
25
 *     Vivid Solutions
 
26
 *     Suite #1A
 
27
 *     2328 Government Street
 
28
 *     Victoria BC  V8T 5G5
 
29
 *     Canada
 
30
 *
 
31
 *     (250)385-6040
 
32
 *     www.vividsolutions.com
 
33
 */
 
34
package com.vividsolutions.jts.operation.valid;
 
35
 
 
36
import java.util.*;
 
37
import com.vividsolutions.jts.algorithm.*;
 
38
import com.vividsolutions.jts.geom.*;
 
39
import com.vividsolutions.jts.geomgraph.*;
 
40
import com.vividsolutions.jts.index.sweepline.*;
 
41
import com.vividsolutions.jts.util.*;
 
42
 
 
43
/**
 
44
 * Tests whether any of a set of {@link LinearRing}s are
 
45
 * nested inside another ring in the set, using a {@link SweepLineIndex}
 
46
 * index to speed up the comparisons.
 
47
 *
 
48
 * @version 1.6
 
49
 */
 
50
public class SweeplineNestedRingTester
 
51
{
 
52
 
 
53
  private final CGAlgorithms cga = new CGAlgorithms();
 
54
 
 
55
  private GeometryGraph graph;  // used to find non-node vertices
 
56
  private List rings = new ArrayList();
 
57
  private Envelope totalEnv = new Envelope();
 
58
  private SweepLineIndex sweepLine;
 
59
  private Coordinate nestedPt = null;
 
60
 
 
61
  public SweeplineNestedRingTester(GeometryGraph graph)
 
62
  {
 
63
    this.graph = graph;
 
64
  }
 
65
 
 
66
  public Coordinate getNestedPoint() { return nestedPt; }
 
67
 
 
68
  public void add(LinearRing ring)
 
69
  {
 
70
    rings.add(ring);
 
71
  }
 
72
 
 
73
  public boolean isNonNested()
 
74
  {
 
75
    buildIndex();
 
76
 
 
77
    OverlapAction action = new OverlapAction();
 
78
 
 
79
    sweepLine.computeOverlaps(action);
 
80
    return action.isNonNested;
 
81
  }
 
82
 
 
83
  private void buildIndex()
 
84
  {
 
85
    sweepLine = new SweepLineIndex();
 
86
 
 
87
    for (int i = 0; i < rings.size(); i++) {
 
88
      LinearRing ring = (LinearRing) rings.get(i);
 
89
      Envelope env = ring.getEnvelopeInternal();
 
90
      SweepLineInterval sweepInt = new SweepLineInterval(env.getMinX(), env.getMaxX(), ring);
 
91
      sweepLine.add(sweepInt);
 
92
    }
 
93
  }
 
94
 
 
95
  private boolean isInside(LinearRing innerRing, LinearRing searchRing)
 
96
  {
 
97
    Coordinate[] innerRingPts = innerRing.getCoordinates();
 
98
    Coordinate[] searchRingPts = searchRing.getCoordinates();
 
99
 
 
100
    if (! innerRing.getEnvelopeInternal().intersects(searchRing.getEnvelopeInternal()))
 
101
      return false;
 
102
 
 
103
    Coordinate innerRingPt = IsValidOp.findPtNotNode(innerRingPts, searchRing, graph);
 
104
    Assert.isTrue(innerRingPt != null, "Unable to find a ring point not a node of the search ring");
 
105
 
 
106
    boolean isInside = cga.isPointInRing(innerRingPt, searchRingPts);
 
107
    if (isInside) {
 
108
      nestedPt = innerRingPt;
 
109
      return true;
 
110
    }
 
111
    return false;
 
112
  }
 
113
 
 
114
 
 
115
  class OverlapAction
 
116
    implements SweepLineOverlapAction
 
117
  {
 
118
    boolean isNonNested = true;
 
119
 
 
120
  public void overlap(SweepLineInterval s0, SweepLineInterval s1)
 
121
  {
 
122
    LinearRing innerRing = (LinearRing) s0.getItem();
 
123
    LinearRing searchRing = (LinearRing) s1.getItem();
 
124
    if (innerRing == searchRing) return;
 
125
 
 
126
    if (isInside(innerRing, searchRing))
 
127
      isNonNested = false;
 
128
  }
 
129
 
 
130
  }
 
131
}