[From nobody Tue Aug 14 12:05:57 2007 Return-Path: <dev-bounces@openstreetmap.org> X-Original-To: tweety@localhost Delivered-To: tweety@localhost Received: from battlefield.dasch.ostertag.name (localhost [127.0.0.1]) by battlefield.dasch.ostertag.name (Postfix) with ESMTP id 81DE362C207 for <tweety@localhost>; Tue, 14 Aug 2007 16:25:04 +0200 (CEST) Received: from secure.key-systems.net [81.3.43.213] by battlefield.dasch.ostertag.name with POP3 (fetchmail-6.3.8) for <tweety@localhost> (single-drop); Tue, 14 Aug 2007 16:25:04 +0200 (CEST) Received: (qmail 7375 invoked by uid 54538); 14 Aug 2007 14:24:50 +0000 Delivered-To: mailspacedomain_dp6fuge97x-openstreetmap@ostertag.name Received: (qmail 7369 invoked by uid 0); 14 Aug 2007 14:24:50 +0000 Received: from [80.68.94.95] (HELO streetmap.vm.bytemark.co.uk) (80.68.94.95) by mx-01.dd24.net (qpsmtpd/0.31.1) with ESMTP; Di, 14 Aug 2007 14:24:50 +0000 Received: from localhost ([127.0.0.1] helo=streetmap.vm.bytemark.co.uk) by streetmap.vm.bytemark.co.uk with esmtp (Exim 4.63) (envelope-from <dev-bounces@openstreetmap.org>) id 1IKxH1-0008Pf-6n; Tue, 14 Aug 2007 15:21:31 +0100 Received: from thewordnerd.info ([208.75.85.127]) by streetmap.vm.bytemark.co.uk with esmtp (Exim 4.63) (envelope-from <nolan@thewordnerd.info>) id 1IKxGy-0008Pa-G6 for dev@openstreetmap.org; Tue, 14 Aug 2007 15:21:28 +0100 Received: from [192.168.23.140] (cpe-70-112-109-131.austin.res.rr.com [70.112.109.131]) by thewordnerd.info (Postfix) with ESMTP id DFBE698093 for <dev@openstreetmap.org>; Tue, 14 Aug 2007 14:21:27 +0000 (UTC) Mime-Version: 1.0 (Apple Message framework v752.2) Message-Id: <E3B76563-3216-4527-AEA4-1D5E1D0D4412@thewordnerd.info> To: dev@openstreetmap.org From: Nolan Darilek <nolan@thewordnerd.info> Date: Tue, 14 Aug 2007 09:21:24 -0500 X-Mailer: Apple Mail (2.752.2) Subject: [OSM-dev] Creating a graph for routing X-BeenThere: dev@openstreetmap.org X-Mailman-Version: 2.1.9 Precedence: list List-Id: OpenStreetMap developer discusssion <dev.openstreetmap.org> List-Unsubscribe: <http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev>, <mailto:dev-request@openstreetmap.org?subject=unsubscribe> List-Archive: <http://lists.openstreetmap.org/pipermail/dev> List-Post: <mailto:dev@openstreetmap.org> List-Help: <mailto:dev-request@openstreetmap.org?subject=help> List-Subscribe: <http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev>, <mailto:dev-request@openstreetmap.org?subject=subscribe> Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 7bit Sender: dev-bounces@openstreetmap.org Errors-To: dev-bounces@openstreetmap.org X-Length: 6164 Hello. First, I'm not certain whether my questions are completely on- topic for this list, and apologize if they aren't. If there's a better community for folks developing mapping applications that aren't necessarily OSM core, do let me know and I'll go there. As a brief summary, I'm designing GPS navigation software for blind/ visually-impaired users. So instead of displaying a map, for instance, the software displays everything in a text stream--what street you're on, upcoming intersections, how many ways they are, what streets meet, etc. It's written in Ruby using ActiveRecord, WXRuby and Postgres/Postgis for the data store. I intend for this to be run on high-end mobile devices, and the stack may be too heavy for that, I just don't know yet. I registered my domain yesterday, though, and what I have thus far can be found at http://hermes- gps.info. Apologies for the stock website--I tweaked the newgem default and am leaving it for now. But, anyway, onto the questions. I'm planning on using pgRouting, and for this and other features I need to create a graph of all intersections. I currently check whether each path I save intersects any others and generate intersection models at the point of intersection. I tried determining whether or not any given node was at an intersection between ways, but this didn't seem markably faster, and since I'd eventually like to support users creating new paths on the fly, this unifies everything under a single callback invoked whenever paths are saved. I also generate edges for each intersection and path, two edges if the path completely contains the intersection point (I.e. crosses) but since I don't have all intersections saved in the initial import, it's impossible to complete the graph by setting the "to" component of each edge. I have an algorithm for this, but it looks like it may take more than a day to run for a single county, and I can't help but wonder if it could be optimized, or if I'm missing something super obvious. Here's the algorithm. Iterate over all edges created during a given import. First, find all intersections on an edge's path sorted by distance. Then check whether an edge from the given intersection exists to the target. If so then another edge has already been created, so move on (since, again, the initial pass only knows how many are necessary, not where they will lead.) Then for each intersection, iterate through all points between the edge's intersection and the target intersection exclusive. If any intermediate point is an intersection, move onto the next furthest intersection. Otherwise, you've found the closest intersection with none between, so set this as the destination of the edge and set the distance along the line as the cost of the edge. Thoughts as to how I might optimize that? Or is there a better way? And if anyone is interested in helping with this project, check out the above website. This scratches an itch for me, but I really know little about how this stuff works, so I'm figuring it all out by brute-force thinking my way through. While this may seem admirable, it discounts the notion that others have already done the same, and have probably done so with better results. :) _______________________________________________ dev mailing list dev@openstreetmap.org http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/dev ]