From 09e7cc70408cb288757174236abd12e40b502dd6 Mon Sep 17 00:00:00 2001 From: Kaj-Michael Lang Date: Tue, 7 Aug 2007 04:31:37 +0300 Subject: [PATCH] New data format. Much nicer to work with. And faster. --- docs/osm-indexes.sql | 4 + docs/osm-tables.sql | 6 ++ src/osm-db.c | 243 ++++++++++++++++++++++++++++++++++--------- src/osm.c | 97 ++++++++++++----- src/osm.h | 5 +- 5 files changed, 276 insertions(+), 79 deletions(-) diff --git a/docs/osm-indexes.sql b/docs/osm-indexes.sql index 893573f..4720664 100644 --- a/docs/osm-indexes.sql +++ b/docs/osm-indexes.sql @@ -9,3 +9,7 @@ CREATE INDEX way_ref_idx on way_ref (ref); CREATE INDEX way_seg_wsid_idx on way_seg (wsid); CREATE INDEX way_seg_node_idx on way_seg (node); + +CREATE INDEX way_seg2_wsid_idx on way_s2s (wsid); +CREATE INDEX way_seg_f_idx on way_s2s (f); +CREATE INDEX way_seg_t_idx on way_s2s (t); diff --git a/docs/osm-tables.sql b/docs/osm-tables.sql index 57e4b57..c82ef6f 100644 --- a/docs/osm-tables.sql +++ b/docs/osm-tables.sql @@ -23,6 +23,12 @@ create table way_seg ( node int not null ); +create table way_s2s ( + wsid int not null, + f int not null, + t int not null +); + create table area ( waid int not null, num int not null, diff --git a/src/osm-db.c b/src/osm-db.c index def24b8..909b5b4 100644 --- a/src/osm-db.c +++ b/src/osm-db.c @@ -19,6 +19,10 @@ struct sql_select_stmt { sqlite3_stmt *select_way; + sqlite3_stmt *select_way2; + sqlite3_stmt *select_way_next_seg; + sqlite3_stmt *select_way_prev_seg; + sqlite3_stmt *select_way_nodes; sqlite3_stmt *select_way_name; sqlite3_stmt *select_way_ref; @@ -31,6 +35,9 @@ static GTimer *dbt; /* Cache hash tables */ static GHashTable *_place_cache; +osm_way_node *osm_way_get_prev_node(osm_way *w); +osm_way_node *osm_way_get_next_node(osm_way *w); + /*****************************************************************************/ static int @@ -43,7 +50,7 @@ return 0; gboolean osm_db_prepare(sqlite3 *db) { -#ifdef DEBUG +#ifdef DEBUG_OSM sqlite3_progress_handler(db, 1000, osm_progress, NULL); #endif @@ -70,26 +77,30 @@ if (sqlite3_prepare_v2(db, "select name,(($LAT-lat)*($LAT-lat))+(($LON-lon)*($LO /* Ways */ /* Select neareset ways inside lat,lon+-range */ if (sqlite3_prepare_v2(db, "select wid,type,nodes,flags," - "(($LAT-lat)*($LAT-lat))+(($LON-lon)*($LON-lon)) as dist, num" - " from way,way_seg,nodes" - " where wid=wsid and way_seg.node=nodes.nid " + "(($LAT-lat)*($LAT-lat))+(($LON-lon)*($LON-lon)) as dist,f,t,lat,lon " + " from way,way_s2s,nodes" + " where wid=wsid and way_s2s.f=nodes.nid " " and lat between $LAT-$RANGE and $LAT+$RANGE " " and lon between $LON-$RANGE and $LON+$RANGE " " and type between $WTS and $WTY " " order by dist", - -1, &sql.select_way, NULL)!=SQLITE_OK) + -1, &sql.select_way2, NULL)!=SQLITE_OK) return FALSE; -/* Select way nodes */ -if (sqlite3_prepare_v2(db, "select num,lat,lon from way_seg,nodes where wsid=? and way_seg.node=nodes.nid order by num", - -1, &sql.select_way_nodes, NULL)!=SQLITE_OK) +if (sqlite3_prepare_v2(db, "select t,lat,lon from way_s2s,nodes where wsid=? and f=? and way_s2s.t=nodes.nid limit 1", + -1, &sql.select_way_next_seg, NULL)!=SQLITE_OK) return FALSE; -/* Way name and ref */ +if (sqlite3_prepare_v2(db, "select f,lat,lon from way_s2s,nodes where wsid=? and t=? and way_s2s.f=nodes.nid limit 1", + -1, &sql.select_way_prev_seg, NULL)!=SQLITE_OK) + return FALSE; + +/* Way name */ if (sqlite3_prepare_v2(db, "select name from way_names where wid=?", -1, &sql.select_way_name, NULL)!=SQLITE_OK) return FALSE; +/* Way ref and int_ref */ if (sqlite3_prepare_v2(db, "select ref,int_ref from way_ref where rid=?", -1, &sql.select_way_ref, NULL)!=SQLITE_OK) return FALSE; @@ -114,6 +125,25 @@ g_timer_destroy(dbt); /*****************************************************************************/ +osm_way_node * +osm_way_node_new(guint id, gint lat, gint lon, gint flags) +{ +osm_way_node *n=g_slice_new(osm_way_node); + +n->id=id; +n->lat=lat; +n->lon=lon; +n->flags=flags; +return n; +} + +void +osm_way_node_free(osm_way_node *n) +{ +if (n) + g_slice_free(osm_way_node, n); +} + /** * Free way nodes list */ @@ -313,6 +343,7 @@ if (SQLITE_ROW == sqlite3_step(sql.select_near_place)) { return FALSE; } +#if 0 /* Way helper */ static GList * osm_find_nearest_way_nodes(gint lat, gint lon, guint range) @@ -357,6 +388,64 @@ g_printf("Query took: %f sec, found: %d ways\n", g_timer_elapsed(dbt, &tms), wc) return ways; } +#else + +/* Way helper */ +static GList * +osm_find_nearest_way_nodes(gint lat, gint lon, guint range) +{ +GList *ways=NULL; +osm_way *w; +gulong tms; +gint wc=0; + +sqlite3_reset(sql.select_way2); +sqlite3_clear_bindings(sql.select_way2); + +if (SQLITE_OK != sqlite3_bind_int(sql.select_way2, 1, lat) || + SQLITE_OK != sqlite3_bind_int(sql.select_way2, 2, lon) || + SQLITE_OK != sqlite3_bind_int(sql.select_way2, 3, range) || + SQLITE_OK != sqlite3_bind_int(sql.select_way2, 4, WAY_ROAD_START) || + SQLITE_OK != sqlite3_bind_int(sql.select_way2, 5, WAY_ROAD_END)) { + g_printerr("Failed to bind values for way\n"); + return NULL; +} + +g_timer_start(dbt); + +while (SQLITE_ROW == sqlite3_step(sql.select_way2)) { + guint32 dist; + gint lat, lon; + + wc++; + w=g_slice_new0(osm_way); + w->id=sqlite3_column_int(sql.select_way2, 0); + w->type=sqlite3_column_int(sql.select_way2, 1); + w->nodecnt=sqlite3_column_int(sql.select_way2, 2); + w->flags=sqlite3_column_int(sql.select_way2, 3); + dist=sqlite3_column_int(sql.select_way2, 4); + w->dist=sqrt((gdouble)dist); + w->f=sqlite3_column_int(sql.select_way2, 5); + w->t=sqlite3_column_int(sql.select_way2, 6); + + lat=sqlite3_column_int(sql.select_way2, 7); + lon=sqlite3_column_int(sql.select_way2, 8); + + w->node_f=osm_way_node_new(w->f, lat, lon, 0); + + ways=g_list_prepend(ways, w); +} + +g_timer_stop(dbt); +g_printf("Query took: %f sec, found: %d ways\n", g_timer_elapsed(dbt, &tms), wc); + +return ways; +} + +#endif + +/*****************************************************************************/ + inline gdouble magnitude(gdouble x1, gdouble y1, gdouble x2, gdouble y2) { @@ -394,8 +483,15 @@ return TRUE; gboolean osm_way_distance(gint lat, gint lon, osm_way_node *f, osm_way_node *t, gdouble *d) { -if (!f || !t) +if (!f) { + g_printerr("## From point missing\n"); return FALSE; +} + +if (!t) { + g_printerr("## To point missing\n"); + return FALSE; +} return distance_point_to_line((gdouble)lon, (gdouble)lat, (gdouble)f->lon, (gdouble)f->lat, (gdouble)t->lon, (gdouble)t->lat, d); } @@ -409,6 +505,9 @@ return distance_point_to_line((gdouble)lon, (gdouble)lat, (gdouble)f->lon, (gdou * - Store result if closer than before * - Return closest way */ + +#define START_DIST (900000.0) + osm_way * osm_find_nearest_way(gint lat, gint lon) { @@ -416,7 +515,7 @@ GList *iter; GList *w=NULL; guint range=4096; osm_way *cw=NULL; -gdouble pdist=900000.0, pndist=9000000.0; +gdouble pdist=START_DIST, dist_n, dist_p; while ((w=osm_find_nearest_way_nodes(lat, lon, range))==NULL && range<=65536) { range=range<<1; @@ -429,54 +528,45 @@ if (g_list_length(w)==0) return NULL; for (iter=w; iter!=NULL; iter=iter->next) { - osm_way_node *wnf; - osm_way_node *wnt; + osm_way_node *wnn; + osm_way_node *wnp; osm_way *way=(osm_way*)iter->data; -#ifdef DEBUG_OSM g_printf("WAY %d (%d) HAS %d NODES, nearest is %d\n", - way->id, way->type, way->nodecnt, way->node_num); -#endif - - if (osm_way_get_nodes(way)==FALSE) - continue; + way->id, way->type, way->nodecnt, way->f); - if (way->nodes==0) { - g_printerr("Way with 0 nodes ? Skipping\n"); - continue; - } + way->node_t=NULL; - wnf=g_list_nth_data(way->nodes, way->node_num); - if (!wnf) { - osm_way_free(way); - continue; + wnn=osm_way_get_next_node(way); + if (osm_way_distance(lat, lon, way->node_f, wnn, &dist_n)==FALSE) { + osm_way_node_free(wnn); + dist_n=START_DIST; + } else if (dist_ndistance=dist_n; + way->node_t=wnn; + g_printf("#1 distance: %f (%f)\n", dist_n, pdist); } - if ((way->node_num==way->nodecnt) || (way->node_num==0)) { - wnt=g_list_nth_data(way->nodes, way->node_num==way->nodecnt ? way->nodecnt-1 : 1); - if (osm_way_distance(lat, lon, wnf, wnt, &pndist)==FALSE) { - osm_way_free(way); - continue; - } - } else { - wnt=g_list_nth_data(way->nodes, way->node_num-1); - if (osm_way_distance(lat, lon, wnf, wnt, &pndist)==FALSE) { - wnt=g_list_nth_data(way->nodes, way->node_num+1); - if (osm_way_distance(lat, lon, wnf, wnt, &pndist)==FALSE) { - osm_way_free(way); - continue; - } + wnp=osm_way_get_prev_node(way); + if (osm_way_distance(lat, lon, way->node_f, wnp, &dist_p)==FALSE) { + osm_way_node_free(wnp); + dist_p=START_DIST; + } else if (dist_pdistance=dist_n; + if (way->node_t) { + osm_way_node_free(wnn); } + way->node_t=wnp; + g_printf("#2 distance: %f (%f)\n", dist_p, pdist); } - if (pndistnode_f=wnf; - way->node_t=wnt; - way->distance=pndist; - cw=way; - } else { + g_printf("Found close way, distance: %f %f (%f)\n", dist_n, dist_p, pdist); + + if (!cw) { osm_way_free(way); way=NULL; } @@ -506,6 +596,52 @@ g_printf("\tNF: %d NT: %d DT %f\n", return cw; } +osm_way_node * +osm_way_get_prev_node(osm_way *w) +{ +sqlite3_reset(sql.select_way_prev_seg); +sqlite3_clear_bindings(sql.select_way_prev_seg); + +if (SQLITE_OK != sqlite3_bind_int(sql.select_way_prev_seg, 1, w->id) || + SQLITE_OK != sqlite3_bind_int(sql.select_way_prev_seg, 2, w->f) ) { + g_printerr("Failed to bind values for prev seg\n"); + return NULL; +} + +if (SQLITE_ROW == sqlite3_step(sql.select_way_prev_seg)) { + return osm_way_node_new( + sqlite3_column_int(sql.select_way_prev_seg, 0), + sqlite3_column_int(sql.select_way_prev_seg, 1), + sqlite3_column_int(sql.select_way_prev_seg, 2), + 0); +} + +return NULL; +} + +osm_way_node * +osm_way_get_next_node(osm_way *w) +{ +sqlite3_reset(sql.select_way_next_seg); +sqlite3_clear_bindings(sql.select_way_next_seg); + +if (SQLITE_OK != sqlite3_bind_int(sql.select_way_next_seg, 1, w->id) || + SQLITE_OK != sqlite3_bind_int(sql.select_way_next_seg, 2, w->f) ) { + g_printerr("Failed to bind values for next seg\n"); + return NULL; +} + +if (SQLITE_ROW == sqlite3_step(sql.select_way_next_seg)) { + return osm_way_node_new( + sqlite3_column_int(sql.select_way_next_seg, 0), + sqlite3_column_int(sql.select_way_next_seg, 1), + sqlite3_column_int(sql.select_way_next_seg, 2), + 0); +} + +return NULL; +} + /** * Get list of nodes for given way */ @@ -527,7 +663,7 @@ while (SQLITE_ROW == sqlite3_step(sql.select_way_nodes)) { osm_way_node *n; n=g_slice_new(osm_way_node); - n->num=sqlite3_column_int(sql.select_way_nodes, 0); + n->id=sqlite3_column_int(sql.select_way_nodes, 0); n->lat=sqlite3_column_int(sql.select_way_nodes, 1); n->lon=sqlite3_column_int(sql.select_way_nodes, 2); w->nodes=g_list_append(w->nodes, n); @@ -536,6 +672,9 @@ while (SQLITE_ROW == sqlite3_step(sql.select_way_nodes)) { return (w->nodes==NULL) ? FALSE : TRUE; } +/** + * Get way name (primary name only for now) + */ gboolean osm_way_get_name(osm_way *w) { @@ -555,6 +694,10 @@ if (SQLITE_ROW == sqlite3_step(sql.select_way_name)) { return FALSE; } + +/** + * Get Way ref and int_ref + */ gboolean osm_way_get_ref(osm_way *w) { diff --git a/src/osm.c b/src/osm.c index 0fb5041..56011bc 100644 --- a/src/osm.c +++ b/src/osm.c @@ -163,35 +163,35 @@ struct _nodeinfo { struct _wayinfo { gchar *k, *v; way_type_t type; - gboolean oneway, link, area; + gboolean oneway, link, area, car, foot; } wayinfo[] = { - { "highway", "motorway",WAY_MOTORWAY, TRUE, FALSE, FALSE }, - { "highway", "motorway_link",WAY_MOTORWAY, TRUE, TRUE, FALSE }, - { "highway", "trunk",WAY_TRUNK, FALSE, FALSE, FALSE }, - { "highway", "trunk_link",WAY_TRUNK, FALSE, TRUE, FALSE }, - { "highway", "primary",WAY_PRIMARY, FALSE, FALSE, FALSE }, - { "highway", "primary_link",WAY_PRIMARY, FALSE, TRUE, FALSE }, - { "highway", "secondary",WAY_SECONDARY, FALSE, FALSE, FALSE }, - { "highway", "secondary_link",WAY_SECONDARY, FALSE, TRUE, FALSE }, - { "highway", "tertiary",WAY_TERTIARY, FALSE, FALSE, FALSE }, - { "highway", "unclasified",WAY_UNCLASSIFIED, FALSE, FALSE, FALSE }, - { "highway", "residential",WAY_RESIDENTIAL, FALSE, FALSE, FALSE }, - { "highway", "service",WAY_SERVICE, FALSE, FALSE, FALSE }, - { "highway", "track",WAY_TRACK, FALSE, FALSE, FALSE }, - { "highway", "unsurfaced",WAY_TRACK, FALSE, FALSE, FALSE }, - { "highway", "pedestrian",WAY_FOOTWAY, FALSE, FALSE, FALSE }, - { "highway", "footway",WAY_FOOTWAY, FALSE, FALSE, FALSE }, - { "highway", "steps",WAY_FOOTWAY, FALSE, FALSE, FALSE }, - { "highway", "bridleway",WAY_FOOTWAY, FALSE, FALSE, FALSE }, - { "highway", "cycleway",WAY_CYCLEWAY, FALSE, FALSE, FALSE }, - { "railway", "rail",WAY_RAIL, FALSE, FALSE, FALSE }, - { "aeroway", "runway",WAY_RUNWAY, FALSE, FALSE, FALSE }, - { "aeroway", "taxiway",WAY_TAXIWAY, FALSE, FALSE, FALSE }, - { "natural", "water",WAY_WATER, FALSE, FALSE, TRUE }, - { "waterway", "river",WAY_WATER, FALSE, FALSE, FALSE }, - { "waterway", "canal",WAY_WATER, FALSE, FALSE, FALSE }, - { "waterway", "stream",WAY_WATER, FALSE, FALSE, FALSE }, - { NULL, NULL, WAY_UNWAYED, FALSE, FALSE, FALSE } + { "highway", "motorway",WAY_MOTORWAY, TRUE, FALSE, FALSE, TRUE, FALSE }, + { "highway", "motorway_link",WAY_MOTORWAY, TRUE, TRUE, FALSE, TRUE, FALSE }, + { "highway", "trunk",WAY_TRUNK, FALSE, FALSE, FALSE, TRUE, FALSE }, + { "highway", "trunk_link",WAY_TRUNK, FALSE, TRUE, FALSE, TRUE, FALSE }, + { "highway", "primary",WAY_PRIMARY, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "primary_link",WAY_PRIMARY, FALSE, TRUE, FALSE, TRUE, TRUE }, + { "highway", "secondary",WAY_SECONDARY, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "secondary_link",WAY_SECONDARY, FALSE, TRUE, FALSE, TRUE, TRUE }, + { "highway", "tertiary",WAY_TERTIARY, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "unclasified",WAY_UNCLASSIFIED, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "residential",WAY_RESIDENTIAL, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "service",WAY_SERVICE, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "track",WAY_TRACK, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "unsurfaced",WAY_TRACK, FALSE, FALSE, FALSE, TRUE, TRUE }, + { "highway", "pedestrian",WAY_FOOTWAY, FALSE, FALSE, FALSE, FALSE, TRUE }, + { "highway", "footway",WAY_FOOTWAY, FALSE, FALSE, FALSE, FALSE, TRUE }, + { "highway", "steps",WAY_FOOTWAY, FALSE, FALSE, FALSE, FALSE, TRUE}, + { "highway", "bridleway",WAY_FOOTWAY, FALSE, FALSE, FALSE, FALSE, TRUE }, + { "highway", "cycleway",WAY_CYCLEWAY, FALSE, FALSE, FALSE, FALSE, TRUE }, + { "railway", "rail",WAY_RAIL, FALSE, FALSE, FALSE, FALSE, FALSE }, + { "aeroway", "runway",WAY_RUNWAY, FALSE, FALSE, FALSE, FALSE, FALSE }, + { "aeroway", "taxiway",WAY_TAXIWAY, FALSE, FALSE, FALSE, FALSE, FALSE }, + { "natural", "water",WAY_WATER, FALSE, FALSE, TRUE, FALSE, FALSE }, + { "waterway", "river",WAY_WATER, FALSE, FALSE, FALSE, FALSE, FALSE }, + { "waterway", "canal",WAY_WATER, FALSE, FALSE, FALSE, FALSE, FALSE }, + { "waterway", "stream",WAY_WATER, FALSE, FALSE, FALSE, FALSE, FALSE }, + { NULL, NULL, WAY_UNWAYED, FALSE, FALSE, FALSE, FALSE, FALSE } }; static sqlite3 *db; @@ -227,8 +227,10 @@ struct sql_stmt { sqlite3_stmt *insert_way_ref; sqlite3_stmt *insert_way_name; sqlite3_stmt *insert_way_seg; + sqlite3_stmt *insert_way_seg2seg; sqlite3_stmt *delete_way; sqlite3_stmt *delete_way_seg; + sqlite3_stmt *delete_way_seg2seg; sqlite3_stmt *delete_way_seg_wsid; sqlite3_stmt *delete_way_name; sqlite3_stmt *delete_way_ref; @@ -314,6 +316,7 @@ sqlite3_prepare_v2(db, "insert or replace into way (wid,nodes,type,flags,speed,i sqlite3_prepare_v2(db, "delete from way", -1, &sql.delete_way, NULL); +/* Way segments, try 1*/ sqlite3_prepare_v2(db, "insert into way_seg (wsid,num,node) values (?, ?, ?)", -1, &sql.insert_way_seg, NULL); sqlite3_prepare_v2(db, "delete from way_seg", -1, @@ -321,11 +324,19 @@ sqlite3_prepare_v2(db, "delete from way_seg", -1, sqlite3_prepare_v2(db, "delete from way_seg where wsid=?", -1, &sql.delete_way_seg_wsid, NULL); +/* Way segments, try 2*/ +sqlite3_prepare_v2(db, "insert into way_s2s (wsid,f,t) values (?, ?, ?)", + -1, &sql.insert_way_seg2seg, NULL); +sqlite3_prepare_v2(db, "delete from way_s2s where wsid=?", -1, + &sql.delete_way_seg2seg, NULL); + +/* Way names */ sqlite3_prepare_v2(db, "insert or replace into way_names (wid,name) values (?, ?)", -1, &sql.insert_way_name, NULL); sqlite3_prepare_v2(db, "delete from way_names", -1, &sql.delete_way_name, NULL); +/* Way ref and int_ref */ sqlite3_prepare_v2(db, "insert or replace into way_ref (rid,ref,int_ref) values (?, ?, ?)", -1, &sql.insert_way_ref, NULL); sqlite3_prepare_v2(db, "delete from way_ref", -1, @@ -426,6 +437,22 @@ db_update_node_links(n); wsegcnt++; } +void +db_insert_way_seg2seg(way *w, node *nf, node *nt) +{ +sqlite3_bind_int(sql.insert_way_seg2seg, 1, w->id); +sqlite3_bind_int(sql.insert_way_seg2seg, 2, nf->id); +sqlite3_bind_int(sql.insert_way_seg2seg, 3, nt->id); + +sqlite3_step(sql.insert_way_seg2seg); +sqlite3_reset(sql.insert_way_seg2seg); +sqlite3_clear_bindings(sql.insert_way_seg2seg); +db_update_node_links(nf); +db_update_node_links(nt); + +wsegcnt++; +} + void db_insert_way_ref(way *w) { @@ -471,6 +498,16 @@ sqlite3_reset(sql.delete_way_seg_wsid); sqlite3_clear_bindings(sql.delete_way_seg_wsid); } +void +db_delete_way_segments2seg(way *w) +{ +sqlite3_bind_int(sql.delete_way_seg2seg, 1, w->id); + +sqlite3_step(sql.delete_way_seg2seg); +sqlite3_reset(sql.delete_way_seg2seg); +sqlite3_clear_bindings(sql.delete_way_seg2seg); +} + gboolean db_insert_way_segments(segment *s, way *w) { @@ -496,9 +533,13 @@ if (!t) { return FALSE; } +#if OLD_WAYSEG db_insert_way_seg(f,w); if (w->ncnt==wsegcnt) db_insert_way_seg(t,w); +#else +db_insert_way_seg2seg(w,f,t); +#endif return TRUE; } diff --git a/src/osm.h b/src/osm.h index 3a30136..bc33227 100644 --- a/src/osm.h +++ b/src/osm.h @@ -132,7 +132,8 @@ struct _osm_place { /* Way node */ typedef struct _osm_way_node osm_way_node; struct _osm_way_node { - guint num; + guint id; + guint flags; gint lat; gint lon; }; @@ -146,6 +147,8 @@ struct _osm_way { guint nodecnt; guint32 isin; guint node_num; + guint f; + guint t; gdouble dist; gdouble distance; gchar *name; -- 2.39.5