2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
9 * http://www.apache.org/licenses/LICENSE-2.0
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
17 package org.apache.lucene.spatial.tier;
19 import java.io.IOException;
20 import java.util.LinkedList;
21 import java.util.List;
24 import org.apache.lucene.analysis.MockAnalyzer;
25 import org.apache.lucene.document.Document;
26 import org.apache.lucene.document.Field;
27 import org.apache.lucene.index.IndexReader;
28 import org.apache.lucene.index.IndexWriter;
29 import org.apache.lucene.index.IndexReader;
30 import org.apache.lucene.index.Term;
31 import org.apache.lucene.search.IndexSearcher;
32 import org.apache.lucene.search.Query;
33 import org.apache.lucene.search.ScoreDoc;
34 import org.apache.lucene.search.Sort;
35 import org.apache.lucene.search.SortField;
36 import org.apache.lucene.search.TermQuery;
37 import org.apache.lucene.search.TopDocs;
38 import org.apache.lucene.search.function.CustomScoreQuery;
39 import org.apache.lucene.search.function.CustomScoreProvider;
40 import org.apache.lucene.search.function.FieldScoreQuery;
41 import org.apache.lucene.search.function.FieldScoreQuery.Type;
42 import org.apache.lucene.spatial.DistanceUtils;
43 import org.apache.lucene.spatial.geohash.GeoHashUtils;
44 import org.apache.lucene.spatial.geometry.DistanceUnits;
45 import org.apache.lucene.spatial.geometry.FloatLatLng;
46 import org.apache.lucene.spatial.geometry.LatLng;
47 import org.apache.lucene.spatial.tier.projections.CartesianTierPlotter;
48 import org.apache.lucene.spatial.tier.projections.IProjector;
49 import org.apache.lucene.spatial.tier.projections.SinusoidalProjector;
50 import org.apache.lucene.store.Directory;
51 import org.apache.lucene.util.LuceneTestCase;
52 import org.apache.lucene.util.NumericUtils;
54 public class TestCartesian extends LuceneTestCase {
56 private Directory directory;
57 private IndexSearcher searcher;
59 private double lat = 38.969398;
60 private double lng= -77.386398;
61 private String latField = "lat";
62 private String lngField = "lng";
63 private List<CartesianTierPlotter> ctps = new LinkedList<CartesianTierPlotter>();
64 private String geoHashPrefix = "_geoHash_";
66 private IProjector project = new SinusoidalProjector();
71 public void setUp() throws Exception {
73 directory = newDirectory();
75 IndexWriter writer = new IndexWriter(directory, newIndexWriterConfig(TEST_VERSION_CURRENT, new MockAnalyzer(random)));
84 public void tearDown() throws Exception {
90 private void setUpPlotter(int base, int top) {
92 for (; base <= top; base ++){
93 ctps.add(new CartesianTierPlotter(base,project,
94 CartesianTierPlotter.DEFALT_FIELD_PREFIX));
98 private void addPoint(IndexWriter writer, String name, double lat, double lng) throws IOException{
100 Document doc = new Document();
102 doc.add(newField("name", name,Field.Store.YES, Field.Index.ANALYZED));
104 // convert the lat / long to lucene fields
105 doc.add(new Field(latField, NumericUtils.doubleToPrefixCoded(lat),Field.Store.YES, Field.Index.NOT_ANALYZED));
106 doc.add(new Field(lngField, NumericUtils.doubleToPrefixCoded(lng),Field.Store.YES, Field.Index.NOT_ANALYZED));
108 // add a default meta field to make searching all documents easy
109 doc.add(newField("metafile", "doc",Field.Store.YES, Field.Index.ANALYZED));
111 int ctpsize = ctps.size();
112 for (int i =0; i < ctpsize; i++){
113 CartesianTierPlotter ctp = ctps.get(i);
114 doc.add(new Field(ctp.getTierFieldName(),
115 NumericUtils.doubleToPrefixCoded(ctp.getTierBoxId(lat,lng)),
117 Field.Index.NOT_ANALYZED_NO_NORMS));
119 doc.add(newField(geoHashPrefix, GeoHashUtils.encode(lat,lng),
121 Field.Index.NOT_ANALYZED_NO_NORMS));
123 writer.addDocument(doc);
129 private void addData(IndexWriter writer) throws IOException {
130 addPoint(writer,"McCormick & Schmick's Seafood Restaurant",38.9579000,-77.3572000);
131 addPoint(writer,"Jimmy's Old Town Tavern",38.9690000,-77.3862000);
132 addPoint(writer,"Ned Devine's",38.9510000,-77.4107000);
133 addPoint(writer,"Old Brogue Irish Pub",38.9955000,-77.2884000);
134 addPoint(writer,"Alf Laylah Wa Laylah",38.8956000,-77.4258000);
135 addPoint(writer,"Sully's Restaurant & Supper",38.9003000,-77.4467000);
136 addPoint(writer,"TGIFriday",38.8725000,-77.3829000);
137 addPoint(writer,"Potomac Swing Dance Club",38.9027000,-77.2639000);
138 addPoint(writer,"White Tiger Restaurant",38.9027000,-77.2638000);
139 addPoint(writer,"Jammin' Java",38.9039000,-77.2622000);
140 addPoint(writer,"Potomac Swing Dance Club",38.9027000,-77.2639000);
141 addPoint(writer,"WiseAcres Comedy Club",38.9248000,-77.2344000);
142 addPoint(writer,"Glen Echo Spanish Ballroom",38.9691000,-77.1400000);
143 addPoint(writer,"Whitlow's on Wilson",38.8889000,-77.0926000);
144 addPoint(writer,"Iota Club and Cafe",38.8890000,-77.0923000);
145 addPoint(writer,"Hilton Washington Embassy Row",38.9103000,-77.0451000);
146 addPoint(writer,"HorseFeathers, Bar & Grill", 39.01220000000001, -77.3942);
147 addPoint(writer,"Marshall Island Airfield",7.06, 171.2);
148 addPoint(writer, "Wonga Wongue Reserve, Gabon", -0.546562,9.459229);
149 addPoint(writer,"Midway Island",25.7, -171.7);
150 addPoint(writer,"North Pole Way",55.0, 4.0);
153 // TODO: fix CustomScoreQuery usage in testRange/testGeoHashRange so we don't need this.
154 writer.forceMerge(1);
159 public void testDistances() throws IOException, InvalidGeoException {
160 LatLng p1 = new FloatLatLng( 7.06, 171.2 );
161 LatLng p2 = new FloatLatLng( 21.6032207, -158.0 );
162 double miles = p1.arcDistance( p2, DistanceUnits.MILES );
164 System.out.println("testDistances");
165 System.out.println("miles:" + miles);
167 assertEquals(2288.82495932794, miles, 0.001);
168 LatLng p3 = new FloatLatLng( 41.6032207, -73.087749);
169 LatLng p4 = new FloatLatLng( 55.0, 4.0 );
170 miles = p3.arcDistance( p4, DistanceUnits.MILES );
171 if (VERBOSE) System.out.println("miles:" + miles);
172 assertEquals(3474.331719997617, miles, 0.001);
175 /*public void testCartesianPolyFilterBuilder() throws Exception {
176 CartesianPolyFilterBuilder cpfb = new CartesianPolyFilterBuilder(CartesianTierPlotter.DEFALT_FIELD_PREFIX, 2, 15);
177 //try out some shapes
178 final double miles = 20.0;
180 // 2300 miles to Marshall Island Airfield
181 //Hawaii to Midway is 911 miles
185 shape = cpfb.getBoxShape(lat, lng, miles);
186 System.out.println("Tier: " + shape.getTierLevel());
187 System.out.println("area: " + shape.getArea().size());
190 shape = cpfb.getBoxShape(lat, lng, miles);
191 System.out.println("Tier: " + shape.getTierLevel());
192 System.out.println("area: " + shape.getArea().size());
196 shape = cpfb.getBoxShape(lat, lng, miles);
197 System.out.println("Tier: " + shape.getTierLevel());
198 System.out.println("area: " + shape.getArea().size());
203 public void testAntiM() throws IOException, InvalidGeoException {
204 IndexReader reader = IndexReader.open(directory);
205 searcher = new IndexSearcher(reader);
207 final double miles = 2800.0;
209 // 2300 miles to Marshall Island Airfield
210 //Hawaii to Midway is 911 miles
214 if (VERBOSE) System.out.println("testAntiM");
215 // create a distance query
216 final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles,
217 latField, lngField, CartesianTierPlotter.DEFALT_FIELD_PREFIX, true, 2, 15);
219 if (VERBOSE) System.out.println(dq);
220 //create a term query to search against all documents
221 Query tq = new TermQuery(new Term("metafile", "doc"));
223 FieldScoreQuery fsQuery = new FieldScoreQuery("geo_distance", Type.FLOAT);
225 CustomScoreQuery customScore = new CustomScoreQuery(dq.getQuery(tq),fsQuery){
228 protected CustomScoreProvider getCustomScoreProvider(IndexReader reader) {
229 return new CustomScoreProvider(reader) {
230 @Override // TODO: broken, as reader is not used!
231 public float customScore(int doc, float subQueryScore, float valSrcScore){
232 if (VERBOSE) System.out.println(doc);
233 if (dq.distanceFilter.getDistance(doc) == null)
236 double distance = dq.distanceFilter.getDistance(doc);
237 // boost score shouldn't exceed 1
240 //boost by distance is invertly proportional to
241 // to distance from center point to location
242 float score = (float) ((miles - distance) / miles );
243 return score * subQueryScore;
249 // Create a distance sort
250 // As the radius filter has performed the distance calculations
251 // already, pass in the filter to reuse the results.
253 DistanceFieldComparatorSource dsort = new DistanceFieldComparatorSource(dq.distanceFilter);
254 Sort sort = new Sort(new SortField("foo", dsort,false));
256 // Perform the search, using the term query, the serial chain filter, and the
258 TopDocs hits = searcher.search(customScore.createWeight(searcher),null, 1000, sort);
259 int results = hits.totalHits;
260 ScoreDoc[] scoreDocs = hits.scoreDocs;
262 // Get a list of distances
263 Map<Integer,Double> distances = dq.distanceFilter.getDistances();
265 // distances calculated from filter first pass must be less than total
266 // docs, from the above test of 20 items, 12 will come from the boundary box
267 // filter, but only 5 are actually in the radius of the results.
269 // Note Boundary Box filtering, is not accurate enough for most systems.
273 System.out.println("Distance Filter filtered: " + distances.size());
274 System.out.println("Results: " + results);
275 System.out.println("=============================");
276 System.out.println("Distances should be 2 "+ distances.size());
277 System.out.println("Results should be 2 "+ results);
280 assertEquals(2, distances.size()); // fixed a store of only needed distances
281 assertEquals(2, results);
282 double lastDistance = 0;
283 for(int i =0 ; i < results; i++){
284 Document d = searcher.doc(scoreDocs[i].doc);
286 String name = d.get("name");
287 double rsLat = NumericUtils.prefixCodedToDouble(d.get(latField));
288 double rsLng = NumericUtils.prefixCodedToDouble(d.get(lngField));
289 Double geo_distance = distances.get(scoreDocs[i].doc);
291 double distance = DistanceUtils.getDistanceMi(lat, lng, rsLat, rsLng);
292 double llm = DistanceUtils.getLLMDistance(lat, lng, rsLat, rsLng);
293 if (VERBOSE) System.out.println("Name: "+ name +", Distance "+ distance); //(res, ortho, harvesine):"+ distance +" |"+ geo_distance +"|"+ llm +" | score "+ hits.score(i));
294 assertTrue(Math.abs((distance - llm)) < 1);
295 assertTrue((distance < miles ));
296 assertTrue(geo_distance >= lastDistance);
297 lastDistance = geo_distance;
303 public void testPoleFlipping() throws IOException, InvalidGeoException {
304 IndexReader reader = IndexReader.open(directory);
305 searcher = new IndexSearcher(reader);
307 final double miles = 3500.0;
311 if (VERBOSE) System.out.println("testPoleFlipping");
313 // create a distance query
314 final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles,
315 latField, lngField, CartesianTierPlotter.DEFALT_FIELD_PREFIX, true, 2, 15);
317 if (VERBOSE) System.out.println(dq);
318 //create a term query to search against all documents
319 Query tq = new TermQuery(new Term("metafile", "doc"));
321 FieldScoreQuery fsQuery = new FieldScoreQuery("geo_distance", Type.FLOAT);
323 CustomScoreQuery customScore = new CustomScoreQuery(dq.getQuery(tq),fsQuery){
326 protected CustomScoreProvider getCustomScoreProvider(IndexReader reader) {
327 return new CustomScoreProvider(reader) {
328 @Override // TODO: broken, as reader is not used!
329 public float customScore(int doc, float subQueryScore, float valSrcScore){
330 if (VERBOSE) System.out.println(doc);
331 if (dq.distanceFilter.getDistance(doc) == null)
334 double distance = dq.distanceFilter.getDistance(doc);
335 // boost score shouldn't exceed 1
338 //boost by distance is invertly proportional to
339 // to distance from center point to location
340 float score = (float) ((miles - distance) / miles );
341 return score * subQueryScore;
347 // Create a distance sort
348 // As the radius filter has performed the distance calculations
349 // already, pass in the filter to reuse the results.
351 DistanceFieldComparatorSource dsort = new DistanceFieldComparatorSource(dq.distanceFilter);
352 Sort sort = new Sort(new SortField("foo", dsort,false));
354 // Perform the search, using the term query, the serial chain filter, and the
356 TopDocs hits = searcher.search(customScore.createWeight(searcher),null, 1000, sort);
357 int results = hits.totalHits;
358 ScoreDoc[] scoreDocs = hits.scoreDocs;
360 // Get a list of distances
361 Map<Integer,Double> distances = dq.distanceFilter.getDistances();
363 // distances calculated from filter first pass must be less than total
364 // docs, from the above test of 20 items, 12 will come from the boundary box
365 // filter, but only 5 are actually in the radius of the results.
367 // Note Boundary Box filtering, is not accurate enough for most systems.
371 System.out.println("Distance Filter filtered: " + distances.size());
372 System.out.println("Results: " + results);
373 System.out.println("=============================");
374 System.out.println("Distances should be 18 "+ distances.size());
375 System.out.println("Results should be 18 "+ results);
378 assertEquals(18, distances.size()); // fixed a store of only needed distances
379 assertEquals(18, results);
380 double lastDistance = 0;
381 for(int i =0 ; i < results; i++){
382 Document d = searcher.doc(scoreDocs[i].doc);
383 String name = d.get("name");
384 double rsLat = NumericUtils.prefixCodedToDouble(d.get(latField));
385 double rsLng = NumericUtils.prefixCodedToDouble(d.get(lngField));
386 Double geo_distance = distances.get(scoreDocs[i].doc);
388 double distance = DistanceUtils.getDistanceMi(lat, lng, rsLat, rsLng);
389 double llm = DistanceUtils.getLLMDistance(lat, lng, rsLat, rsLng);
390 if (VERBOSE) System.out.println("Name: "+ name +", Distance "+ distance); //(res, ortho, harvesine):"+ distance +" |"+ geo_distance +"|"+ llm +" | score "+ hits.score(i));
391 assertTrue(Math.abs((distance - llm)) < 1);
392 if (VERBOSE) System.out.println("checking limit "+ distance + " < " + miles);
393 assertTrue((distance < miles ));
394 if (VERBOSE) System.out.println("checking sort "+ geo_distance + " >= " + lastDistance);
395 assertTrue(geo_distance >= lastDistance);
396 lastDistance = geo_distance;
402 public void testRange() throws IOException, InvalidGeoException {
403 IndexReader reader = IndexReader.open(directory);
404 searcher = new IndexSearcher(reader);
406 final double[] milesToTest = new double[] {6.0, 0.5, 0.001, 0.0};
407 final int[] expected = new int[] {7, 1, 0, 0};
409 for(int x=0;x<expected.length;x++) {
411 final double miles = milesToTest[x];
413 // create a distance query
414 final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles,
415 latField, lngField, CartesianTierPlotter.DEFALT_FIELD_PREFIX, true, 2, 15);
417 if (VERBOSE) System.out.println(dq);
418 //create a term query to search against all documents
419 Query tq = new TermQuery(new Term("metafile", "doc"));
421 FieldScoreQuery fsQuery = new FieldScoreQuery("geo_distance", Type.FLOAT);
423 CustomScoreQuery customScore = new CustomScoreQuery(dq.getQuery(tq),fsQuery){
425 protected CustomScoreProvider getCustomScoreProvider(IndexReader reader) {
426 return new CustomScoreProvider(reader) {
427 @Override // TODO: broken, as reader is not used!
428 public float customScore(int doc, float subQueryScore, float valSrcScore){
429 if (VERBOSE) System.out.println(doc);
430 if (dq.distanceFilter.getDistance(doc) == null)
433 double distance = dq.distanceFilter.getDistance(doc);
434 // boost score shouldn't exceed 1
437 //boost by distance is invertly proportional to
438 // to distance from center point to location
439 float score = (float) ( (miles - distance) / miles );
440 return score * subQueryScore;
445 // Create a distance sort
446 // As the radius filter has performed the distance calculations
447 // already, pass in the filter to reuse the results.
449 DistanceFieldComparatorSource dsort = new DistanceFieldComparatorSource(dq.distanceFilter);
450 Sort sort = new Sort(new SortField("foo", dsort,false));
452 // Perform the search, using the term query, the serial chain filter, and the
454 TopDocs hits = searcher.search(customScore.createWeight(searcher),null, 1000, sort);
455 int results = hits.totalHits;
456 ScoreDoc[] scoreDocs = hits.scoreDocs;
458 // Get a list of distances
459 Map<Integer,Double> distances = dq.distanceFilter.getDistances();
461 // distances calculated from filter first pass must be less than total
462 // docs, from the above test of 20 items, 12 will come from the boundary box
463 // filter, but only 5 are actually in the radius of the results.
465 // Note Boundary Box filtering, is not accurate enough for most systems.
468 System.out.println("Distance Filter filtered: " + distances.size());
469 System.out.println("Results: " + results);
470 System.out.println("=============================");
471 System.out.println("Distances should be 7 "+ expected[x] + ":" + distances.size());
472 System.out.println("Results should be 7 "+ expected[x] + ":" + results);
475 assertEquals(expected[x], distances.size()); // fixed a store of only needed distances
476 assertEquals(expected[x], results);
477 double lastDistance = 0;
478 for(int i =0 ; i < results; i++){
479 Document d = searcher.doc(scoreDocs[i].doc);
481 String name = d.get("name");
482 double rsLat = NumericUtils.prefixCodedToDouble(d.get(latField));
483 double rsLng = NumericUtils.prefixCodedToDouble(d.get(lngField));
484 Double geo_distance = distances.get(scoreDocs[i].doc);
486 double distance = DistanceUtils.getDistanceMi(lat, lng, rsLat, rsLng);
487 double llm = DistanceUtils.getLLMDistance(lat, lng, rsLat, rsLng);
488 if (VERBOSE) System.out.println("Name: "+ name +", Distance "+ distance); //(res, ortho, harvesine):"+ distance +" |"+ geo_distance +"|"+ llm +" | score "+ hits.score(i));
489 assertTrue(Math.abs((distance - llm)) < 1);
490 assertTrue((distance < miles ));
491 assertTrue(geo_distance > lastDistance);
492 lastDistance = geo_distance;
501 public void testGeoHashRange() throws IOException, InvalidGeoException {
502 IndexReader reader = IndexReader.open(directory);
503 searcher = new IndexSearcher(reader);
505 final double[] milesToTest = new double[] {6.0, 0.5, 0.001, 0.0};
506 final int[] expected = new int[] {7, 1, 0, 0};
508 for(int x=0;x<expected.length;x++) {
509 final double miles = milesToTest[x];
511 // create a distance query
512 final DistanceQueryBuilder dq = new DistanceQueryBuilder(lat, lng, miles,
513 geoHashPrefix, CartesianTierPlotter.DEFALT_FIELD_PREFIX, true, 2, 15);
515 if (VERBOSE) System.out.println(dq);
516 //create a term query to search against all documents
517 Query tq = new TermQuery(new Term("metafile", "doc"));
519 FieldScoreQuery fsQuery = new FieldScoreQuery("geo_distance", Type.FLOAT);
520 CustomScoreQuery customScore = new CustomScoreQuery(tq,fsQuery){
522 protected CustomScoreProvider getCustomScoreProvider(IndexReader reader) {
523 return new CustomScoreProvider(reader) {
524 @Override // TODO: broken, as reader is not used!
525 public float customScore(int doc, float subQueryScore, float valSrcScore){
526 if (VERBOSE) System.out.println(doc);
527 if (dq.distanceFilter.getDistance(doc) == null)
530 double distance = dq.distanceFilter.getDistance(doc);
531 // boost score shouldn't exceed 1
534 //boost by distance is invertly proportional to
535 // to distance from center point to location
536 float score = (float) ( (miles - distance) / miles );
537 return score * subQueryScore;
542 // Create a distance sort
543 // As the radius filter has performed the distance calculations
544 // already, pass in the filter to reuse the results.
546 //DistanceFieldComparatorSource dsort = new DistanceFieldComparatorSource(dq.distanceFilter);
547 //Sort sort = new Sort(new SortField("foo", dsort));
549 // Perform the search, using the term query, the serial chain filter, and the
551 TopDocs hits = searcher.search(customScore.createWeight(searcher),dq.getFilter(), 1000); //,sort);
552 int results = hits.totalHits;
553 ScoreDoc[] scoreDocs = hits.scoreDocs;
555 // Get a list of distances
556 Map<Integer,Double> distances = dq.distanceFilter.getDistances();
558 // distances calculated from filter first pass must be less than total
559 // docs, from the above test of 20 items, 12 will come from the boundary box
560 // filter, but only 5 are actually in the radius of the results.
562 // Note Boundary Box filtering, is not accurate enough for most systems.
565 System.out.println("Distance Filter filtered: " + distances.size());
566 System.out.println("Results: " + results);
567 System.out.println("=============================");
568 System.out.println("Distances should be 14 "+ expected[x] + ":" + distances.size());
569 System.out.println("Results should be 7 "+ expected[x] + ":" + results);
572 assertEquals(expected[x], distances.size());
573 assertEquals(expected[x], results);
575 for(int i =0 ; i < results; i++){
576 Document d = searcher.doc(scoreDocs[i].doc);
578 String name = d.get("name");
579 double rsLat = NumericUtils.prefixCodedToDouble(d.get(latField));
580 double rsLng = NumericUtils.prefixCodedToDouble(d.get(lngField));
581 Double geo_distance = distances.get(scoreDocs[i].doc);
583 double distance = DistanceUtils.getDistanceMi(lat, lng, rsLat, rsLng);
584 double llm = DistanceUtils.getLLMDistance(lat, lng, rsLat, rsLng);
585 if (VERBOSE) System.out.println("Name: "+ name +", Distance (res, ortho, harvesine):"+ distance +" |"+ geo_distance +"|"+ llm +" | score "+ scoreDocs[i].score);
586 assertTrue(Math.abs((distance - llm)) < 1);
587 assertTrue((distance < miles ));