This content has been marked as final.
Show 12 replies

1. Re: how to find dangles
Stefan Jager May 6, 2013 2:47 PM (in response to 1005896)Hi Eva,
The query you've tried is probably not going to work. Can you explain a little bit more about your data? For example: a line that ends on another line, but between two vertices, is that considered a dangle? Or is a dangle only the start or endpoint of a line that does not have another start or endpoint near it?
Depending on these kinds of business requirements, I would probably start thinking along the lines of selecting all the start and endpoints of my linework and then checking whther something else is near or on top of them. You may find this thread interesting: {thread:id=2525154}. Luc's answer on Ronnie's question is very similar to what you are after, I think.
HTH,
Stefan 
2. Re: how to find dangles
1005896 May 6, 2013 3:43 PM (in response to Stefan Jager)Hi Stefan,
thank you for your answer. The dangle, what I want to find is the start or endpoint of a line that does not have another start or endpoint. But I would like to figure it out without using topology model, because I'm trying to compare work with spatial model and work with topology model in my esey. Do you have any idea how to do that?
Eva 
3. Re: how to find dangles
Stefan Jager May 8, 2013 3:32 AM (in response to 1005896)Hi Eva,
If you do not want to use Topology or LRS, it's going to be a bit more difficult. In such a case I would use this kind of approach:
1. Collect all start and endpoints, making sure the lineid is stored with them
2. Do a duplicate rows query.
Any points that do not have a duplicate, are dangles. Checking whether geometry equals other geometry can be done with the [url http://docs.oracle.com/cd/E11882_01/appdev.112/e11830/sdo_operat.htm#BGEBCEJE]SDO_EQUAL operator.
To get the start and endpoints of your linework, the easiest thing to do is to create two small functions (it's a bit complicated to get the start and endpoint with pure SQL, I'm not even sure it can be done as a subquery). So something like this, which is NOT TESTED and just off the top of my head (Right now I have no Oracle instance available :))
And now you can find the unique points in the table line_points, which will tell you which lines are dangling.CREATE OR REPLACE FUNCTION getStartPoint(geom IN MDSYS.SDO_GEOMETRY) RETURN MDSYS.SDO_GEOMETRY IS g_type NUMBER; BEGIN g_type:=geom.SDO_GTYPE; IF (g_type = 2002) or (g_type = 2006) THEN RETURN MDSYS.SDO_GEOMETRY(2001,geom.SDO_SRID,SDO_POINT(geom.SDO_ORDINATES(1),geom.SDO_ORDINATES(2),NULL),NULL,NULL); ELSE RETURN NULL; END IF; END; / CREATE OR REPLACE FUNCTION getEndPoint(geom IN MDSYS.SDO_GEOMETRY) RETURN MDSYS.SDO_GEOMETRY IS g_type NUMBER; num_vertices NUMBER; BEGIN g_type:=geom.SDO_GTYPE; num_vertices:=geom.SDO_ORDINATES.count; IF (g_type = 2002) or (g_type = 2006) THEN RETURN MDSYS.SDO_GEOMETRY(2001,geom.SDO_SRID,SDO_POINT(geom.SDO_ORDINATES(num_vertices1),geom.SDO_ORDINATES(num_vertices),NULL),NULL,NULL); ELSE RETURN NULL; END IF; END; / create table line_points ( line_id NUMBER, points SDO_GEOMETRY ); insert into line_points select l.objectid, getStartPoint(l.geom) from line l; insert into line_points select l.objectid, getEndPoint(l.geom) from line l;
HTH,
Stefan 
4. Re: how to find dangles
1005896 May 8, 2013 5:03 AM (in response to Stefan Jager)Hi Stefan,
Thanks for your help, I'll try it :)
Eva 
5. Re: how to find dangles
NoelKhan May 8, 2013 12:12 PM (in response to 1005896)Eva,
When straight lines connect tiptotail, the shared coordinate occurs twice (e.g., A > B, B> C). If your data is comprised of straight lines only (no curves), you could use the following query.
Stefan's code works with straight lines and curves.
Regards,
Noel
SELECT DISTINCT( xy ), COUNT(*) FROM ( SELECT ROUND(v.x, 0 )','ROUND(v.y, 0 ) xy  "set precision here" FROM TableName t,  "your tablename here" TABLE(SDO_UTIL.GETVERTICES( Geom )) v  "your geometrycolumn here" ) GROUP BY xy HAVING COUNT(xy) = 1

6. Re: how to find dangles
Luc Van Linden May 8, 2013 7:29 PM (in response to 1005896)Hi Eva
Stefan has given you already some good direction using some functions.
Should you want to use only LOCATOR functionality (NO LRS etc) and also only use plain SQL here is a possible solution.
Stefan, yes even with SQL you can get a linestring start and endpoint. (see part A below).
A. Here is a simple SQL Locator (non LRS) approach to get start & endpoint from a line geometry.
B. The use of SDO_JOIN wil list pair up the lines that touch eachother.WITH l_vertices as (select v.row_id, v.id, v.x, v.y, max(v.id ) OVER (PARTITION BY v.row_id ) last_v  max analitical function to get last vertex index from ( select rowid row_id, t.id, t.x , t.y from line l, TABLE(SDO_UTIL.GETVERTICES(l.geometry)) t  getvertices table function ) v ) select lvs.row_id, lvs.id, lvs.x start_x, lvs.y start_y, lve.id, lve.x end_x, lve.y end_y from ( select lv.row_id, lv.id, lv.x, lv.y from l_vertices lv where lv.id =1  vertexindex = 1 is the startpoint ) lvs, ( select lv.row_id, lv.id, lv.x, lv.y from l_vertices lv where lv.id =lv.last_v  vertexindex = last_v (last vertex index) is the endpoint ) lve where lvs.row_id = lve.row_id  join on the rowid to get start & endpoint together in a row ;
(assuming they will only touch at the end not one touching at the inner part of the other line).
The a.rowid != b.rowid might be redundant here as a line cannot TOUCH itself.select a.id, a.geom, a.geom.sdo_srid srid, b.id idb, b.geom as geomb from table(sdo_join('LINE', 'GEOMETRY', 'LINE', 'GEOMETRY', 'mask=TOUCH')) c, LINE a, LINE b WHERE c.rowid1 = a.rowid AND c.rowid2 = b.rowid AND a.rowid != b.rowid;
C. Combined we do the following
we use the with clause to define the l_vertices using the getvertices functionWITH l_vertices  SUBQUERY l_vertices as ( select v.row_id, v.id, v.vix, v.x, v.y, max(v.vix ) OVER (PARTITION BY v.row_id ) last_v  max analitical function to get last vertex index from ( select rowid row_id, l.id, t.id vix, t.x , t.y from LINE l, TABLE(SDO_UTIL.GETVERTICES(l.geometry)) t  getvertices table function  change LINE to your tablename and GEOMETRY to your geometry field ) v ), al_s_e_vertices  SUBQUERY al_s_e_vertices based on l_vertices as ( select lvs.row_id, lvs.id, lvs.vix s_vix, lvs.x start_x, lvs.y start_y, lve.vix e_vix, lve.x end_x, lve.y end_y from ( select lv.row_id, lv.id, lv.vix, lv.x, lv.y from l_vertices lv where lv.vix =1  vertexindex = 1 is the startpoint ) lvs, ( select lv.row_id, lv.id, lv.vix, lv.x, lv.y from l_vertices lv where lv.vix =lv.last_v  vertexindex = last_v (last vertex index) is the endpoint ) lve where lvs.row_id = lve.row_id ), bl_s_e_vertices  SUBQUERY bl_s_e_vertices based on l_vertices as ( select lv.row_id, lv.id, lv.vix, lv.x, lv.y from l_vertices lv where lv.vix =1  vertexindex = 1 is the startpoint UNION ALL select lv.row_id, lv.id, lv.vix, lv.x, lv.y from l_vertices lv where lv.vix =lv.last_v  vertexindex = last_v (last vertex index) is the endpoint ) select a.ID, sum(atS), sum(atE)  Main query using SDO_JOIN (self join on LINE, LINE) in combination with the derived (from LINE) subqueries al_s_e_vertices a, bl_s_e_vertices b from ( select l.*, CASE WHEN (start_x = x AND start_y = y) THEN 1 ELSE 0 END atS, CASE WHEN (end_x = x AND end_y = y) THEN 1 ELSE 0 END atE FROM ( select a.id, a.row_id, a.s_vix, a.start_x, a.start_y, a.e_vix, a.end_x, a.end_y, b.id b_id, b.row_id b_row_id, b.vix, b.x, b.y from table(sdo_join('LINE', 'GEOMETRY', 'LINE', 'GEOMETRY', 'mask=TOUCH')) c,  change LINE to your tablename and GEOMETRY to your geometry field al_s_e_vertices a, bl_s_e_vertices b WHERE c.rowid1 = a.row_id AND c.rowid2 = b.row_id AND a.row_id != b.row_id ) l ) a group by ID ;
from that we define the al_s_e_vertices which are the lines with their start and endpoint info
and we defined the bl_s_e_vertices but collected via the union all on the start and endpoint
These are then joined on the result of the SDO_JOIN as A and B (hence the reason why the subqueries in the With definition contain the original ROWIDs
This means that for every line A we know which other line(s) B is (are) touching (either at B's start or end).
For every TOUCH B at A start point or A end point a 1 value is given for atS(tart) or atE(nd).
Finally we group by on A.ID and summing the atS and summing the atE.
This means that we know how many Bs are touching at the start of A and how many are touching at the end of A.
Dangles A should be those that have 0 for one of the sums.
Those LINES that are not listed at all, are actually individually isolated lines (they were not selected at all due to the sdo_join)
Should they be listed also, they should be rejoined at the end.
You only have to replace your table name and geometry field name in 2 places above as indicated in the comments. This assumes you have an ID field also.
One small remark, this approach assumes that no line is touching another's inner part (between start and end).
Hope this helps.
Luc 
7. Re: how to find dangles
Stefan Jager May 9, 2013 2:25 AM (in response to Luc Van Linden)Hi Luc,
I desperately need to brush up my SQL knowledge:
Stefan, yes even with SQL you can get a linestring start and endpoint.
Completely missed the OVER PARTITION BY, when I was playing with this..... oh well, I know what to do now ;)
select v.row_id, v.id, v.x, v.y, max(v.id ) OVER (PARTITION BY v.row_id ) last_v
Thanks a lot though, this will come in pretty handy :)
Cheers,
Stefan 
8. Re: how to find dangles
Stefan Jager May 15, 2013 7:08 AM (in response to Luc Van Linden)Hi Luc,
I started playing with this a little bit myself, and came up with this:
The endpoints1 and endpoints2 are in there twice to avoid ORA32036: unsupported case for inlining of query name in WITH clause, which keeps popping up. But with the version above, I'm getting ORA13249: Error in join: check spatial table/indexes.with l_vertices as ( select tg.id, tg.geometry, t.id v_id, t.x, t.y from testgeom tg, TABLE(SDO_UTIL.GETVERTICES(tg.geometry)) t ), endpoints1 as ( select lv1.id, sdo_geometry(2001,lv1.geometry.sdo_srid,sdo_point_type(lv1.x,lv1.y,null),null,null) point, 'startpoint' p_type from l_vertices lv1 where lv1.v_id=1 UNION ALL select lv2.id, sdo_geometry(2001,lv2.geometry.sdo_srid,sdo_point_type(lv2.x,lv2.y,null),null,null) point, 'endpoint' p_type from l_vertices lv2 where lv2.v_id=SDO_UTIL.GETNUMVERTICES(lv2.geometry) ), endpoints2 as ( select lv1.id, sdo_geometry(2001,lv1.geometry.sdo_srid,sdo_point_type(lv1.x,lv1.y,null),null,null) point, 'startpoint' p_type from l_vertices lv1 where lv1.v_id=1 UNION ALL select lv2.id, sdo_geometry(2001,lv2.geometry.sdo_srid,sdo_point_type(lv2.x,lv2.y,null),null,null) point, 'endpoint' p_type from l_vertices lv2 where lv2.v_id=SDO_UTIL.GETNUMVERTICES(lv2.geometry) ) select a.id, b.id, a.point, a.p_type from table(sdo_join('endpoints1', 'point', 'endpoints2', 'point')) c, endpoints1 a, endpoints2 b WHERE c.rowid1 = a.id AND c.rowid2 = b.id AND a.id != b.id ;
Now since these are virtual tables, I can't create a spatial index on them of course, but this does not seem to happen in your code, right? The whole thing works if you use Noel's solution (where you do a check on the combined X and Y values through a simple DISTINCT  but I don't think that's a very elegant solution, allthough it works :) ).
Any thoughts on what I'm doing wrong? There is a spatial index on the base table, and it is valid according to Oracle. I'm using 11.2.0.1.0, by the way.
Thanks,
Stefan 
9. Re: how to find dangles
Luc Van Linden May 15, 2013 8:29 AM (in response to Stefan Jager)Stefan
The sdo_join always works on the spatial indexes of geometries of the tables you have passed in the SDO_JOIN.
This results in rowid1, rowid2 resultset C , with rowid1 the rowids from the first table and the rowid2 the rowid from the second table (passed in the sdo_join). Nothing more, nothing less.
These 2 rowids (from C) are used to join back to the base tables (A and B) to collect additional fields/columns via the
What I did in the example is using the subqueries to be joined back (as they already contain more results on their own (the getvertices stuff)).WHERE c.rowid1 = a.row_id AND c.rowid2 = b.row_id
In order to be able to join them to the resultset (C) from the SDO_JOIN, I included the rowid from the basetables passed into to the sdo_join.
What you have to do is to
change totable(sdo_join('endpoints1', 'point', 'endpoints2', 'point')) c,
This will allow the sdo_join to use the spatial index.table(sdo_join('testgeom', 'geometry', 'testgeom', 'geometry')) c,
Secondly you need to include the rowid of the testgeom table in the l_vertices definition:
Third, make sure the endpoints1 and endpoints2 contain also that row_idwith l_vertices as ( select tg.rowid as row_id, tg.id, tg.geometry, t.id v_id, t.x, t.y from testgeom tg, TABLE(SDO_UTIL.GETVERTICES(tg.geometry)) t )
last, change the join in the main query as :select lv1.row_id, lv1.id, sdo_geom .... ... select lv2.row_id, lv2.id, sdo_geom ....
{
WHERE c.rowid1 = a.row_id AND c.rowid2 = b.row_id ...
}
As a side note:
You are using the sdo_join as a PRIMARY SPATIAL FILTER only on the MBR's as no MASK is applied.
Should the geometries of the testgeom table be points, it would be the same as using an ANYINTERACT mask which is for points also an EQUAL mask. So be careful on using an appropriate mask if required.
This is just a test, right, this is not giving you dangles.
Luc
BTW check the bottom example on the use of (to remove redundant geometries) SDO_JOIN in this thread: query is taking too much time
You will see that rejoining back to table A, B is not always necessary if you do not need to (re)collect other columns then the ROWID.
Edited by: Luc Van Linden on May 15, 2013 3:22 PM 
10. Re: how to find dangles
Stefan Jager May 15, 2013 8:26 AM (in response to Luc Van Linden)Hi Luc,
This is just a test, right, this is not giving you dangles.
Yes, this is just me playing around (already said a few posts earlier that I needed to brush up on my SQL ;) ). And so I started playing with this example, to see if I could get the dangles with pure SQL (well  besides the calls to SDO_UTIL for the vertices, that is...), and my first results gave me a neat little table with all the endpoints of my lines, so thought I could take that further (that's when ORA32036 started popping up :( ). I'll try it with the ROWID's and the rest.
Thanks!
Stefan
PS. I guess if I have more questions I'll start my own thread, I've kind of hijacked this one :o 
11. Re: how to find dangles
Luc Van Linden May 15, 2013 8:49 AM (in response to Stefan Jager)Stefan
If you take my original C.example, just only have to change the sql in 2 places:
1. in the l_vertices definition on line 9: LINE > testgeom
2. in the main query in the sdo_join: sdo_join('LINE', 'GEOMETRY', 'LINE', 'GEOMETRY', 'mask=TOUCH')) LINE > testgeom
The main query needs an additional select and where filter to get the dangling lines (as explained before).
select * from (
select a.ID, sum(atS) as sumstart, sum(atE) as sumend from ( select l.*, CASE WHEN (start_x = x AND start_y = y) THEN 1 ELSE 0 END atS, CASE WHEN (end_x = x AND end_y = y) THEN 1 ELSE 0 END atE FROM ( select a.id, a.row_id, a.s_vix, a.start_x, a.start_y, a.e_vix, a.end_x, a.end_y, b.id b_id, b.row_id b_row_id, b.vix, b.x, b.y from table(sdo_join('LINE', 'GEOMETRY', 'LINE', 'GEOMETRY', 'mask=TOUCH')) c, al_s_e_vertices a, bl_s_e_vertices b WHERE c.rowid1 = a.row_id AND c.rowid2 = b.row_id AND a.row_id != b.row_id ) l ) a group by ID
This way you will know, the id of the dangling line and also at which end it is dangling (the one with the 0).) WHERE sumstart = 0 OR sumend = 0;
Again, this does not include isolated (single) lines only the dangling ones.
Luc
Edited by: Luc Van Linden on May 15, 2013 3:48 PM 
12. Re: how to find dangles
Luc Van Linden May 15, 2013 9:07 AM (in response to Stefan Jager)Stefan
As s a side note:
SDO_UTIL is licensed under the Oracle LOCATOR so that is ok to use anyway.
A Spatial way could have been to UNION aggregate the endpoints of the touching lines into a multipoint,
Perform an sdo_xor with the line_endpoints (also multipoint) and the sdo_intersection of the line and the touching lines endpoints (multipoint).
If this XOR returns a geometry, you should have a dangling line.PSEUDOCODE: sdo_xor (mulitpoint_enpoints_line, sdo_intersection (line, multipoint_endpoints_touching_lines))
If it returns NULL, the line should be connected at both ends.
Regards
Luc