Sorting and merging geometries in Oracle Spatial

Consider a requirement where an unsorted set of geometries needs to be merged into a single geometry. Take for instance the following set of geometries where:

  • a Red dot indicates the startpoint
  • The arrow indicates the drawing direction
  • The label “1-50″ indicates the order of drawing and an identifier for the geometry
Sample set 1

Sample set 1

Sample set 2

Sample set 2

Both of these geometries should be merged into the following:

Result set 1

Result set 1

Oracle lets you create your own aggregate function enabling a nice flexible solution, let’s try to create an aggregate function SDE_MERGE enabling us to create a 3002-gtype geometry or in G/Technology terms a ‘CompositePolylineGeometry’, (G3E_COMPONENT.G3E_TYPE=4). Our aggregate function must be able to:

    • Change the order of geometries. The order in which the geometries are drawn may not be the order in which the geometries need to be merged to create the resulting geometry.
    • Change direction of a geometry. Geometries may have different drawing directions, but when appending geometries to each other to create a resulting geometry, the direction needs to be the same.
    • Detect not supported situations:
      1. A closed set of Geometries
      2. Geometries with multiple connections
      3. A set of disjoint geometries

The picture below shows a closed set of Geometries, this set of geometry cannot be merged into a 3002-gtype geometry so when this situation is encountered SDE_MERGE should return null:

Closed set

Closed set

Also, if there are more then 2 geometries connecting to each other, no 3002-gtype geometry can be created:

Multiple connections

Multiple connections

When a set of geometries is not connected/disjoint, null should be returned:

Disjoint set

Disjoint set

Here’s the header of the SDO_MERGE function:

create or replace type SDE_MERGE_i as object
(
  geom 	mdsys.sdo_geometry,

  STATIC FUNCTION ODCIAggregateInitialize
  ( sctx IN OUT SDE_MERGE_i
  ) RETURN number,

  MEMBER FUNCTION ODCIAggregateIterate
  (   self IN OUT SDE_MERGE_i
    , item IN mdsys.sdo_geometry
  )	RETURN number,

  MEMBER FUNCTION ODCIAggregateTerminate
  (   self IN 	  SDE_MERGE_i
    , ret  OUT    mdsys.sdo_geometry
    , flgs IN     number
  ) RETURN number,

  MEMBER FUNCTION ODCIAggregateMerge
  (   self IN OUT SDE_MERGE_i
    , ctx2 IN     SDE_MERGE_i
  ) RETURN number
);

Our SDE_MERGE function has a single member geom, a geometry which we will use to store all geometries to be merged and return the resulting geometry. When SDE_MERGE is called, Oracle first calls 'ODCIAggregateInitialize', this is were the initial geometry is initialized. Then, for each geometry in the applied order, 'ODCIAggregateIterate' is called and when all geometries have been entered, Oracle will call 'ODCIAggregateTerminate'. Sorting and merging geometries can only take place after all geometries are known so this is where the actual sorting and merging of geometries is done. Before this is called, we need some kind of data structure to store all geometries to be processed later. This is were a 3006-gtype geometry comes in, we will store all temporary geometries in it and enumerate this 3006-geometry when we need to do the sorting and merging.

This is all we need in 'ODCIAggregateIterate':

MEMBER FUNCTION ODCIAggregateIterate
(
  self IN OUT SDO_MERGE_i
, item IN 	mdsys.sdo_geometry
) return number
IS
BEGIN
  if( self.geom.SDO_ORDINATES is null)
  then
	SELF.geom := item;
	return( ODCIConst.Success);
  end if;

  SELF.geom := sdo_util.append ( SELF.geom, item);
  return( ODCIConst.Success);
END;

When all items are encountered Oracle calls the ‘ODCIAggregateTerminate’-function where the temporary 3006-gtype/multi-line geometry is enumerated, all 3002-gtype geometries in it are sorted and merged into a 3002-gtype geometry.

Implementation

The real work of this solution is done in the 'ODCIAggregateTerminate'-function where all the geometries in the temporary 3006-gtype geometry are enumerated to see if they can be merged into a single geometry. If they can, the order and direction of all the geometries is changed where needed, and then merged into a single geometry. The complete solution can be downloaded from here.

Testing

While the actual target data is G/Technology driven, I will use a table DB_ORIGIN_PATHS for testing purposes :

CREATE TABLE DB_ORIGIN_PATHS
(
  ID          NUMBER,
  PATH_FID    NUMBER(10),
  HASH        INTEGER,
  GEOM        MDSYS.SDO_GEOMETRY,
  GEOM2D      MDSYS.SDO_GEOMETRY
);

The geometries are rendered using Geoserver/Openlayers so I can quickly inspect results without the hassle of publishing data with G/Technology. Each geometry inserted is converted to a 2D-geometry because Geoserver has problems rendering 3D-arcs, this 2D-geometry then is used to inspect the results:

CREATE OR REPLACE TRIGGER DB_ORIGIN_PATHS_AfterIU BEFORE INSERT or UPDATE ON DB_ORIGIN_PATHS
for each row
begin
  :new.geom2d := SDO_CS.MAKE_2D( :new.GEOM);
end;
/

Furthermore, because I don’t have a reference to a fid of the applied geometries inside my 'SDE_MERGE'-implementation, I need some way of identifying the geometries. That’s why I introduced a ‘Hash’-value for each one :

create or replace function GETHASHCODE( theGeom mdsys.sdo_geometry)
	return int
as
    p1 		mdsys.sdo_geometry;
    p2 		mdsys.sdo_geometry;
    hash	int;
begin
  p1 := SDO_LRS.GEOM_SEGMENT_START_PT( theGeom);	
  p2 := SDO_LRS.GEOM_SEGMENT_END_PT  ( theGeom);
    
  hash := p1.sdo_ordinates( 1) + p1.sdo_ordinates( 2) + p2.sdo_ordinates( 1) + p2.sdo_ordinates( 2);
  return( hash);    
end;

Now onto our first testset, 3 basic lines :

BEGIN
delete from DB_ORIGIN_PATHS;

insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
  select 1, 1, SDO_GEOMETRY( 3002, NULL, NULL, 
    SDO_ELEM_INFO_ARRAY( 1,2,1), 
    SDO_ORDINATE_ARRAY( 10,10,0, 20,10,0 ))
from dual;            

insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
  select 2, 2, SDO_GEOMETRY( 3002, NULL, NULL, 
    SDO_ELEM_INFO_ARRAY( 1,2,1), 
    SDO_ORDINATE_ARRAY( 20,10,0, 30,10,0))
from dual;

insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
  select 3, 3, SDO_GEOMETRY( 3002, NULL, NULL, 
    SDO_ELEM_INFO_ARRAY( 1,2,1), 
    SDO_ORDINATE_ARRAY( 30,10,0, 40,10,0)) 
from dual;

update DB_ORIGIN_PATHS set hash = GETHASHCODE( geom);    
commit;
END;

This renders into this :

Test set 1

Test set 1

Merging the geometries and deleting the old ones:

BEGIN   
  insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
    select 100, 100, SDE_MERGE( geom) from rr.DB_ORIGIN_PATHS;

  update DB_ORIGIN_PATHS set hash = GETHASHCODE( geom);
  delete from DB_ORIGIN_PATHS where id < 100; 
  commit;
END;

Renders into:

Result set 1

Result set 1

Our second test set :

BEGIN
  delete from DB_ORIGIN_PATHS;

  insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
    select 1, 1, SDO_GEOMETRY( 3002, NULL, NULL, 
      SDO_ELEM_INFO_ARRAY( 1,2,1), 
      SDO_ORDINATE_ARRAY( 10,10,0, 20,10,0 )) 
  from dual;

  insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
    select 2, 2, SDO_GEOMETRY( 3002, NULL, NULL, 
      SDO_ELEM_INFO_ARRAY( 1,2,1), 
      SDO_ORDINATE_ARRAY( 30,10,0, 20,10,0)) 
  from dual;

  insert into DB_ORIGIN_PATHS( id, path_fid, geom) 
    select 3, 3, SDO_GEOMETRY( 3002, NULL, NULL, 
      SDO_ELEM_INFO_ARRAY( 1,2,1), 
      SDO_ORDINATE_ARRAY( 30,10,0, 40,10,0)) 
  from dual;		

  update DB_ORIGIN_PATHS set hash = GETHASHCODE( geom);
  commit;
END;

renders into this :

Test set 2

Test set 2

Again, merging the geometries and deleting the old ones:

BEGIN   
  insert into DB_ORIGIN_PATHS( id, path_fid, geom) select 100, 100, SDE_MERGE( geom) from rr.DB_ORIGIN_PATHS;	            
  update DB_ORIGIN_PATHS set hash = GETHASHCODE( geom);
  delete from DB_ORIGIN_PATHS where id < 100;    
  commit;
END;

Renders into:

Result set 2

Result set 2

I have repeated this for a couple of geometries where the set is listed on the left and merged result on the right :

Test set Result
sample_set3

Sample set 3

result_set3

Result set 3

sample_set4

Sample set 4

result_set4

Result set 4

sample_set5

Sample set 5

result_set5

Result set 5

sample_set6

Sample set 6

result_set6

Result set 6

sample_set7

Sample set 7

result_set7

Result set 7

Background

KPN Netherlands has ‘Direct Buried Cables’, fiber cables lying in the ground without any protection. Direct buried cables are registered as Copper Cables contained by a Path Feature (fno=3500), so these cables themselves have no geometry. If you want to create real Fiber Cable-features with a geometry, you need to fetch and merge the geometries from the containing paths.

Direct Buried cables are identified by it’s ID attribute, the following Ad-Hoc query shows the paths containing a Direct Buried cable with id ‘407329’ :

select	GC_CONTAIN.g3e_ownerfno g3e_fno
	,	GC_CONTAIN.g3e_ownerfid g3e_fid
	,	3510 g3e_cno
	,	1 g3e_cid
	,	GC_CONTAIN.g3e_ownerfno
	,	GC_CONTAIN.g3e_fid cable_fid
	,	GC_CBL.total_size
	,	GC_CBL.id
	from GC_CONTAIN
	inner join GC_CBL on GC_CBL.g3e_fid = GC_CONTAIN.g3e_fid
	  and GC_CONTAIN.g3e_ownerfno = 3500
  where GC_CBL.id = '407329'

Running this query results in the following resultset:

Direct Buried cable in G/Technology

Direct Buried cable in G/Technology

The result shows the geometries of the Paths containing the cables, the actual Direct Buried cables themselves have no geometry. The first approach I took to merge these Path-geometries into a new Fiber Cable geometry was using the 'SDO_AGGR_UNION'-operator: like the following code snippet illustrates:

INSERT INTO B$GC_FCBL_L ( G3E_ID, G3E_FNO, G3E_FID, G3E_CNO, G3E_CID, G3E_GEOMETRY )
SELECT gc_fcbl_l_seq.nextval, 7200, 64169619, 7210, 1, geom
FROM
(
  select SDO_AGGR_UNION( SDOAGGRTYPE( B$GC_PATH_L.g3e_geometry, cTOLERANCE)) geom from B$GC_PATH_L
  WHERE g3e_fid IN (
  SELECT DISTINCT gc_contain.g3e_ownerfid
    FROM gc_cbl
      INNER JOIN gc_contain ON gc_contain.g3e_fid = gc_cbl.g3e_fid
	  AND gc_contain.g3e_ownerfno = 3500
      WHERE gc_cbl.id           = ‘407329’
	  AND gc_cbl.total_size  = 8
	  AND gc_cbl.composition = 'FIBER' )
);

This approach fails because the geometries may not be merged in the correct order, and for these cables the following error is generated when publishing data:

Started publish at 28/06/2017 14:11:02
Successful Connection GTFIBER

Full Publish VGC_FCBL_L
Querying component view at 28/06/2017 14:11:07
Populating DDC layer at 28/06/2017 14:11:13
6 number of rows in VGC_FCBL_L
Successfully published VGC_FCBL_L in C:\Mapfiles\FOWProd\Data\FiberCable.ddc at 28/06/2017 14:11:13
VGC_FCBL_L has 3 geometry errors. These follow:
1) Invalid geometry for component view VGC_FCBL_L, FID 64169619, CID 1, and LTT_ID 0 - No geometry was produced, probably because of a mismatch of G3E_COMPONENT.G3E_GEOMETRYTYPE and the actual geometry, or because of an un-supported SDO_GType.
2) Invalid geometry for component view VGC_FCBL_L, FID 64169620, CID 1, and LTT_ID 0 - No geometry was produced, probably because of a mismatch of G3E_COMPONENT.G3E_GEOMETRYTYPE and the actual geometry, or because of an un-supported SDO_GType.
3) Invalid geometry for component view VGC_FCBL_L, FID 64169622, CID 1, and LTT_ID 0 - No geometry was produced, probably because of a mismatch of G3E_COMPONENT.G3E_GEOMETRYTYPE and the actual geometry, or because of an un-supported SDO_GType.

The actual data in Oracle looks like this :

Oracle data

Oracle data

The 3006-types fail when publishing, the 3002-types are OK. For this migration to work, a geometry-sorting algorithm is needed and that’s why I created the ‘SDE_MERGE’-function.

The SDE_MERGE-code has been executed on actual production data, and from a total of 1874 Direct Buried cables, 1660 could be created. The failures were caused by missing gaps in segments and data needs to be corrected.

hope this helps, Stephan

This entry was posted in G/Technology, Oracle, Oracle Spatial, PL/SQL and tagged , , , , , . Bookmark the permalink.

5 Responses to Sorting and merging geometries in Oracle Spatial

  1. JUM says:

    Had to solve a similar problem, used CTE…

    Started at arbitrary edge. Each step looked for possible edges to merge with operator SDO_TOUCH (via 2D-spatial index). These candidates where connected to the actual result with SDO_GEOM.SDO_UNION and then followed the next recursion.
    Validatet each resulting geometry with the help of SDO_GEOM.SDO_LENGTH (connected length = last length + length of actual edge) and for SDO_GTYPE =3002 (discarded 3006).
    This pure SQL solution is fast and gives repeatable results since ORACLE 12.1.

    Thanks for sharing your alternative, will compare the performance and the results.

  2. JUM says:

    Here the results of my comparision.
    The task: 16.746 single line strings (SDO_GTYPE=3002) possibly to connect to 57 line strings (SDO_GTYPE=3002 too)
    - CTE found 46 results in 20.6 seconds
    - MERGE aggregate function found the same 46 results in 20.8 seconds
    - changing the ODCIAggregateIterate function to SDO_GEOM.SDO_UNION gave the result already in 10.7 (!) seconds
    The resulting geometries where EQUAL in all three tests.

    Thanks for sharing this the impressive solution!

  3. MOHAN GOKAVARAPU says:

    Is this work with out oracle spatial (means using locator)

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>