← Back to branch summary

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

« back to all changes in this revision

Viewing changes to src/com/vividsolutions/jts/index/chain/MonotoneChainBuilder.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/index/chain/MonotoneChainBuilder.java
 
1
 
 
2
 
 
3
/*
 
4
 * The JTS Topology Suite is a collection of Java classes that
 
5
 * implement the fundamental operations required to validate a given
 
6
 * geo-spatial data set to a known topological specification.
 
7
 *
 
8
 * Copyright (C) 2001 Vivid Solutions
 
9
 *
 
10
 * This library is free software; you can redistribute it and/or
 
11
 * modify it under the terms of the GNU Lesser General Public
 
12
 * License as published by the Free Software Foundation; either
 
13
 * version 2.1 of the License, or (at your option) any later version.
 
14
 *
 
15
 * This library is distributed in the hope that it will be useful,
 
16
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 
17
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 
18
 * Lesser General Public License for more details.
 
19
 *
 
20
 * You should have received a copy of the GNU Lesser General Public
 
21
 * License along with this library; if not, write to the Free Software
 
22
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
23
 *
 
24
 * For more information, contact:
 
25
 *
 
26
 *     Vivid Solutions
 
27
 *     Suite #1A
 
28
 *     2328 Government Street
 
29
 *     Victoria BC  V8T 5G5
 
30
 *     Canada
 
31
 *
 
32
 *     (250)385-6040
 
33
 *     www.vividsolutions.com
 
34
 */
 
35
package com.vividsolutions.jts.index.chain;
 
36
 
 
37
import java.util.*;
 
38
import com.vividsolutions.jts.geom.Coordinate;
 
39
import com.vividsolutions.jts.geomgraph.Quadrant;
 
40
 
 
41
/**
 
42
 * A MonotoneChainBuilder implements functions to determine the monotone chains
 
43
 * in a sequence of points.
 
44
 *
 
45
 * @version 1.6
 
46
 */
 
47
public class MonotoneChainBuilder {
 
48
 
 
49
  public static int[] toIntArray(List list)
 
50
  {
 
51
    int[] array = new int[list.size()];
 
52
    for (int i = 0; i < array.length; i++) {
 
53
      array[i] = ((Integer) list.get(i)).intValue();
 
54
    }
 
55
    return array;
 
56
  }
 
57
 
 
58
  public static List getChains(Coordinate[] pts)
 
59
  {
 
60
    return getChains(pts, null);
 
61
  }
 
62
 
 
63
  /**
 
64
   * Return a list of the {@link MonotoneChain}s
 
65
   * for the given list of coordinates.
 
66
   */
 
67
  public static List getChains(Coordinate[] pts, Object context)
 
68
  {
 
69
    List mcList = new ArrayList();
 
70
    int[] startIndex = getChainStartIndices(pts);
 
71
    for (int i = 0; i < startIndex.length - 1; i++) {
 
72
      MonotoneChain mc = new MonotoneChain(pts, startIndex[i], startIndex[i + 1], context);
 
73
      mcList.add(mc);
 
74
    }
 
75
    return mcList;
 
76
  }
 
77
 
 
78
  /**
 
79
   * Return an array containing lists of start/end indexes of the monotone chains
 
80
   * for the given list of coordinates.
 
81
   * The last entry in the array points to the end point of the point array,
 
82
   * for use as a sentinel.
 
83
   */
 
84
  public static int[] getChainStartIndices(Coordinate[] pts)
 
85
  {
 
86
    // find the startpoint (and endpoints) of all monotone chains in this edge
 
87
    int start = 0;
 
88
    List startIndexList = new ArrayList();
 
89
    startIndexList.add(new Integer(start));
 
90
    do {
 
91
      int last = findChainEnd(pts, start);
 
92
      startIndexList.add(new Integer(last));
 
93
      start = last;
 
94
    } while (start < pts.length - 1);
 
95
    // copy list to an array of ints, for efficiency
 
96
    int[] startIndex = toIntArray(startIndexList);
 
97
    return startIndex;
 
98
  }
 
99
 
 
100
  /**
 
101
   * @return the index of the last point in the monotone chain starting at <code>start</code>.
 
102
   */
 
103
  private static int findChainEnd(Coordinate[] pts, int start)
 
104
  {
 
105
    // determine quadrant for chain
 
106
    int chainQuad = Quadrant.quadrant(pts[start], pts[start + 1]);
 
107
    int last = start + 1;
 
108
    while (last < pts.length) {
 
109
      // compute quadrant for next possible segment in chain
 
110
      int quad = Quadrant.quadrant(pts[last - 1], pts[last]);
 
111
      if (quad != chainQuad) break;
 
112
      last++;
 
113
    }
 
114
    return last - 1;
 
115
  }
 
116
 
 
117
 
 
118
  public MonotoneChainBuilder() {
 
119
  }
 
120
}