null+****@clear*****
null+****@clear*****
2010年 8月 12日 (木) 17:20:13 JST
Kouhei Sutou 2010-08-12 08:20:13 +0000 (Thu, 12 Aug 2010)
New Revision: 70f65fc8098689cdf99cf2947607540b4ea087b8
Log:
work for long latitude rectangle.
Modified files:
lib/geo.c
test/unit/story/test-taiyaki.c
Modified: lib/geo.c (+45 -42)
===================================================================
--- lib/geo.c 2010-08-12 02:48:01 +0000 (a152e94)
+++ lib/geo.c 2010-08-12 08:20:13 +0000 (11fdae8)
@@ -31,24 +31,16 @@ typedef struct {
static int
compute_diff_bit(uint8_t *geo_key1, uint8_t *geo_key2)
{
- int i, diff_bit = 0;
+ int i, j, diff_bit = 0;
for (i = 0; i < sizeof(grn_geo_point); i++) {
- if (geo_key1[i] == geo_key2[i]) {
- continue;
- }
-
- if ((geo_key1[i] & 0xc0) != (geo_key2[i] & 0xc0)) {
- diff_bit = 0;
- break;
- } else if ((geo_key1[i] & 0x30) != (geo_key2[i] & 0x30)) {
- diff_bit = 2;
- break;
- } else if ((geo_key1[i] & 0x0c) != (geo_key2[i] & 0x0c)) {
- diff_bit = 4;
- break;
- } else if ((geo_key1[i] & 0x03) != (geo_key2[i] & 0x03)) {
- diff_bit = 6;
+ if (geo_key1[i] != geo_key2[i]) {
+ for (j = 0; j < 8; j++) {
+ if ((geo_key1[i] & (1 << (7 - j))) != (geo_key2[i] & (1 << (7 - j)))) {
+ diff_bit = j + 1;
+ break;
+ }
+ }
break;
}
}
@@ -120,6 +112,9 @@ grn_geo_table_sort_detect_far_point(grn_ctx *ctx, grn_obj *table, grn_obj *index
diff_bit_prev = diff_bit_current;
diff_bit_current = compute_diff_bit(geo_key_curr, geo_key_prev);
+ if ((diff_bit_current % 2) == 1) {
+ diff_bit_current--;
+ }
if (diff_bit_current < diff_bit_prev && *diff_bit > diff_bit_current) {
if (i == n) {
break;
@@ -581,6 +576,9 @@ grn_geo_search_in_circle(grn_ctx *ctx, grn_obj *obj, grn_obj **args, int nargs,
grn_gton(geo_key1, geo_point1, sizeof(grn_geo_point));
grn_gton(geo_key2, &geo_point2, sizeof(grn_geo_point));
diff_bit = compute_diff_bit(geo_key1, geo_key2);
+ if ((diff_bit % 2) == 1) {
+ diff_bit--;
+ }
n_meshes = grn_geo_get_meshes_for_circle(ctx, geo_point1,
d_far, diff_bit, GRN_TRUE,
meshes);
@@ -651,35 +649,38 @@ grn_geo_search_in_rectangle(grn_ctx *ctx, grn_obj *obj, grn_obj **args, int narg
mesh_direction direction;
int distance, latitude_distance, longitude_distance;
int i, start, end, diff_bit;
- grn_geo_point geo_point_base, geo_point_min, geo_point_max;
- uint8_t geo_key1[sizeof(grn_geo_point)];
+ grn_geo_point *geo_point_input, geo_point_base, geo_point_min, geo_point_max;
+ uint8_t geo_key_input[sizeof(grn_geo_point)];
uint8_t geo_key_base[sizeof(grn_geo_point)];
latitude_distance = geo_point1->latitude - geo_point2->latitude;
longitude_distance = geo_point2->longitude - geo_point1->longitude;
if (latitude_distance > longitude_distance) {
direction = MESH_LATITUDE;
- distance = latitude_distance;
- geo_point_base.latitude = geo_point1->latitude;
- geo_point_base.longitude = geo_point1->longitude + distance;
- end = geo_point2->latitude;
+ geo_point_input = geo_point2;
+ geo_point_base.latitude = geo_point2->latitude;
+ geo_point_base.longitude = geo_point2->longitude - longitude_distance;
} else {
direction = MESH_LONGITUDE;
- distance = longitude_distance;
- geo_point_base.latitude = geo_point1->latitude + distance;
+ geo_point_input = geo_point1;
+ geo_point_base.latitude = geo_point1->latitude + latitude_distance;
geo_point_base.longitude = geo_point1->longitude;
- end = geo_point2->longitude;
}
- grn_gton(geo_key1, geo_point1, sizeof(grn_geo_point));
+ grn_gton(geo_key_input, geo_point_input, sizeof(grn_geo_point));
grn_gton(geo_key_base, &geo_point_base, sizeof(grn_geo_point));
- diff_bit = compute_diff_bit(geo_key1, geo_key_base);
- compute_min_and_max(geo_point1, diff_bit + 2, &geo_point_min, &geo_point_max);
+ diff_bit = compute_diff_bit(geo_key_input, geo_key_base);
+ compute_min_and_max(geo_point_input, diff_bit,
+ &geo_point_min, &geo_point_max);
if (direction == MESH_LATITUDE) {
- start = geo_point_max.latitude;
+ start = geo_point2->latitude;
+ end = geo_point_max.latitude;
+ distance = geo_point_max.latitude - geo_point_min.latitude + 1;
} else {
- start = geo_point_max.longitude;
+ start = geo_point_min.longitude;
+ end = geo_point2->longitude;
+ distance = geo_point_max.longitude - geo_point_min.longitude + 1;
}
- memcpy(&geo_point_base, &geo_point_max, sizeof(grn_geo_point));
+ memcpy(&geo_point_base, &geo_point_min, sizeof(grn_geo_point));
#ifdef GEO_DEBUG
printf("direction: %s\n",
direction == MESH_LATITUDE ? "latitude" : "longitude");
@@ -689,17 +690,15 @@ grn_geo_search_in_rectangle(grn_ctx *ctx, grn_obj *obj, grn_obj **args, int narg
grn_p_geo_point(ctx, geo_point1);
printf("bottom-right: ");
grn_p_geo_point(ctx, geo_point2);
+ printf("start: %10d\n", start);
+ printf("end: %10d\n", end);
+ printf("distance: %10d\n", distance);
#endif
for (i = start; i < end + distance; i += distance) {
grn_table_cursor *tc;
- if (direction == MESH_LATITUDE) {
- geo_point_base.latitude += direction;
- } else {
- geo_point_base.longitude += direction;
- }
tc = grn_table_cursor_open(ctx, pat,
- &geo_point_base, diff_bit + 1,
+ &geo_point_base, diff_bit,
NULL, 0,
0, -1,
GRN_CURSOR_PREFIX|GRN_CURSOR_SIZE_BY_BIT);
@@ -708,16 +707,20 @@ grn_geo_search_in_rectangle(grn_ctx *ctx, grn_obj *obj, grn_obj **args, int narg
grn_id tid;
grn_geo_point pos;
while ((tid = grn_table_cursor_next(ctx, tc))) {
- if (i == start || end < i) {
- grn_table_get_key(ctx, pat, tid, &pos, sizeof(grn_geo_point));
- if (!grn_geo_in_rectangle_raw(ctx, &pos, geo_point1, geo_point2)) {
- continue;
- }
+ grn_table_get_key(ctx, pat, tid, &pos, sizeof(grn_geo_point));
+ if (!grn_geo_in_rectangle_raw(ctx, &pos, geo_point1, geo_point2)) {
+ continue;
}
+ inspect_tid(ctx, tid, &pos, 0);
grn_ii_at(ctx, (grn_ii *)obj, tid, (grn_hash *)res, op);
}
grn_table_cursor_close(ctx, tc);
}
+ if (direction == MESH_LATITUDE) {
+ geo_point_base.latitude += distance;
+ } else {
+ geo_point_base.longitude += distance;
+ }
}
}
exit :
Modified: test/unit/story/test-taiyaki.c (+40 -7)
===================================================================
--- test/unit/story/test-taiyaki.c 2010-08-12 02:48:01 +0000 (b5b40b4)
+++ test/unit/story/test-taiyaki.c 2010-08-12 08:20:13 +0000 (3925a75)
@@ -22,7 +22,8 @@
#include "../lib/grn-assertions.h"
void test_in_circle(void);
-void test_in_rectangle(void);
+void test_in_rectangle_long_longitude(void);
+void test_in_rectangle_long_latitude(void);
void test_sort(void);
void test_filter_by_tag_and_sort_by_distance_from_tokyo_tocho(void);
void test_but_white(void);
@@ -123,7 +124,7 @@ test_in_circle(void)
}
void
-test_in_rectangle(void)
+test_in_rectangle_long_longitude(void)
{
gdouble takada_no_baba_latitude = 35.7121;
gdouble takada_no_baba_longitude = 139.7038;
@@ -134,16 +135,17 @@ test_in_rectangle(void)
cut_assert_equal_string(
"[[[3],"
- "[[\"name\",\"ShortText\"],[\"_score\",\"Int32\"]],"
- "[\"たいやき神田達磨 八重洲店\",3273],"
- "[\"銀座 かずや\",3713],"
- "[\"たい焼き鉄次 大丸東京店\",3732]"
+ "[[\"name\",\"ShortText\"],[\"_score\",\"Int32\"],"
+ "[\"location\",\"WGS84GeoPoint\"]],"
+ "[\"たいやき神田達磨 八重洲店\",3273,\"130094061x505025099\"],"
+ "[\"銀座 かずや\",3713,\"130055008x504968095\"],"
+ "[\"たい焼き鉄次 大丸東京店\",3732,\"130089012x505045070\"]"
"]]",
send_command(
cut_take_printf(
"select Shops "
"--sortby '+_score, +name' "
- "--output_columns 'name, _score' "
+ "--output_columns 'name, _score, location' "
"--filter 'geo_in_rectangle(location, \"%s\", \"%s\")' "
"--scorer '_score=geo_distance(location, \"%s\")'",
grn_test_location_string(takada_no_baba_latitude,
@@ -153,6 +155,37 @@ test_in_rectangle(void)
}
void
+test_in_rectangle_long_latitude(void)
+{
+ gdouble sugamo_latitude = 35.73360;
+ gdouble sugamo_longitude = 139.7394;
+ gdouble daiba_latitude = 35.62614;
+ gdouble daiba_longitude = 139.7714;
+ gdouble budoukan_latitude = 35.69328;
+ gdouble budoukan_longitude = 139.74968;
+
+ cut_assert_equal_string(
+ "[[[4],"
+ "[[\"name\",\"ShortText\"],[\"_score\",\"Int32\"],"
+ "[\"location\",\"WGS84GeoPoint\"]],"
+ "[\"たいやき神田達磨 八重洲店\",3273,\"130094061x505025099\"],"
+ "[\"銀座 かずや\",3713,\"130055008x504968095\"],"
+ "[\"根津のたいやき\",4754,\"130322053x504985073\"],"
+ "[\"築地 さのきや\",5244,\"130019020x505027021\"]"
+ "]]",
+ send_command(
+ cut_take_printf(
+ "select Shops "
+ "--sortby '+_score, +name' "
+ "--output_columns 'name, _score, location' "
+ "--filter 'geo_in_rectangle(location, \"%s\", \"%s\")' "
+ "--scorer '_score=geo_distance(location, \"%s\")'",
+ grn_test_location_string(sugamo_latitude, sugamo_longitude),
+ grn_test_location_string(daiba_latitude, daiba_longitude),
+ grn_test_location_string(budoukan_latitude, budoukan_longitude))));
+}
+
+void
test_sort(void)
{
gdouble yurakucho_latitude = 35.67487;