You are viewing a plain text version of this content. The canonical link for it is here.
Posted to java-commits@lucene.apache.org by ry...@apache.org on 2008/12/30 08:37:18 UTC
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...
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;
+ }
+
+}