12 Replies Latest reply: May 15, 2013 9:07 AM by Luc Van Linden RSS

    how to find dangles

    1005896
      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
          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
            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
              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
                Hi Stefan,
                Thanks for your help, I'll try it :-)

                Eva
                • 5. Re: how to find dangles
                  NoelKhan
                  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
                    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
                      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
                        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
                          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
                            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
                              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
                                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