This discussion is archived
12 Replies Latest reply: May 15, 2013 7:07 AM by Luc Van Linden RSS

how to find dangles

1005896 Newbie
Currently Being Moderated
Hi,
I'm trying to find line with dangles. Has anyone advice how to built the query?
My first idea was something like this, but I know that's not my result.

*create table line_dangles as
select l1.geom, l1.objectid l1_id
from line l1, line l2
where l1.objectid <> l2.objectid and SDO_TOUCH(l1.geom,l2.geom) <> 'TRUE';*

I'm new spatial database so I'll appreciate some help.

Thx Eva
  • 1. Re: how to find dangles
    Stefan Jager Journeyer
    Currently Being Moderated
    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 Newbie
    Currently Being Moderated
    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 Journeyer
    Currently Being Moderated
    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 line-id 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 :-))
    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_vertices-1),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;
    And now you can find the unique points in the table line_points, which will tell you which lines are dangling.

    HTH,
    Stefan
  • 4. Re: how to find dangles
    1005896 Newbie
    Currently Being Moderated
    Hi Stefan,
    Thanks for your help, I'll try it :-)

    Eva
  • 5. Re: how to find dangles
    NoelKhan Journeyer
    Currently Being Moderated
    Eva,

    When straight lines connect tip-to-tail, 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 table-name here"
               TABLE(SDO_UTIL.GETVERTICES( Geom )) v       -- "your geometry-column here"
    )
    GROUP BY xy
    HAVING COUNT(xy) = 1
  • 6. Re: how to find dangles
    Luc Van Linden Pro
    Currently Being Moderated
    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.

    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
      ;
    B. The use of SDO_JOIN wil list pair up the lines that touch eachother.
    (assuming they will only touch at the end not one touching at the inner part of the other line).
     
    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;
    The a.rowid != b.rowid might be redundant here as a line cannot TOUCH itself.

    C. Combined we do the following
      WITH
    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
      ;
    we use the with clause to define the l_vertices using the getvertices function
    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 Journeyer
    Currently Being Moderated
    Hi Luc,

    I desperately need to brush up my SQL knowledge:
    Stefan, yes even with SQL you can get a linestring start and endpoint.

    select v.row_id, v.id, v.x, v.y, max(v.id ) OVER (PARTITION BY v.row_id ) last_v
    Completely missed the OVER PARTITION BY, when I was playing with this..... oh well, I know what to do now ;-)

    Thanks a lot though, this will come in pretty handy :-)

    Cheers,
    Stefan
  • 8. Re: how to find dangles
    Stefan Jager Journeyer
    Currently Being Moderated
    Hi Luc,

    I started playing with this a little bit myself, and came up with this:
    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
    ;
    The endpoints1 and endpoints2 are in there twice to avoid ORA-32036: unsupported case for inlining of query name in WITH clause, which keeps popping up. But with the version above, I'm getting ORA-13249: Error in join: check spatial table/indexes.

    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 Pro
    Currently Being Moderated
    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
     WHERE c.rowid1 = a.row_id AND c.rowid2 = b.row_id 
    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)).
    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
    table(sdo_join('endpoints1', 'point', 'endpoints2', 'point')) c,
    change to
    table(sdo_join('testgeom', 'geometry', 'testgeom', 'geometry')) c,
    This will allow the sdo_join to use the spatial index.

    Secondly you need to include the rowid of the testgeom table in the l_vertices definition:
    with 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 
    )
    Third, make sure the endpoints1 and endpoints2 contain also that row_id
    select lv1.row_id,  lv1.id, sdo_geom ....
    ...
    select lv2.row_id,  lv2.id, sdo_geom ....
    last, change the join in the main query as :

    {
    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 re-joining 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 Journeyer
    Currently Being Moderated
    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 ORA-32036 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 Pro
    Currently Being Moderated
    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
    )
    WHERE sumstart = 0 OR sumend = 0;
    This way you will know, the id of the dangling line and also at which end it is dangling (the one with the 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 Pro
    Currently Being Moderated
    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).
    PSEUDOCODE:
    
    sdo_xor (mulitpoint_enpoints_line, sdo_intersection (line, multipoint_endpoints_touching_lines))
    If this XOR returns a geometry, you should have a dangling line.
    If it returns NULL, the line should be connected at both ends.

    Regards

    Luc

Legend

  • Correct Answers - 10 points
  • Helpful Answers - 5 points