[postgis-users] How to identify start node and end node in shortest_path_astar when
Pradeep B V
pradeepbv at gmail.com
Thu Sep 28 03:40:47 PDT 2006
If your start multilinestring (nearest to the start clicked point) or
> end multilinestring (nearest to the end clicked point) is not straight
> (because multilinestring consists of a lot of linestrings).So what
> should I draw?
I understand it now.
We too had similar problems. The way we have solved it is like this.
We defined a custom type in the postgres database called mapunity_geom which
not only holds the geom (in our case the linesegment) but also the order in
which the linesegment appears in the linestring.
It is done like this.
CREATE TYPE mapunity_geoms AS
(gid integer,
rid integer,
the_geom geometry);
ALTER TYPE mapunity_geoms OWNER TO postgres;
here the rid integer stores the order/sequence info.
Now we create the new shortest_path function like this:
CREATE OR REPLACE FUNCTION
mapunity_shortest_path_as_geometry_internal_id(geom_table character varying,
source integer, target integer)
RETURNS SETOF mapunity_geoms AS
$BODY$
DECLARE
r record;
path_result record;
v_id integer;
e_id integer;
geom mapunity_geoms;
BEGIN
FOR path_result IN EXECUTE 'SELECT vertex_id, edge_id FROM
shortest_path(''SELECT id, source, target, cost FROM ' ||
quote_ident(geom_table) || '_edges '', ' ||
quote_literal(source) || ' , ' || quote_literal(target) || ' , false, false)
' LOOP
v_id = path_result.vertex_id;
e_id = path_result.edge_id;
FOR r IN EXECUTE 'SELECT gid, the_geom FROM ' ||
quote_ident(geom_table) || ' WHERE edge_id = ' || quote_literal(e_id) LOOP
geom.gid := r.gid;
geom.rid := nextval ('rid_seq');
geom.the_geom := r.the_geom;
RETURN NEXT geom;
END LOOP;
END LOOP;
RETURN;
END;
$BODY$
LANGUAGE 'plpgsql' VOLATILE STRICT;
where the rid is set as serial thus incrementing everytime a new
line-segment appears in the path.
now use this and create a custom version of shortest_path_as_geometry
function like this
CREATE OR REPLACE FUNCTION mapunity_shortest_path_as_geometry(geom_table
character varying, geom_source anyelement, geom_target anyelement)
RETURNS SETOF mapunity_geoms AS
$BODY$
DECLARE
r record;
source int4;
target int4;
path_result record;
v_id integer;
e_id integer;
geom mapunity_geoms;
BEGIN
FOR r IN EXECUTE 'SELECT id FROM ' || quote_ident(geom_table) ||
'_vertices WHERE geom_id = ' || quote_literal(geom_source) LOOP
source = r.id;
END LOOP;
IF source IS NULL THEN
RAISE EXCEPTION 'Can''t find source edge';
END IF;
FOR r IN EXECUTE 'SELECT id FROM ' || quote_ident(geom_table) ||
'_vertices WHERE geom_id = ' || quote_literal(geom_target) LOOP
target = r.id;
END LOOP;
IF target IS NULL THEN
RAISE EXCEPTION 'Can''t find target edge';
END IF;
FOR geom IN SELECT * FROM
mapunity_shortest_path_as_geometry_internal_id(geom_table, source, target)
LOOP
RETURN NEXT geom;
END LOOP;
RETURN;
END;
$BODY$
LANGUAGE 'plpgsql' VOLATILE STRICT;
The query goes like this.
SELECT * FROM mapunity_shortest_path_as_geometry ('indiaroads',33,137);
for which you get the result like this :
gid;rid;the_geom
"37";"1109649";"0105000020E610000001000000010200000004000000597342E98BBA524005B7B14621ED4040D997FB3CC6B85240F14C57CABFE940400078D22457B6524075C7992301E44040B1452D40A8B45240847BEAD308E24040"
"43";"1109650";"0105000020E610000001000000010200000006000000597342E98BBA524005B7B14621ED40406A9A09D7F7BB524067A88EF8C2E9404081BDB79B3CBD524060FCBB8DB6E64040291F8C0521BE524012854E542CE34040E1457CDF26BF5240A68B5FCC35DE404035A3B897E2BF52404DA57CC934DA4040"
"47";"1109651";"0105000020E61000000100000001020000000300000035A3B897E2BF52404DA57CC934DA4040D1E4636B1FC05240411A4072E8D84040CE62042155C1524032C4018AE3D24040"
"49";"1109652";"0105000020E610000001000000010200000002000000CE62042155C1524032C4018AE3D24040613A69CEA9C15240855FB9DD3DD14040"
"80";"1109653";"0105000020E610000001000000010200000016000000613A69CEA9C15240855FB9DD3DD14040DCE692DDBEC2524023EB3EEC67C940409705E62D39C35240F82EEEF224C64040ACED4835A4C35240BCA90A3234C440406542614A51C45240C068AC1668C24040A872C3CCF6C552402A22ABF620BE40403A3E370A87C652401289FABBDFBB4040385E89E6D3C652408A21C20C96B940406C401CD43BC75240CFE4CDDCF0B1404042BE6C86B0C752409290F0FD20AC40402BEF1EECBEC7524023C753165EA9404088F31C0BEBC65240B79A39B8BD9F404023DD0112C2C65240E99FBA4C659D404008A193FDDAC65240FDFF5075319B4040D00B090F2DC75240539E8887E7994040499E704E0AC852401F3B988B3D9840404D24458601CA52408E314CAF7E95404075EC3D1ACACA5240DC6A3702279440409104797A8ACB5240894551D507924040C25617FAC9CC524084D91580158F4040CCA0C55989CF5240DA18BE2CE4874040CF7353B8BBD15240EFBB7832EC804040"
"88";"1109654";"0105000020E61000000100000001020000000A00000065767E7CB0C35240D60D40EF326C40409A736D021CC452404284075E056D40406D822BCD84C65240F3A5B5F6F8714040AA080F1A53C75240D5862FC611734040424930B1B3CA5240FB898AEFF97640409841AE2E2BCD52408FEB1099B67A40400265DEF5B1CE5240ED3364BAE57B40402EDCE9EA14D052405FC1F508497D4040CE0DD904AFD052405C93DCB6937E4040CF7353B8BBD15240EFBB7832EC804040"
"89";"1109655";"0105000020E610000001000000010200000002000000176AD542DCC35240BAC49F0D4E6A404065767E7CB0C35240D60D40EF326C4040"
"97";"1109656";"0105000020E6100000010000000102000000040000009CEDEC4578C352401D2CEBCC8F534040EE75C1B28EC3524055385361ED5C404092C02327BDC352407CE3CA5EB9644040176AD542DCC35240BAC49F0D4E6A4040"
"112";"1109657";"0105000020E610000001000000010200000005000000970FA955DDC35240F0AADAE6963A4040F31FEF1102C45240920CE1C457414040A40B0D59CBC35240AE41DB23424640401F3329BC8FC35240A9B911999A4B40409CEDEC4578C352401D2CEBCC8F534040"
"121";"1109658";"0105000020E6100000010000000102000000070000004F4EDDC049D05240537F47FB622F404011F4140941CE5240008B13D4F0304040FCF67469E3CB52403DE7791EEE324040A3442311C7C95240154A5FF6693540406AB6197B7CC7524060F655A533384040C65965B157C55240A66DEC7FBA394040970FA955DDC35240F0AADAE6963A4040"
"124";"1109659";"0105000020E61000000100000001020000000500000023B67138F3D95240467BF287E0294040FE1750A124D7524068A0F10E772B4040AC3B67DDA2D3524007B5EFD55E2D40401FC29A88F3D152402B691BDFB92E40404F4EDDC049D05240537F47FB622F4040"
"127";"1109660";"0105000020E610000001000000010200000006000000BB7CA72C79E1524038ACC396EB2540400304F1BE39DF5240C57088B900274040BE8BF92D93DD5240DD0E0C03792740406146C3898FDC5240BFF738CDE6274040997BD96F82DB5240F7A5F93D6D28404023B67138F3D95240467BF287E0294040"
"131";"1109661";"0105000020E61000000100000001020000000900000040BA752214E75240C9F46A6733194040D1FB16C90FE75240F681E8D4D9194040712B3A2A81E652409E0A96CFFE1D40409A023E4D16E6524057817FE0452040407EB5314E6CE552401B7ED0883022404094F94FAFA6E4524052DA842C8A2340406AF71130C3E352402D07CF398B2440400E876CAB8DE252404F11634966254040BB7CA72C79E1524038ACC396EB254040"
"130";"1109662";"0105000020E610000001000000010200000007000000B83C75F21AEE524060A3A0FEE01940402361D79DF5ED52401B153633E3194040C4B6B655DBEA5240C9B8AC4B211A404054724E52E3E8524099D46984241A4040A761C8113CE852401C992F1DE1194040DE2656676FE752409542C8978E19404040BA752214E75240C9F46A6733194040"
"129";"1109663";"0105000020E610000001000000010200000004000000AF0D16500EF852405A1F158F431B4040713744A435F6524017A176CA0E1B404023E6C27E69F152406168DA9DAE194040B83C75F21AEE524060A3A0FEE0194040"
"137";"1109664";"0105000020E61000000100000001020000000C000000FB755B8F02105340D10FC010CA0840401B50E802E00E534084BD41BA250A4040D9FDC791990C5340D7514667D50C4040A3BC4C9FC80953401DB3284CEC0E4040FF12E177A0025340D3E24FD0731240409691D396080153401691FF62B6134040BB7E0D7794FF524083A4F3B3FC144040FB6AAD444DFD5240DB9432A69A174040AED8BE0151FB52408716E5C8E4194040591D14CBBCF95240921E6AF1BB1A40400519A23B61F852408DC326CB4C1B4040AF0D16500EF852405A1F158F431B4040"
"139";"1109665";"0105000020E61000000100000001020000001200000074EFD45B5F1F53403879DCDD02024040E7202FFDF11E53401A55FF2A72014040BC526ECF801D53405735E91D13FF3F40B65976C4471C5340ED9B233ACBFC3F40FC1499B5A61B5340DF46494AAAFC3F40DB234E30391B53409F7FFC370EFD3F4089477C50B31A5340611AB030DCFE3F4069A9BD07281A534065BDA972ED0040408525BA268819534029767EA5C4024040F7D1B12F0F19534045C6870729044040CE3327069A185340A765DA3E30054040BB1A75480418534082BC8151D805404086CA1F283D1753400E4466E800064040CA62BE9BB814534098EF5002BE054040899E48F7AA1353405B99707DC00540400A0D11D7D012534038815B7605064040C1DBFF98CF115340F6630E0CA2064040FB755B8F02105340D10FC010CA084040"
"148";"1109666";"0105000020E610000001000000010200000012000000421AD3AB3B335340D9C60D8757EB3F40E90385B2F1325340E314A676C9EB3F40215ECBC08431534015BF6D352FED3F402A0490228330534095E26D8BA9EE3F40539B5BB3E72F5340552D3C13ACEF3F40E50C48B9212E53405A1FF2C09EF23F401A8260D0A52C53402843621B49F33F40D9536E737D2B5340929B5C3761F33F403FA0E5D634295340CEA2984690F33F40B37831D72B275340FEBEA949A3F33F40F6D406E64F265340F1F2A468A9F43F40C8497F8A93255340B44BA677AAF63F40D235DF42B124534076A2D2391EF93F40C0BB5D100A225340321D6E6C440240402820C57C4D215340873E5AB64403404026E9FE26D0205340C025060D380340407E414BBED91F5340CB9D7FC1A402404074EFD45B5F1F53403879DCDD02024040"
"181";"1109667";"0105000020E61000000100000001020000000C000000901DF3452D395340B3DF94A700A33F405F5B788E8D3953403E2E036A01AA3F40D8C6A2AA123A53401DA1405D19B53F4094A3BD500E3A5340025E065479BA3F40ECE38AF4523953405F4414D464C93F4027CA74FCC63853408FF9EF862DD13F40901E18211B385340BDE32559FBD73F40568789644B375340FEC87E40C2DE3F40B8706D50AC36534027CC9FE676E23F4038DAF5BAB1355340DD095B5894E63F40E15648509934534079B3E2CA3CE93F40421AD3AB3B335340D9C60D8757EB3F40"
"183";"1109668";"0105000020E61000000100000001020000000B000000901DF3452D395340B3DF94A700A33F403526C6BEDC3B5340043222E0E4A73F4055E53373B63C5340781100193FA93F40AE98280DD93D5340F6457C4029A93F40B767D53C6F4153408F252AC8F8A23F40439D486195425340EE0648EAFDA13F40D0F51640D9445340CA6CCA6E1CA23F4008CC1A4E4B485340BAF2160AD4A43F40D18D1A4F334B53401501DF95A2A83F40A5E6A180F34B5340C2818196DBAA3F4043C7BF843E4C5340F6B0C9187DAE3F40"
where you can clearly see the rid showing the sequence in which the line
segments appear.
Hope this helps.
- pradeep B V
Thanks a lot,
>
>
> Pradeep B V wrote:
> > Hi Nguyen,
> >
> >
> > But I can't find path between 2 points (one of them is a
> > coordinate on the
> > road, not the node). My problem is here. I don't know how to
> > handle the
> > start point and end point if they're not nodes.
> >
> >
> >
> > From what you say no and what you said earlier ...
> >
> >
> > "My problem here is drawing the shortest path on the map. The user
> > clicked on 2 points, but the shortest path begins and ends with 2
> > nodes. The shortest path between 2 nodes is ok. But it's a matter with
> > the start path (the path contains start point) and the end path (the
> > path contains end point) because the user don't click exactly the
> > available coordinate on your roads. If both start path and end path
> > are multilinestring which are not straight, how can you draw exactly
> > that path from the user's start clicked point to his end clicked point?
> "
> >
> > I gather this.
> >
> > 1. you have the shortest path available between two nodes.
> > 2. but they do not contain the points cliked by the user (i.e the
> > start point and the end point) which are different from the start node
> > and end node of the shortest path.
> > 3. the problem now is to draw the lines between the start point to the
> > start node and end node to end point to complete the route.
> >
> > This can be handled by simply appending the start and end points to
> > the path-linestring at the beginning and the end of the path.
> >
> >
> > - Pradeep B V
> >
> >
> > >> Anton A. Patrushev wrote:
> > >> >
> > >> > Hi Nguyen
> > >> >
> > >> > You can use Distance function of PostGIS.
> > >> > Here is an example:
> > >> >
> > >> > SELECT Distance(geom_column, GeomFromText('POINT(x y)',
> > >> > projection_code)) AS dist
> > >> > FROM table_name
> > >> > ORDER BY dist LIMIT 1";
> > >> >
> > >> > where
> > >> > geom_column - the name of the column which contains geometry;
> > >> > 'x y' - coordinates of your point divided by space;
> > >> > projection_code - the code of projection you're using;
> > >> > table_name - the name of the table.
> > >> >
> > >> > It will search in entire table, so it will be nice to apply a
> > filter to
> > >> > the search, but anyway you'll have an idea.
> > >> >
> > >> > Good luck!
> > >> >
> > >> > Anton A. Patrushev
> > >> > Software Engineer
> > >> > Orkney, Inc.
> > >> > 6F JA-Kyosai Yokohama Building,
> > >> > 1-2 Kaigandori, Naka, Yokohama 231-0002 JAPAN
> > >> > Tel 81-45-228-3320 Fax 81-45-228-3321
> > >> > www.orkney.co.jp <http://www.orkney.co.jp>
> > >> >
> > >> >> Hi everybody,
> > >> >>
> > >> >> I'm doing a project which needs to find a shortest path
> > between two
> > >> >> user's clicked points. I already installed
> > successfully pgRouting.
> > >> >>
> > >> >> I use this function:
> > >> >> SELECT * from shortest_path_astar('SELECT gid as id, source,
> > target,
> > >> >> length as cost, x1, y1, x2, y2 FROM roads', 3, 7, false,
> > false);
> > >> >>
> > >> >> But the problem is that I can't identify exactly the start
> > node and
> > >> >> end node to find path (How to identify node 3 and node 7?).
> > I already
> > >> >> have the start point and end point of the user. But they
> > don't select
> > >> >> correctly the points on my roads. So I can't draw the path
> > correctly
> > >> >> on the map (The path begins with their start clicked point
> > and ends
> > >> >> with their end clicked point)
> > >> >>
> > >> >> Anybody has experiences with this? Please help me!
> > >> >>
> > >> >> Thanks so much.
> > >> >> _______________________________________________
> > >> >> postgis-users mailing list
> > >> >> postgis-users at postgis.refractions.net
> > <mailto:postgis-users at postgis.refractions.net>
> > >> >> http://postgis.refractions.net/mailman/listinfo/postgis-users
> > >> >>
> > >> >
> > >> > _______________________________________________
> > >> > postgis-users mailing list
> > >> > postgis-users at postgis.refractions.net
> > <mailto:postgis-users at postgis.refractions.net>
> > >> > http://postgis.refractions.net/mailman/listinfo/postgis-users
> > <http://postgis.refractions.net/mailman/listinfo/postgis-users>
> > >> >
> > >> >
> > >>
> > >> --
> > >> View this message in context:
> > >>
> >
> http://www.nabble.com/How-to-identify-start-node-and-end-node-in-shortest_path_astar-when-the-user-click-2-points-on-the-map--tf2349095.html#a6542912
> > >> Sent from the PostGIS - User mailing list archive at Nabble.com
> > <http://Nabble.com>.
> > >>
> > >> _______________________________________________
> > >> postgis-users mailing list
> > >> postgis-users at postgis.refractions.net
> > <mailto:postgis-users at postgis.refractions.net>
> > >> http://postgis.refractions.net/mailman/listinfo/postgis-users
> > >>
> > >
> > >
> > >
> > > --
> > > Pradeep B V
> > >
> > > _______________________________________________
> > > postgis-users mailing list
> > > postgis-users at postgis.refractions.net
> > <mailto:postgis-users at postgis.refractions.net>
> > > http://postgis.refractions.net/mailman/listinfo/postgis-users
> > >
> > >
> >
> > --
> > View this message in context:
> >
> http://www.nabble.com/How-to-identify-start-node-and-end-node-in-shortest_path_astar-when-the-user-click-2-points-on-the-map--tf2349095.html#a6543409
> > Sent from the PostGIS - User mailing list archive at Nabble.com
> > <http://Nabble.com>.
> >
> > _______________________________________________
> > postgis-users mailing list
> > postgis-users at postgis.refractions.net
> > <mailto:postgis-users at postgis.refractions.net>
> > http://postgis.refractions.net/mailman/listinfo/postgis-users
> >
> >
> >
> >
> > --
> > Pradeep B V
>
>
--
Pradeep B V
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20060928/31a02a82/attachment.html>
More information about the postgis-users
mailing list