lucene-java-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From r...@apache.org
Subject svn commit: r730067 [1/2] - in /lucene/java/trunk/contrib/spatial: ./ src/ src/java/ src/java/org/ src/java/org/apache/ src/java/org/apache/lucene/ src/java/org/apache/lucene/spatial/ src/java/org/apache/lucene/spatial/geometry/ src/java/org/apache/luc...
Date Tue, 30 Dec 2008 07:37:18 GMT
Author: ryan
Date: Mon Dec 29 23:37:17 2008
New Revision: 730067

URL: http://svn.apache.org/viewvc?rev=730067&view=rev
Log:
LUCENE-1387 -- adding locallucene as new spatial contrib package.

Added:
    lucene/java/trunk/contrib/spatial/
    lucene/java/trunk/contrib/spatial/build.xml
    lucene/java/trunk/contrib/spatial/pom.xml.template
    lucene/java/trunk/contrib/spatial/src/
    lucene/java/trunk/contrib/spatial/src/java/
    lucene/java/trunk/contrib/spatial/src/java/org/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/ISerialChainFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/NumberUtils.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/SerialChainFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/CartesianPoint.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/DistanceUnits.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FixedLatLng.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FloatLatLng.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/LatLng.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Geometry2D.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/IntersectCase.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LineSegment.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Point2D.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Rectangle.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Vector2D.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/BoundaryBoxFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianShapeFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceFilter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceHandler.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceQuery.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceSortSource.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/DistanceUtils.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/InvalidGeoException.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/Shape.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/projections/
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/projections/CartesianTierPlotter.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/projections/IProjector.java
    lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/projections/SinusoidalProjector.java
    lucene/java/trunk/contrib/spatial/src/test/
    lucene/java/trunk/contrib/spatial/src/test/org/
    lucene/java/trunk/contrib/spatial/src/test/org/apache/
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/DistanceCheck.java
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/PolyShape.java
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestCartesian.java
    lucene/java/trunk/contrib/spatial/src/test/org/apache/lucene/spatial/tier/TestDistance.java

Added: lucene/java/trunk/contrib/spatial/build.xml
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/build.xml?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/build.xml (added)
+++ lucene/java/trunk/contrib/spatial/build.xml Mon Dec 29 23:37:17 2008
@@ -0,0 +1,32 @@
+<?xml version="1.0"?>
+
+<!--
+    Licensed to the Apache Software Foundation (ASF) under one or more
+    contributor license agreements.  See the NOTICE file distributed with
+    this work for additional information regarding copyright ownership.
+    The ASF licenses this file to You under the Apache License, Version 2.0
+    the "License"); you may not use this file except in compliance with
+    the License.  You may obtain a copy of the License at
+ 
+        http://www.apache.org/licenses/LICENSE-2.0
+ 
+    Unless required by applicable law or agreed to in writing, software
+    distributed under the License is distributed on an "AS IS" BASIS,
+    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+    See the License for the specific language governing permissions and
+    limitations under the License.
+ -->
+
+<project name="spatial" default="default">
+
+  <description>
+    Lucene Spatial Indexing
+  </description>
+
+  <property name="javac.source" value="1.5" />
+  <property name="javac.target" value="1.5" />
+  
+  <import file="../contrib-build.xml"/>
+
+
+</project>

Added: lucene/java/trunk/contrib/spatial/pom.xml.template
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/pom.xml.template?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/pom.xml.template (added)
+++ lucene/java/trunk/contrib/spatial/pom.xml.template Mon Dec 29 23:37:17 2008
@@ -0,0 +1,50 @@
+<project xmlns="http://maven.apache.org/POM/4.0.0"
+         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
+         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
+
+  <!--
+    Licensed to the Apache Software Foundation (ASF) under one
+    or more contributor license agreements.  See the NOTICE file
+    distributed with this work for additional information
+    regarding copyright ownership.  The ASF licenses this file
+    to you under the Apache License, Version 2.0 (the
+    "License"); you may not use this file except in compliance
+    with the License.  You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+    Unless required by applicable law or agreed to in writing,
+    software distributed under the License is distributed on an
+    "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+    KIND, either express or implied.  See the License for the
+    specific language governing permissions and limitations
+    under the License.
+  -->
+
+  <modelVersion>4.0.0</modelVersion>
+  <parent>
+    <groupId>org.apache.lucene</groupId>
+    <artifactId>lucene-contrib</artifactId>
+    <version>@version@</version>
+  </parent>
+  <groupId>org.apache.lucene</groupId>
+  <artifactId>lucene-instantiated</artifactId>
+  <name>Lucene InstantiatedIndex</name>
+  <version>@version@</version>
+  <description>InstantiatedIndex, alternative RAM store for small corpora.</description>
+  <packaging>jar</packaging>
+
+  <build>
+    <plugins>
+      <plugin>
+        <groupId>org.apache.maven.plugins</groupId>
+        <artifactId>maven-compiler-plugin</artifactId>
+        <configuration>
+          <source>1.5</source>
+          <target>1.5</target>
+        </configuration>
+      </plugin>
+    </plugins>
+  </build>
+  
+</project>

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/ISerialChainFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/ISerialChainFilter.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/ISerialChainFilter.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/ISerialChainFilter.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,34 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial;
+
+import java.io.IOException;
+import java.util.BitSet;
+
+import org.apache.lucene.index.CorruptIndexException;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.Filter;
+
+/**
+ * Provide an optimized filter, by allowing the bitset from 
+ * previous filters in the bitset to be used in the next part of the chain.
+ * 
+ */
+public abstract class ISerialChainFilter extends Filter {
+  public abstract BitSet bits(IndexReader reader, BitSet bits) throws CorruptIndexException, IOException, Exception;
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/NumberUtils.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/NumberUtils.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/NumberUtils.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/NumberUtils.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,68 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial;
+
+/**
+ * TODO -- when solr moves NumberUtils to lucene, this should be redundant
+ * 
+ * This is a copy of solr's number utils with only the functions we use...
+ * 
+ * @deprecated will be replaced with lucene version of solr copy...
+ */
+@Deprecated
+public class NumberUtils {
+
+
+  public static String long2sortableStr(long val) {
+    char[] arr = new char[5];
+    long2sortableStr(val,arr,0);
+    return new String(arr,0,5);
+  }
+
+  public static String double2sortableStr(double val) {
+    long f = Double.doubleToRawLongBits(val);
+    if (f<0) f ^= 0x7fffffffffffffffL;
+    return long2sortableStr(f);
+  }
+
+  public static double SortableStr2double(String val) {
+    long f = SortableStr2long(val,0,6);
+    if (f<0) f ^= 0x7fffffffffffffffL;
+    return Double.longBitsToDouble(f);
+  }
+  
+  public static int long2sortableStr(long val, char[] out, int offset) {
+    val += Long.MIN_VALUE;
+    out[offset++] = (char)(val >>>60);
+    out[offset++] = (char)(val >>>45 & 0x7fff);
+    out[offset++] = (char)(val >>>30 & 0x7fff);
+    out[offset++] = (char)(val >>>15 & 0x7fff);
+    out[offset] = (char)(val & 0x7fff);
+    return 5;
+  }
+
+  public static long SortableStr2long(String sval, int offset, int len) {
+    long val = (long)(sval.charAt(offset++)) << 60;
+    val |= ((long)sval.charAt(offset++)) << 45;
+    val |= ((long)sval.charAt(offset++)) << 30;
+    val |= sval.charAt(offset++) << 15;
+    val |= sval.charAt(offset);
+    val -= Long.MIN_VALUE;
+    return val;
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/SerialChainFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/SerialChainFilter.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/SerialChainFilter.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/SerialChainFilter.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,199 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial;
+
+import java.io.IOException;
+import java.util.BitSet;
+
+import org.apache.lucene.index.CorruptIndexException;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.Filter;
+
+/**
+ * 
+ * Provide a serial chain filter, passing the bitset in with the
+ * index reader to each of the filters in an ordered fashion.
+ * 
+ * Based off chain filter, but will some improvements to allow a narrowed down
+ * filtering. Traditional filter required iteration through an IndexReader.
+ * 
+ * By implementing the ISerialChainFilter class, you can create a bits(IndexReader reader, BitSet bits)
+ * @see org.apache.lucene.spatial.ISerialChainFilter
+ * 
+ */
+public class SerialChainFilter extends Filter {
+
+  /**
+   * $Id: SerialChainFilter.java 136 2008-12-17 16:16:38Z ryantxu $
+   */
+  private static final long serialVersionUID = 1L;
+  private Filter chain[];
+  public static final int SERIALAND = 1;
+  public static final int SERIALOR = 2;
+  public static final int AND = 3;  // regular filters may be used first
+  public static final int OR = 4;    // regular filters may be used first
+  public static final int DEFAULT = SERIALOR;
+  
+  private int actionType[];
+  
+  public SerialChainFilter(Filter chain[]){
+    this.chain = chain;
+    this.actionType = new int[] {DEFAULT};
+  }
+  
+  public SerialChainFilter(Filter chain[], int actionType[]){
+    this.chain= chain;
+    this.actionType = actionType;
+  }
+  
+  /* (non-Javadoc)
+   * @see org.apache.lucene.search.Filter#bits(org.apache.lucene.index.IndexReader)
+   */
+  @Override
+  public BitSet bits(IndexReader reader) throws CorruptIndexException, IOException {
+    
+    BitSet bits = new BitSet(reader.maxDoc());
+    int chainSize = chain.length;
+    int actionSize = actionType.length;
+    int i = 0;
+    
+    /**
+     * taken from ChainedFilter, first and on an empty bitset results in 0
+     */
+    if (actionType[i] == AND){
+       try {
+        bits = (BitSet) chain[i].bits(reader).clone();
+      } catch (IOException e) {
+        // TODO Auto-generated catch block
+        e.printStackTrace();
+      }
+           ++i;
+    }
+    
+    for( ; i < chainSize; i++) {
+    
+      int action = (i < actionSize)? actionType[i]: DEFAULT;
+    
+      switch (action){
+      
+      case (SERIALAND):
+        try {
+            bits.and(((ISerialChainFilter) chain[i]).bits(reader, bits));
+          } catch (CorruptIndexException e) {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
+          } catch (IOException e) {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
+          } catch (Exception e) {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
+          }
+        break;
+      case (SERIALOR):
+        try {
+            bits.or(((ISerialChainFilter) chain[i]).bits(reader,bits));
+          } catch (Exception e) {
+            // TODO Auto-generated catch block
+            e.printStackTrace();
+          }
+        break;
+      case (AND):
+        bits.and(chain[i].bits(reader));
+        break;
+      case (OR):
+        bits.and(chain[i].bits(reader));
+        break;
+      }
+  
+    }
+    return bits;
+  }
+
+    /**
+   * @return the chain
+   */
+  Filter[] getChain() {
+    return chain;
+  }
+
+  /**
+   * @return the actionType
+   */
+  int[] getActionType() {
+    return actionType;
+  }
+
+  /** 
+   * Returns true if <code>o</code> is equal to this.
+   * 
+   * @see org.apache.lucene.search.RangeFilter#equals
+   */
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (!(o instanceof SerialChainFilter)) return false;
+    SerialChainFilter other = (SerialChainFilter) o;
+
+    if (this.chain.length != other.getChain().length ||
+      this.actionType.length != other.getActionType().length)
+      return false;
+    
+    for (int i = 0; i < this.chain.length; i++) {
+      if (this.actionType[i] != other.getActionType()[i]  ||
+        (!this.chain[i].equals(other.getChain()[i])))
+        return false;
+    }
+    return true;
+  }
+    
+  /** 
+   * Returns a hash code value for this object.
+   * 
+   * @see org.apache.lucene.search.RangeFilter#hashCode
+   */
+  @Override
+  public int hashCode() {
+    if (chain.length == 0)
+      return 0;
+
+    int h = chain[0].hashCode() ^ new Integer(actionType[0]).hashCode(); 
+    for (int i = 1; i < this.chain.length; i++) {
+      h ^= chain[i].hashCode();
+      h ^= new Integer(actionType[i]).hashCode();
+    }
+    return h;
+  }
+  
+  @Override
+  public String toString() {
+    StringBuffer buf = new StringBuffer();
+    buf.append("SerialChainFilter(");
+    for (int i = 0; i < chain.length; i++) {
+      switch(actionType[i]) {
+        case (SERIALAND): buf.append("SERIALAND"); break;
+        case (SERIALOR):  buf.append("SERIALOR");  break;
+        case (AND):       buf.append("AND");       break;
+        case (OR):        buf.append("OR");        break;
+        default:          buf.append(actionType[i]);
+      }
+      buf.append(" " + chain[i].toString() + " ");
+    }
+    return buf.toString().trim() + ")";
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/CartesianPoint.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/CartesianPoint.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/CartesianPoint.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/CartesianPoint.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,56 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry;
+
+/**
+ * Represents lat/lngs as fixed point numbers translated so that all
+ * world coordinates are in the first quadrant.  The same fixed point
+ * scale as is used for FixedLatLng is employed.
+ */
+public class CartesianPoint {
+  private int x;
+  private int y;
+  
+  public CartesianPoint(int x, int y) {
+    this.x=x;
+    this.y=y;
+  }
+  
+  public int getX() {
+    return x;
+  }
+  
+  public int getY() {
+    return y;
+  }
+  
+  @Override
+  public String toString() {
+    return "Point(" + x + "," + y + ")";
+  }
+
+  /**
+   * Return a new point translated in the x and y dimensions
+   * @param i
+   * @param translation
+   * @return
+   */
+  public CartesianPoint translate(int deltaX, int deltaY) {
+    return new CartesianPoint(this.x+deltaX, this.y+deltaY);
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/DistanceUnits.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/DistanceUnits.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/DistanceUnits.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/DistanceUnits.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,23 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry;
+
+public enum DistanceUnits {
+  MILES,
+  KILOMETERS;
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FixedLatLng.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FixedLatLng.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FixedLatLng.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FixedLatLng.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,135 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry;
+
+public class FixedLatLng extends LatLng {
+  public static final double SCALE_FACTOR=1000000;
+  public static final int SCALE_FACTOR_INT=1000000;
+  
+  private int lat, lng;
+  private boolean normalized;
+  
+  public FixedLatLng(int lat, int lng) {
+    setLat(lat);
+    setLng(lng);
+  }
+  
+  public FixedLatLng(LatLng ll) {
+    this.lat=ll.getFixedLat();
+    this.lng=ll.getFixedLng();
+  }
+  
+  protected void setLat(int lat) {
+    if (lat>90*SCALE_FACTOR || lat<-90*SCALE_FACTOR) {
+      throw new IllegalArgumentException("Illegal lattitude");
+    }
+    this.lat=lat;
+  }
+
+  protected void setLng(int lng) {
+    this.lng=lng;
+  }
+  
+  @Override
+  public boolean equals(LatLng other) {
+    return lat==other.getFixedLat() && lng==other.getFixedLng();
+  }
+  
+  public static double fixedToDouble(int fixed) {
+    return (fixed)/SCALE_FACTOR;
+  }
+  
+  public static int doubleToFixed(double d) {
+    return (int)(d*SCALE_FACTOR);
+  }
+  
+  @Override
+  public LatLng copy() {
+    return new FixedLatLng(this);
+  }
+
+  @Override
+  public int getFixedLat() {
+    return lat;
+  }
+
+  @Override
+  public int getFixedLng() {
+    return lng;
+  }
+
+  @Override
+  public double getLat() {
+    return fixedToDouble(lat);
+  }
+
+  @Override
+  public double getLng() {
+    return fixedToDouble(lng);
+  }
+
+  @Override
+  public boolean isFixedPoint() {
+    return true;
+  }
+
+  @Override
+  public FixedLatLng toFixed() {
+    return this;
+  }
+
+  @Override
+  public FloatLatLng toFloat() {
+    return new FloatLatLng(this);
+  }
+
+  @Override
+  public boolean isNormalized() {
+    return 
+      normalized || (
+          (lng>=-180*SCALE_FACTOR_INT) &&
+          (lng<=180*SCALE_FACTOR_INT)
+          );
+  }
+
+  @Override
+  public LatLng normalize() {
+    if (isNormalized()) return this;
+    
+    int delta=0;
+    if (lng<0) delta=360*SCALE_FACTOR_INT;
+    if (lng>=0) delta=-360*SCALE_FACTOR_INT;
+    
+    int newLng=lng;
+    while (newLng<=-180*SCALE_FACTOR_INT || newLng>=180*SCALE_FACTOR_INT) {
+      newLng+=delta;
+    }
+    
+    FixedLatLng ret=new FixedLatLng(lat, newLng);
+    ret.normalized=true;
+    return ret;
+  }
+  
+  @Override
+  public LatLng calculateMidpoint(LatLng other) {
+    return new FixedLatLng(
+        (lat+other.getFixedLat())/2,
+        (lng+other.getFixedLng())/2);
+  }
+
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FloatLatLng.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FloatLatLng.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FloatLatLng.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/FloatLatLng.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,116 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry;
+
+public class FloatLatLng extends LatLng {
+  private double lat;
+  private double lng;
+  private boolean normalized;
+  
+  public FloatLatLng(double lat, double lng) {
+    if (lat>90.0 || lat<-90.0) throw new IllegalArgumentException("Illegal lattitude value " + lat);
+    this.lat=lat;
+    this.lng=lng;
+  }
+  
+  public FloatLatLng(LatLng ll) {
+    this.lat=ll.getLat();
+    this.lng=ll.getLng();
+  }
+  
+  @Override
+  public boolean equals(LatLng other) {
+    return lat==other.getLat() && lng==other.getLng();
+  }
+
+  
+  @Override
+  public LatLng copy() {
+    return new FloatLatLng(this);
+  }
+
+  @Override
+  public int getFixedLat() {
+    return FixedLatLng.doubleToFixed(this.lat);
+  }
+
+  @Override
+  public int getFixedLng() {
+    return FixedLatLng.doubleToFixed(this.lng);
+  }
+
+  @Override
+  public double getLat() {
+    return this.lat;
+  }
+
+  @Override
+  public double getLng() {
+    return this.lng;
+  }
+
+  @Override
+  public boolean isFixedPoint() {
+    return false;
+  }
+
+  @Override
+  public FixedLatLng toFixed() {
+    return new FixedLatLng(this);
+  }
+
+  @Override
+  public FloatLatLng toFloat() {
+    return this;
+  }
+  
+  @Override
+  public boolean isNormalized() {
+    return 
+      normalized || (
+          (lng>=-180) &&
+          (lng<=180)
+          );
+  }
+
+  @Override
+  public LatLng normalize() {
+    if (isNormalized()) return this;
+    
+    double delta=0;
+    if (lng<0) delta=360;
+    if (lng>=0) delta=-360;
+    
+    double newLng=lng;
+    while (newLng<=-180 || newLng>=180) {
+      newLng+=delta;
+    }
+    
+    FloatLatLng ret=new FloatLatLng(lat, newLng);
+    ret.normalized=true;
+    return ret;
+  }
+
+  @Override
+  public LatLng calculateMidpoint(LatLng other) {
+    return new FloatLatLng(
+        (lat+other.getLat())/2.0,
+        (lng+other.getLng())/2.0);
+  }
+
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/LatLng.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/LatLng.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/LatLng.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/LatLng.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,164 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry;
+
+
+/**
+ * Abstract base lat-lng class which can manipulate fixed point or floating
+ * point based coordinates. Instances are immutable.
+ * 
+ * @see FixedLatLngTest
+ * @see FloatLatLng
+ * 
+ */
+public abstract class LatLng {
+
+  public abstract boolean isNormalized();
+
+  public abstract boolean isFixedPoint();
+
+  public abstract LatLng normalize();
+
+  public abstract int getFixedLat();
+
+  public abstract int getFixedLng();
+
+  public abstract double getLat();
+
+  public abstract double getLng();
+
+  public abstract LatLng copy();
+
+  public abstract FixedLatLng toFixed();
+
+  public abstract FloatLatLng toFloat();
+  
+  public abstract boolean equals(LatLng other);
+
+  @Override
+  public boolean equals(Object other) {
+    if (!(other instanceof LatLng)) return false;
+    return equals((LatLng)other);
+  }
+  
+  /**
+   * Convert the lat/lng into the cartesian coordinate plane such that all
+   * world coordinates are represented in the first quadrant.
+   * The x dimension corresponds to latitude and y corresponds to longitude.
+   * The translation starts with the normalized latlng and adds 180 to the latitude and 
+   * 90 to the longitude (subject to fixed point scaling).
+   * 
+   * @return
+   */
+  public CartesianPoint toCartesian() {
+    LatLng ll=normalize();
+    
+    int lat=ll.getFixedLat();
+    int lng=ll.getFixedLng();
+    
+    return new CartesianPoint(
+        lng+180*FixedLatLng.SCALE_FACTOR_INT,
+        lat+90*FixedLatLng.SCALE_FACTOR_INT
+    );
+  }
+  
+  /**
+   * The inverse of toCartesian().  Always returns a FixedLatLng.
+   * @param pt
+   * @return
+   */
+  public static LatLng fromCartesian(CartesianPoint pt) {
+    int lat=pt.getY() - 90 * FixedLatLng.SCALE_FACTOR_INT;
+    int lng=pt.getX() - 180 * FixedLatLng.SCALE_FACTOR_INT;
+    
+    return new FixedLatLng(lat, lng);
+  }
+  
+  /**
+   * Calculates the distance between two lat/lng's in miles.
+   * Imported from mq java client.
+   * 
+   * @param ll2
+   *            Second lat,lng position to calculate distance to.
+   * 
+   * @return Returns the distance in miles.
+   */
+  public double arcDistance(LatLng ll2) {
+    return arcDistance(ll2, DistanceUnits.MILES);
+  }
+
+  /**
+   * Calculates the distance between two lat/lng's in miles or meters.
+   * Imported from mq java client.  Variable references changed to match.
+   * 
+   * @param ll2
+   *            Second lat,lng position to calculate distance to.
+   * @param lUnits
+   *            Units to calculate distace, defaults to miles
+   * 
+   * @return Returns the distance in meters or miles.
+   */
+  public double arcDistance(LatLng ll2, DistanceUnits lUnits) {
+    LatLng ll1 = normalize();
+    ll2 = ll2.normalize();
+
+    double lat1 = ll1.getLat(), lng1 = ll1.getLng();
+    double lat2 = ll2.getLat(), lng2 = ll2.getLng();
+
+    // Check for same position
+    if (lat1 == lat2 && lng1 == lng2)
+      return 0.0;
+
+    // Get the m_dLongitude diffeernce. Don't need to worry about
+    // crossing 180 since cos(x) = cos(-x)
+    double dLon = lng2 - lng1;
+
+    double a = radians(90.0 - lat1);
+    double c = radians(90.0 - lat2);
+    double cosB = (Math.cos(a) * Math.cos(c))
+        + (Math.sin(a) * Math.sin(c) * Math.cos(radians(dLon)));
+
+    double radius = (lUnits == DistanceUnits.MILES) ? 3963.205/* MILERADIUSOFEARTH */
+    : 6378.160187/* KMRADIUSOFEARTH */;
+
+    // Find angle subtended (with some bounds checking) in radians and
+    // multiply by earth radius to find the arc distance
+    if (cosB < -1.0)
+      return 3.14159265358979323846/* PI */* radius;
+    else if (cosB >= 1.0)
+      return 0;
+    else
+      return Math.acos(cosB) * radius;
+  }
+
+  private double radians(double a) {
+    return a * 0.01745329251994;
+  }
+
+  @Override
+  public String toString() {
+    return "[" + getLat() + "," + getLng() + "]";
+  }
+
+  /**
+   * Calculate the midpoint between this point an another.  Respects fixed vs floating point
+   * @param other
+   * @return
+   */
+  public abstract LatLng calculateMidpoint(LatLng other);
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/DistanceApproximation.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,118 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+/**
+ * Imported from mq java client.  No changes made.
+ */
+public class DistanceApproximation
+{
+  private double m_testLat;
+  private double m_testLng;
+  private double m_mpd;
+  private static final double m_milesPerLngDeg[]={
+     69.170976f, 69.160441f, 69.128838f, 69.076177f, 69.002475f,
+     68.907753f, 68.792041f, 68.655373f, 68.497792f, 68.319345f,
+     68.120088f, 67.900079f, 67.659387f, 67.398085f, 67.116253f,
+     66.813976f, 66.491346f, 66.148462f, 65.785428f, 65.402355f,
+     64.999359f, 64.576564f, 64.134098f, 63.672096f, 63.190698f,
+     62.690052f, 62.170310f, 61.631630f, 61.074176f, 60.498118f,
+     59.903632f, 59.290899f, 58.660106f, 58.011443f, 57.345111f,
+     56.661310f, 55.960250f, 55.242144f, 54.507211f, 53.755675f,
+     52.987764f, 52.203713f, 51.403761f, 50.588151f, 49.757131f,
+     48.910956f, 48.049882f, 47.174172f, 46.284093f, 45.379915f,
+     44.461915f, 43.530372f, 42.585570f, 41.627796f, 40.657342f,
+     39.674504f, 38.679582f, 37.672877f, 36.654698f, 35.625354f,
+     34.585159f, 33.534429f, 32.473485f, 31.402650f, 30.322249f,
+     29.232613f, 28.134073f, 27.026963f, 25.911621f, 24.788387f,
+     23.657602f, 22.519612f, 21.374762f, 20.223401f, 19.065881f,
+     17.902554f, 16.733774f, 15.559897f, 14.381280f, 13.198283f,
+     12.011266f, 10.820591f,  9.626619f,  8.429716f,  7.230245f,
+      6.028572f,  4.825062f,  3.620083f,  2.414002f,  1.207185f,
+      1.000000f};
+
+  public static final double MILES_PER_LATITUDE   = 69.170976f;
+  public static final double KILOMETERS_PER_MILE  = 1.609347f;
+
+
+  public DistanceApproximation()
+  {
+  }
+
+  public void setTestPoint(double lat, double lng)
+  {
+    m_testLat = lat;
+    m_testLng = lng;
+    m_mpd     = m_milesPerLngDeg[(int)(Math.abs(lat) + 0.5f)];
+  }
+
+  // Approximate arc distance between 2 lat,lng positions using miles per
+  //    latitude and longitude degree
+  public double getDistanceSq(double lat, double lng)
+  {
+    double latMiles = (lat - m_testLat) * MILES_PER_LATITUDE;
+
+    // Approximate longitude miles using the miles per degree assuming the
+    //    middle latitude/longitude.  This is less accurate at high (near
+    //    polar) latitudes but no road network is present at the poles!
+    //    If we ever have any roads crossing the international date we will
+    //    have to worry about that case.
+    double lngMiles = (lng - m_testLng) * m_mpd;
+
+     // Find the squared distance by the Pythagorean theorem (without sqrt)
+    return (latMiles * latMiles + lngMiles * lngMiles);
+  }
+
+  // Approximate arc distance between a segment (with lat,lng endpoints) and
+  //    the test position
+  public double getDistanceSq(double lat1, double lng1, double lat2, double lng2)
+  {
+     // Check if lat1,lng1 is closest point.  Construct a vector from point1
+     //    to point2 (v1) and another from point 1 to the test point (v2).
+     //    If dot product is negative then point 1 is the closest point
+     double v1y = lat2 - lat1;
+     double v1x = lng2 - lng1;
+     double v2y = m_testLat - lat1;
+     double v2x = m_testLng - lng1;
+     double dot = v1x * v2x + v1y * v2y;
+     if (dot <= 0.0f)
+        return getDistanceSq(lat1, lng1);
+
+     // Get the component of vector v2 along v1.  If component is greater
+     //    than 1 then the endpoint is the closest point.
+     double c = dot / (v1x * v1x + v1y * v1y);
+     if (c >= 1.0f)
+        return getDistanceSq(lat2, lng2);
+
+     // Since we are working io lat,lng space we need to find the point
+     //    along p1->p2 such that q->pt is perpendicular to p1->p2.  We
+     //    then find the distance squared between Q and pt.
+     return getDistanceSq((lat1 + v1y * c), (lng1 + v1x * c));
+  }
+
+  // Return the number of miles per degree of longitude
+  public static double getMilesPerLngDeg(double lat)
+  {
+     return (Math.abs(lat) <= 90.0) ? m_milesPerLngDeg[(int)(Math.abs(lat) + 0.5f)] : 69.170976f;
+  }
+  
+  public static double getMilesPerLatDeg() {
+    return MILES_PER_LATITUDE;
+  }
+}
+

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Ellipse.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,233 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+
+/**
+ * Ellipse shape. From C++ gl.
+ */
+public class Ellipse implements Geometry2D {
+  private Point2D center;
+
+  /**
+   * Half length of major axis
+   */
+  private double a;
+
+  /**
+   * Half length of minor axis
+   */
+  private double b;
+
+  private double k1, k2, k3;
+
+  /**
+   * sin of rotation angle
+   */
+  private double s;
+
+  /**
+   * cos of rotation angle
+   */
+  private double c;
+
+  public Ellipse() {
+    center = new Point2D(0, 0);
+  }
+
+  private double SQR(double d) {
+    return d * d;
+  }
+
+  /**
+   * Constructor given bounding rectangle and a rotation.
+   * 
+   * @param
+   * @param
+   */
+  public Ellipse(Point2D p1, Point2D p2, double angle) {
+    center = new Point2D();
+
+    // Set the center
+    center.x((p1.x() + p2.x()) * 0.5f);
+    center.y((p1.y() + p2.y()) * 0.5f);
+
+    // Find sin and cos of the angle
+    double angleRad = Math.toRadians(angle);
+    c = Math.cos(angleRad);
+    s = Math.sin(angleRad);
+
+    // Find the half lengths of the semi-major and semi-minor axes
+    double dx = Math.abs(p2.x() - p1.x()) * 0.5;
+    double dy = Math.abs(p2.y() - p1.y()) * 0.5;
+    if (dx >= dy) {
+      a = dx;
+      b = dy;
+    } else {
+      a = dy;
+      b = dx;
+    }
+
+    // Find k1, k2, k3 - define when a point x,y is on the ellipse
+    k1 = SQR(c / a) + SQR(s / b);
+    k2 = 2 * s * c * ((1 / SQR(a)) - (1 / SQR(b)));
+    k3 = SQR(s / a) + SQR(c / b);
+  }
+
+  /**
+   * Determines if a line segment intersects the ellipse and if so finds the
+   * point(s) of intersection.
+   * 
+   * @param seg
+   *            Line segment to test for intersection
+   * @param pt0
+   *            OUT - intersection point (if it exists)
+   * @param pt1
+   *            OUT - second intersection point (if it exists)
+   * 
+   * @return Returns the number of intersection points (0, 1, or 2).
+   */
+  public int intersect(LineSegment seg, Point2D pt0, Point2D pt1) {
+    if (pt0 == null)
+      pt0 = new Point2D();
+    if (pt1 == null)
+      pt1 = new Point2D();
+
+    // Solution is found by paramterizing the line segment and
+    // substituting those values into the ellipse equation.
+    // Results in a quadratic equation.
+    double x1 = center.x();
+    double y1 = center.y();
+    double u1 = seg.A.x();
+    double v1 = seg.A.y();
+    double u2 = seg.B.x();
+    double v2 = seg.B.y();
+    double dx = u2 - u1;
+    double dy = v2 - v1;
+    double q0 = k1 * SQR(u1 - x1) + k2 * (u1 - x1) * (v1 - y1) + k3
+        * SQR(v1 - y1) - 1;
+    double q1 = (2 * k1 * dx * (u1 - x1)) + (k2 * dx * (v1 - y1))
+        + (k2 * dy * (u1 - x1)) + (2 * k3 * dy * (v1 - y1));
+    double q2 = (k1 * SQR(dx)) + (k2 * dx * dy) + (k3 * SQR(dy));
+
+    // Compare q1^2 to 4*q0*q2 to see how quadratic solves
+    double d = SQR(q1) - (4 * q0 * q2);
+    if (d < 0) {
+      // Roots are complex valued. Line containing the segment does
+      // not intersect the ellipse
+      return 0;
+    }
+
+    if (d == 0) {
+      // One real-valued root - line is tangent to the ellipse
+      double t = -q1 / (2 * q2);
+      if (0 <= t && t <= 1) {
+        // Intersection occurs along line segment
+        pt0.x(u1 + t * dx);
+        pt0.y(v1 + t * dy);
+        return 1;
+      } else
+        return 0;
+    } else {
+      // Two distinct real-valued roots. Solve for the roots and see if
+      // they fall along the line segment
+      int n = 0;
+      double q = Math.sqrt(d);
+      double t = (-q1 - q) / (2 * q2);
+      if (0 <= t && t <= 1) {
+        // Intersection occurs along line segment
+        pt0.x(u1 + t * dx);
+        pt0.y(v1 + t * dy);
+        n++;
+      }
+
+      // 2nd root
+      t = (-q1 + q) / (2 * q2);
+      if (0 <= t && t <= 1) {
+        if (n == 0) {
+          pt0.x(u1 + t * dx);
+          pt0.y(v1 + t * dy);
+          n++;
+        } else {
+          pt1.x(u1 + t * dx);
+          pt1.y(v1 + t * dy);
+          n++;
+        }
+      }
+      return n;
+    }
+  }
+
+  public IntersectCase intersect(Rectangle r) {
+    // Test if all 4 corners of the rectangle are inside the ellipse
+    Point2D ul = new Point2D(r.MinPt().x(), r.MaxPt().y());
+    Point2D ur = new Point2D(r.MaxPt().x(), r.MaxPt().y());
+    Point2D ll = new Point2D(r.MinPt().x(), r.MinPt().y());
+    Point2D lr = new Point2D(r.MaxPt().x(), r.MinPt().y());
+    if (contains(ul) && contains(ur) && contains(ll) && contains(lr))
+      return IntersectCase.CONTAINS;
+
+    // Test if any of the rectangle edges intersect
+    Point2D pt0 = new Point2D(), pt1 = new Point2D();
+    LineSegment bottom = new LineSegment(ll, lr);
+    if (intersect(bottom, pt0, pt1) > 0)
+      return IntersectCase.INTERSECTS;
+
+    LineSegment top = new LineSegment(ul, ur);
+    if (intersect(top, pt0, pt1) > 0)
+      return IntersectCase.INTERSECTS;
+
+    LineSegment left = new LineSegment(ll, ul);
+    if (intersect(left, pt0, pt1) > 0)
+      return IntersectCase.INTERSECTS;
+
+    LineSegment right = new LineSegment(lr, ur);
+    if (intersect(right, pt0, pt1) > 0)
+      return IntersectCase.INTERSECTS;
+
+    // Ellipse does not intersect any edge : since the case for the ellipse
+    // containing the rectangle was considered above then if the center
+    // is inside the ellipse is fully inside and if center is outside
+    // the ellipse is fully outside
+    return (r.contains(center)) ? IntersectCase.WITHIN
+        : IntersectCase.OUTSIDE;
+  }
+
+  public double area() {
+    throw new UnsupportedOperationException();
+  }
+
+  public Point2D centroid() {
+    throw new UnsupportedOperationException();
+  }
+
+  public boolean contains(Point2D pt) {
+    // Plug in equation for ellipse, If evaluates to <= 0 then the
+    // point is in or on the ellipse.
+    double dx = pt.x() - center.x();
+    double dy = pt.y() - center.y();
+    double eq=(((k1 * SQR(dx)) + (k2 * dx * dy) + (k3 * SQR(dy)) - 1));
+    
+    return eq<=0;
+  }
+
+  public void translate(Vector2D v) {
+    throw new UnsupportedOperationException();
+  }
+
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Geometry2D.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Geometry2D.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Geometry2D.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Geometry2D.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,57 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+
+/**
+ * Common set of operations available on 2d shapes.
+ */
+public interface Geometry2D {
+  /**
+   * Translate according to the vector
+   * @param v
+   */
+  public void translate(Vector2D v);
+  
+  /**
+   * Does the shape contain the given point
+   * @param p
+   * @return
+   */
+  public boolean contains(Point2D p);
+  
+  /**
+   * Return the area
+   * @return
+   */
+  public double area();
+  
+  /**
+   * Return the centroid
+   * @return
+   */
+  public Point2D centroid();
+  
+  /**
+   * Returns information about how this shape intersects the given rectangle
+   * @param r
+   * @return
+   */
+  public IntersectCase intersect(Rectangle r);
+
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/IntersectCase.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/IntersectCase.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/IntersectCase.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/IntersectCase.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,25 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+public enum IntersectCase {
+  WITHIN,
+  CONTAINS,
+  OUTSIDE,
+  INTERSECTS;
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LLRect.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,105 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+import org.apache.lucene.spatial.geometry.FloatLatLng;
+import org.apache.lucene.spatial.geometry.LatLng;
+
+
+
+/**
+ * Lat-long rect.  Instances are mutable.
+ */
+public class LLRect {
+  private LatLng ll, ur;
+  
+  public LLRect(LatLng ll, LatLng ur) {
+    this.ll=ll;
+    this.ur=ur;
+  }
+  
+  public LLRect(LLRect other) {
+    this.ll=other.ll;
+    this.ur=other.ur;
+  }
+  
+  /**
+   * Return the area in units of lat-lng squared.  This is a contrived unit
+   * that only has value when comparing to something else.
+   * @return
+   */
+  public double area() {
+    return Math.abs((ll.getLat()-ur.getLat()) * (ll.getLng()-ur.getLng()));
+  }
+
+  public LatLng getLowerLeft() {
+    return ll;
+  }
+  
+  public LatLng getUpperRight() {
+    return ur;
+  }
+  
+  @Override
+  public boolean equals(Object otherObj) {
+    if (!(otherObj instanceof LLRect)) return false;
+    return equals((LLRect)otherObj);
+  }
+  
+  public boolean equals(LLRect other) {
+    return getLowerLeft().equals(other.getLowerLeft()) && getUpperRight().equals(other.getUpperRight());
+  }
+  
+  @Override
+  public String toString() {
+    return "{" + ll + ", " + ur + "}";
+  }
+
+  public LatLng getMidpoint() {
+    return ll.calculateMidpoint(ur);
+  }
+
+  /**
+   * Approximates a box centered at the given point with the given width and height in miles.
+   * @param center
+   * @param widthMi
+   * @param heightMi
+   * @return
+   */
+  public static LLRect createBox(LatLng center, double widthMi, double heightMi) {
+    double miplatdeg=DistanceApproximation.getMilesPerLngDeg(center.getLat());
+    double miplngdeg=DistanceApproximation.getMilesPerLatDeg();
+    
+    double lngDelta=(widthMi/2)/miplngdeg;
+    double latDelta=(heightMi/2)/miplatdeg;
+    
+    // TODO: Prob only works in northern hemisphere?
+    LatLng ll=new FloatLatLng(center.getLat()-latDelta, center.getLng()-lngDelta);
+    LatLng ur=new FloatLatLng(center.getLat()+latDelta, center.getLng()+lngDelta);
+    
+    return new LLRect(ll, ur);
+  }
+  
+  /**
+   * Returns a rectangle shape for the bounding box
+   * @return
+   */
+  public Rectangle toRectangle() {
+    return new Rectangle(ll.getLng(), ll.getLat(), ur.getLng(), ur.getLat());
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LineSegment.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LineSegment.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LineSegment.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/LineSegment.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,81 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+
+/**
+ * 2d line segment.
+ */
+public class LineSegment {
+  public final Point2D A = new Point2D();
+  public final Point2D B = new Point2D();
+
+  public LineSegment() {
+    A.set(0, 0);
+    B.set(0, 0);
+  }
+
+  public LineSegment(Point2D p1, Point2D p2) {
+    A.set(p1);
+    B.set(p2);
+  }
+
+  /**
+   * Finds the distance of a specified point from the line segment and the
+   * closest point on the segement to the specified point.
+   * 
+   * @param P
+   *            Test point.
+   * @param closestPt
+   *            (Return) Closest point on the segment to c.
+   * 
+   * @return Returns the distance from P to the closest point on the segment.
+   */
+  public double distance(Point2D P, Point2D /* out */closestPt) {
+    if (closestPt == null)
+      closestPt = new Point2D();
+
+    // Construct vector v (AB) and w (AP)
+    Vector2D v = new Vector2D(A, B);
+    Vector2D w = new Vector2D(A, P);
+
+    // Numerator of the component of w onto v. If <= 0 then A
+    // is the closest point. By separating into the numerator
+    // and denominator of the component we avoid a division unless
+    // it is necessary.
+    double n = w.dot(v);
+    if (n <= 0.0f) {
+      closestPt.set(A);
+      return w.norm();
+    }
+
+    // Get the denominator of the component. If the component >= 1
+    // (d <= n) then point B is the closest point
+    double d = v.dot(v);
+    if (d <= n) {
+      closestPt.set(B);
+      return new Vector2D(B, P).norm();
+    }
+
+    // Closest point is along the segment. The point is the projection of
+    // w onto v.
+    closestPt.set(v.mult(n / d));
+    closestPt.add(A);
+    return new Vector2D(closestPt, P).norm();
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Point2D.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Point2D.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Point2D.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Point2D.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,116 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+
+/**
+ * Point class.  This type is mutable.
+ */
+public class Point2D {
+  private double x;
+  private double y;
+  
+  public Point2D(double x, double y) {
+    this.x=x;
+    this.y=y;
+  }
+  
+  public Point2D() {
+    this.x=0;
+    this.y=0;
+  }
+  
+  public Point2D(Point2D other) {
+    this.x=other.x;
+    this.y=other.y;
+  }
+  
+  @Override
+  public String toString() {
+    return "(" + x + "," + y + ")";
+  }
+  
+  public double getX() {
+    return x;
+  }
+  
+  public double getY() {
+    return y;
+  }
+  
+  public double x() {
+    return x;
+  }
+
+  public double y() {
+    return y;
+  }
+
+  public void x(double x) {
+    this.x=x;
+  }
+
+  public void y(double y) {
+    this.y=y;
+  }
+
+  public void setX(double x) {
+    this.x = x;
+  }
+  
+  public void setY(double y) {
+    this.y = y;
+  }
+  
+  public void set(double x, double y) {
+    this.x=x;
+    this.y=y;
+  }
+
+  public boolean equals(Point2D other) {
+    return other!=null && x==other.x && y==other.y;
+  }
+  
+  @Override
+  public boolean equals(Object other) {
+    if (!(other instanceof Point2D)) return false;
+    return equals((Point2D)other);
+  }
+
+  public void add(Vector2D v) {
+    this.x+=v.getX();
+    this.y+=v.getY();
+  }
+
+  public void set(Point2D p1) {
+    this.x=p1.getX();
+    this.y=p1.getY();
+  }
+
+  public void add(Point2D a) {
+    this.x+=a.getX();
+    this.y+=a.getY();
+  }
+
+  public void set(Vector2D v) {
+    this.x=v.getX();
+    this.y=v.getY();
+  }
+  
+  
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Rectangle.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Rectangle.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Rectangle.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Rectangle.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,103 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+
+/**
+ * Rectangle shape.  
+ */
+public class Rectangle implements Geometry2D {
+  private Point2D ptMin, ptMax;
+  
+  public Rectangle() {
+    ptMin=new Point2D(-1, 1);
+    ptMax=new Point2D(1, 1);
+  }
+  
+  public Rectangle(Point2D ptMin, Point2D ptMax) {
+    this.ptMin=new Point2D(ptMin);
+    this.ptMax=new Point2D(ptMax);
+  }
+  
+  public Rectangle(double x1, double y1, double x2, double y2) {
+    set(x1, y1, x2, y2);
+  }
+
+  @Override
+  public String toString() {
+    return "[" + ptMin + "," + ptMax + "]";
+  }
+  
+  private void set(double x1, double y1, double x2, double y2) {
+    this.ptMin=new Point2D(Math.min(x1, x2), Math.min(y1, y2));
+    this.ptMax=new Point2D(Math.max(x1, x2), Math.max(y1, y2));
+  }
+  
+  public boolean equals(Rectangle other) {
+    return other.ptMin.equals(ptMin) && other.ptMax.equals(ptMax);
+  }
+  
+  @Override
+  public boolean equals(Object other) {
+    if (!(other instanceof Rectangle)) return false;
+    return equals((Rectangle)other);
+  }
+  
+  public double area() {
+    return (ptMax.getX() - ptMin.getX()) * (ptMax.getY() - ptMin.getY());
+  }
+
+  public Point2D centroid() {
+    return new Point2D( (ptMin.getX() + ptMax.getX()) / 2,
+                  (ptMin.getY() + ptMax.getY()) / 2);
+  }
+
+  public boolean contains(Point2D p) {
+    return p.getX() >= ptMin.getX() && 
+      p.getX() <= ptMax.getX() &&
+      p.getY() >= ptMin.getY() &&
+      p.getY() <= ptMax.getY();
+  }
+
+  public void translate(Vector2D v) {
+    ptMin.add(v);
+    ptMax.add(v);
+  }
+
+  Point2D MinPt() {
+    return ptMin;
+  }
+
+  Point2D MaxPt() {
+    return ptMax;
+  }
+
+  public IntersectCase intersect(Rectangle r) {
+    throw new UnsupportedOperationException();
+    // TODO
+  }
+
+  public Point2D getMaxPoint() {
+    return ptMax;
+  }
+
+  public Point2D getMinPoint() {
+    return ptMin;
+  }
+
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Vector2D.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Vector2D.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Vector2D.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/geometry/shape/Vector2D.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,120 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.geometry.shape;
+
+
+/**
+ * 2D vector
+ */
+public class Vector2D {
+  private double x;
+  private double y;
+
+  /**
+   * Create a vector from the origin of the coordinate system to the given
+   * point
+   * 
+   * @param x
+   * @param y
+   */
+  public Vector2D(double x, double y) {
+    this.x = x;
+    this.y = y;
+  }
+
+  /**
+   * Create a vector from the origin of the coordinate system to the given
+   * point
+   */
+  public Vector2D(Point2D p) {
+    this(p.getX(), p.getY());
+  }
+
+  /**
+   * Create a vector from one point to another
+   * 
+   * @param from
+   * @param to
+   */
+  public Vector2D(Point2D from, Point2D to) {
+    this(to.getX() - from.getX(), to.getY() - from.getY());
+  }
+
+  public Vector2D() {
+    this.x = 0;
+    this.y = 0;
+  }
+
+  public Vector2D(Vector2D other) {
+    this.x = other.x;
+    this.y = other.y;
+  }
+
+  public double getX() {
+    return x;
+  }
+
+  public double getY() {
+    return y;
+  }
+
+  public void setX(double x) {
+    this.x = x;
+  }
+
+  public void setY(double y) {
+    this.y = y;
+  }
+
+  public void set(double x, double y) {
+    this.x = x;
+    this.y = y;
+  }
+
+  public boolean equals(Vector2D other) {
+    return other != null && x == other.x && y == other.y;
+  }
+
+  @Override
+  public boolean equals(Object other) {
+    if (!(other instanceof Vector2D))
+      return false;
+    return equals((Vector2D) other);
+  }
+
+  public double dot(Vector2D in) {
+    return ((x) * in.x) + (y * in.y);
+  }
+
+  /**
+   * Vector length (magnitude) squared
+   */
+  public double normSqr() {
+    // Cast to F to prevent overflows
+    return (x * x) + (y * y);
+  }
+
+  public double norm() {
+    return Math.sqrt(normSqr());
+  }
+
+  public Vector2D mult(double d) {
+    return new Vector2D(x*d, y*d);
+  }
+
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/BoundaryBoxFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/BoundaryBoxFilter.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/BoundaryBoxFilter.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/BoundaryBoxFilter.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,210 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.tier;
+
+import java.io.IOException;
+import java.util.BitSet;
+import java.util.logging.Logger;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermDocs;
+import org.apache.lucene.index.TermEnum;
+import org.apache.lucene.search.Filter;
+import org.apache.lucene.spatial.NumberUtils;
+
+
+
+/**
+ * An implementation of org.apache.lucene.search.RangeFilter that
+ * caches values extracted from the index.
+ * 
+ */
+public class BoundaryBoxFilter extends Filter {
+
+  private static final long serialVersionUID = 1L;
+  private String fieldName;
+  private String lowerTerm;
+  private String upperTerm;
+  private boolean includeLower;
+  private boolean includeUpper;
+  private Logger log = Logger.getLogger(getClass().getName());
+  
+  // cache of values extracted from the index 
+  // TODO: add generics 
+  //private Map coords;
+  
+  /**
+   * @param fieldName The field this range applies to
+   * @param lowerTerm The lower bound on this range
+   * @param upperTerm The upper bound on this range
+   * @param includeLower Does this range include the lower bound?
+   * @param includeUpper Does this range include the upper bound?
+   * @throws IllegalArgumentException if both terms are null or if
+   *  lowerTerm is null and includeLower is true (similar for upperTerm
+   *  and includeUpper)
+   */
+  public BoundaryBoxFilter(String fieldName, String lowerTerm, String upperTerm,
+                     boolean includeLower, boolean includeUpper) {
+    this.fieldName = fieldName;
+    this.lowerTerm = lowerTerm;
+    this.upperTerm = upperTerm;
+    this.includeLower = includeLower;
+    this.includeUpper = includeUpper;
+    
+    if (null == lowerTerm && null == upperTerm) {
+      throw new IllegalArgumentException
+          ("At least one value must be non-null");
+    }
+    if (includeLower && null == lowerTerm) {
+      throw new IllegalArgumentException
+          ("The lower bound must be non-null to be inclusive");
+    }
+    if (includeUpper && null == upperTerm) {
+      throw new IllegalArgumentException
+          ("The upper bound must be non-null to be inclusive");
+    }
+  }
+    
+    
+  /**
+   * Returns a BitSet with true for documents which should be
+   * permitted in search results, and false for those that should
+   * not.
+   */
+  @Override
+  public BitSet bits(IndexReader reader) throws IOException {
+    long start = System.currentTimeMillis();
+    
+    BitSet bits = new BitSet(reader.maxDoc());
+    TermEnum enumerator =
+        (null != lowerTerm
+         ? reader.terms(new Term(fieldName, lowerTerm))
+         : reader.terms(new Term(fieldName,"")));
+    
+    //coords = new HashMap(enumerator.docFreq());
+    
+    try {
+      if (enumerator.term() == null) {
+        return bits;
+      }
+      
+      boolean checkLower = false;
+      if (!includeLower) // make adjustments to set to exclusive
+        checkLower = true;
+  
+      TermDocs termDocs = reader.termDocs();
+      try {          
+        do {
+          Term term = enumerator.term();
+          if (term != null && term.field().equals(fieldName)) {
+            if (!checkLower || null==lowerTerm || term.text().compareTo(lowerTerm) > 0) {
+              checkLower = false;
+              if (upperTerm != null) {
+                int compare = upperTerm.compareTo(term.text());
+                // if beyond the upper term, or is exclusive and
+                // this is equal to the upper term, break out 
+                if ((compare < 0) ||
+                  (!includeUpper && compare==0)) {
+                  break;
+                }
+              }
+              // we have a good term, find the docs 
+              termDocs.seek(enumerator.term());
+              while (termDocs.next()) {
+                bits.set(termDocs.doc());
+              }
+            }
+          } 
+          else {
+            break;
+          }
+        }
+        while (enumerator.next());    
+      } 
+      finally {
+        termDocs.close();
+      }
+    } 
+    finally {
+      enumerator.close();
+    }
+
+    long end = System.currentTimeMillis();
+    log.info("BoundaryBox Time Taken: "+ (end - start));
+    return bits;
+  }
+
+  @Override
+  public String toString() {
+    StringBuffer buffer = new StringBuffer();
+    buffer.append(fieldName);
+    buffer.append(":");
+    buffer.append(includeLower ? "[" : "{");
+    if (null != lowerTerm) {
+      buffer.append(NumberUtils.SortableStr2double(lowerTerm));
+    }
+    buffer.append("-");
+    if (null != upperTerm) {
+      buffer.append(NumberUtils.SortableStr2double(upperTerm));
+    }
+    buffer.append(includeUpper ? "]" : "}");
+    return buffer.toString();
+  }
+
+  public String getFieldName() {
+    return fieldName;
+  }
+
+  
+  /** 
+   * Returns true if <code>o</code> is equal to this.
+   * 
+   * @see org.apache.lucene.search.RangeFilter#equals
+   */
+  @Override
+  public boolean equals(Object o) {
+    if (this == o) return true;
+    if (!(o instanceof BoundaryBoxFilter)) return false;
+    BoundaryBoxFilter other = (BoundaryBoxFilter) o;
+
+    if (!this.fieldName.equals(other.fieldName)
+        || this.includeLower != other.includeLower
+        || this.includeUpper != other.includeUpper
+       ) { return false; }
+    if (this.lowerTerm != null ? !this.lowerTerm.equals(other.lowerTerm) : other.lowerTerm != null) return false;
+    if (this.upperTerm != null ? !this.upperTerm.equals(other.upperTerm) : other.upperTerm != null) return false;
+    return true;
+  }
+
+  /** 
+   * Returns a hash code value for this object.
+   * 
+   * @see org.apache.lucene.search.RangeFilter#hashCode
+   */
+  @Override
+  public int hashCode() {
+    int h = fieldName.hashCode();
+    h ^= lowerTerm != null ? lowerTerm.hashCode() : 0xB6ECE882;
+    h = (h << 1) | (h >>> 31);  // rotate to distinguish lower from upper
+    h ^= (upperTerm != null ? (upperTerm.hashCode()) : 0x91BEC2C2);
+    h ^= (includeLower ? 0xD484B933 : 0)
+       ^ (includeUpper ? 0x6AE423AC : 0);
+    return h;
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilter.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilter.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianPolyFilter.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,106 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.spatial.tier;
+
+import java.math.BigDecimal;
+import java.math.RoundingMode;
+import java.util.logging.Logger;
+
+import org.apache.lucene.search.Filter;
+import org.apache.lucene.spatial.geometry.shape.Rectangle;
+import org.apache.lucene.spatial.tier.projections.CartesianTierPlotter;
+import org.apache.lucene.spatial.tier.projections.IProjector;
+import org.apache.lucene.spatial.tier.projections.SinusoidalProjector;
+
+
+/**
+ *
+ */
+public class CartesianPolyFilter {
+
+  private IProjector projector = new SinusoidalProjector();
+  private Logger log = Logger.getLogger(getClass().getName());
+  
+  public Shape getBoxShape(double latitude, double longitude, int miles)
+  {  
+    Rectangle box = DistanceUtils.getInstance().getBoundary(latitude, longitude, miles);
+    
+    double latY = box.getMaxPoint().getY();//box.getY();
+    double latX = box.getMinPoint().getY() ; //box.getMaxY();
+    
+    double longY = box.getMaxPoint().getX(); ///box.getX();
+    double longX = box.getMinPoint().getX();//box.getMaxX();
+    
+    CartesianTierPlotter ctp = new CartesianTierPlotter(2, projector);
+    int bestFit = ctp.bestFit(miles);
+    
+    log.info("Best Fit is : " + bestFit);
+    ctp = new CartesianTierPlotter(bestFit, projector);
+    Shape shape = new Shape(ctp.getTierFieldName());
+    
+    // generate shape
+    // iterate from startX->endX
+    //     iterate from startY -> endY
+    //      shape.add(currentLat.currentLong);
+    
+   
+    double beginAt = ctp.getTierBoxId(latX, longX);
+    double endAt = ctp.getTierBoxId(latY, longY);
+    
+    double tierVert = ctp.getTierVerticalPosDivider();
+    log.fine(" | "+ beginAt+" | "+ endAt);
+    
+    double startX = beginAt - (beginAt %1);
+    double startY = beginAt - startX ; //should give a whole number
+    
+    double endX = endAt - (endAt %1);
+    double endY = endAt -endX; //should give a whole number
+    
+    int scale = (int)Math.log10(tierVert);
+    endY = new BigDecimal(endY).setScale(scale, RoundingMode.HALF_EVEN).doubleValue();
+    startY = new BigDecimal(startY).setScale(scale, RoundingMode.HALF_EVEN).doubleValue();
+    log.fine("scale "+scale+" startX "+ startX + " endX "+endX +" startY "+ startY + " endY "+ endY +" tierVert "+ tierVert);
+    
+    double xInc = 1.0d / tierVert;
+    xInc = new BigDecimal(xInc).setScale(scale, RoundingMode.HALF_EVEN).doubleValue();
+    
+    for (; startX <= endX; startX++){
+      
+      double itY = startY;
+      while (itY <= endY){
+        //create a boxId
+        // startX.startY
+        double boxId = startX + itY ;
+        shape.addBox(boxId);
+        //System.out.println("----"+boxId);
+        itY += xInc;
+        
+        // java keeps 0.0001 as 1.0E-1
+        // which ends up as 0.00011111
+        itY = new BigDecimal(itY).setScale(scale, RoundingMode.HALF_EVEN).doubleValue();
+      }
+    }
+    return shape;
+  }
+  
+  public Filter getBoundingArea(double latitude, double longitude, int miles) 
+  {
+    Shape shape = getBoxShape(latitude, longitude, miles);
+    return new CartesianShapeFilter(shape, shape.getTierId());
+  }
+}

Added: lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianShapeFilter.java
URL: http://svn.apache.org/viewvc/lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianShapeFilter.java?rev=730067&view=auto
==============================================================================
--- lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianShapeFilter.java (added)
+++ lucene/java/trunk/contrib/spatial/src/java/org/apache/lucene/spatial/tier/CartesianShapeFilter.java Mon Dec 29 23:37:17 2008
@@ -0,0 +1,75 @@
+/**
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.lucene.spatial.tier;
+
+import java.io.IOException;
+import java.util.BitSet;
+import java.util.List;
+import java.util.logging.Logger;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.Term;
+import org.apache.lucene.index.TermDocs;
+import org.apache.lucene.search.Filter;
+import org.apache.lucene.spatial.NumberUtils;
+
+public class CartesianShapeFilter extends Filter {
+
+  /**
+   * 
+   */
+  private static final long serialVersionUID = 1L;
+  private Shape shape;
+  private Logger log = Logger.getLogger(getClass().getName());
+  private String fieldName;
+  
+  CartesianShapeFilter(Shape shape, String fieldName){
+    this.shape = shape;
+    this.fieldName = fieldName;
+  }
+  
+  @Override
+  public BitSet bits(IndexReader reader) throws IOException {
+    long start = System.currentTimeMillis();
+      
+    BitSet bits = new BitSet(reader.maxDoc());
+
+    TermDocs termDocs = reader.termDocs();
+    List<Double> area = shape.getArea();
+    int sz = area.size();
+    log.info("Area size "+ sz);
+    
+    // iterate through each boxid
+    for (int i =0; i< sz; i++) {
+      double boxId = area.get(i).doubleValue();
+          
+      termDocs.seek(new Term(fieldName,
+          NumberUtils.double2sortableStr(boxId)));
+      
+      // iterate through all documents
+      // which have this boxId
+      while (termDocs.next()) {
+        bits.set(termDocs.doc());
+      }
+    }
+    
+    long end = System.currentTimeMillis();
+    log.info("BoundaryBox Time Taken: "+ (end - start) + " found: "+bits.cardinality()+" candidates");
+    return bits;
+  }
+
+}



Mime
View raw message