Go to content Go to navigation and search

Home

Current Oracle Spatial Blog Articles


Search

Browse

RSS / Atom

Email me

textpattern

Creative Commons License
All Blog Articles, Data Models and Free Source Code by Simon Greener, The SpatialDB Advisor is licensed under a Creative Commons Attribution-ShareAlike 3.0 Unported License.

Oracle Spatial Centroid Shootout

Wednesday November 05 2008 at 12:00

Centroid Shootout

(WARNING: I have completely re-written my centroid code since this article when I discovered that the algorithm I had been supplied by a third-party failed in one important case. Instead of fixing the existing algorithm I completely re-wrote it and have also added support for polygons and mutil-point geometries. I will edit all centroid related articles some time soon.)

I get a lot of requests for help with the centroid function in my PL/SQL packages. It seems to be a universal need people have that is not met by Oracle Locator/Spatial. So I thought I would write a little article on the different centroid functions that are available in Oracle and compare them in a final image!

For all my tests I will use a “half moon” polygon in order to show the differences in the algorithms. An image of the polygon is included at the end of this article.

1. MdSys.Sdo_Geom.Sdo_Centroid

This is a standard mathematical weighted centroid that is part of Oracle. It has been subject to license restrictions in the past and is still subject to license restrictions for Locator users at 11g (see Appendix B: Oracle Locator). Regardless, let’s see how to use it and how good is its result.

gis@XE> SELECT mdsys.sdo_geom.sdo_centroid(poly,0.05)
  2    FROM (select
  3          mdsys.sdo_geometry(2003,null,null,
  4          sdo_elem_info_array(1,1003,1),
  5          sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6  ) as poly from dual)
  7  /
MDSYS.SDO_GEOM.SDO_CENTROID(POLY,0.05)(SDO_GTYPE, SDO_SRID, SDO_POINT(X, Y, Z), SDO_ELEM_INFO, SDO_ORDINATES)
-------------------------------------------------------------------------------------------------------------
SDO_GEOMETRY(2001, NULL, SDO_POINT_TYPE(532.434696, 184.742483, NULL), NULL, NULL)

You can refer to the image at the end of this article to see where this point lies in relation to our polygon. But a quick check with sdo_geom.relate() will tell us the most critical information:

gis@XE> SELECT mdsys.sdo_geom.relate(poly,'mask=DETERMINE',
  2                mdsys.sdo_geom.sdo_centroid(poly,0.05),0.05)
  3    FROM (select
  4          mdsys.sdo_geometry(2003,null,null,
  5          sdo_elem_info_array(1,1003,1),
  6          sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  7  ) as poly from dual)
  8  /
MDSYS.SDO_GEOM.RELATE(POLY,'MASK=DETERMINE',MDSYS.SDO_GEOM.SDO_CENTROID(POLY,0.05),0.05)
----------------------------------------------------------------------------------------
DISJOINT

Not good.

2. MdSys.ST_Polygon.ST_Centroid()

Oracle’s little known SQL/MM compliant type library includes a ST_Centroid() as per the standard. There is no mention in the Oracle licensing that this is a restricted function for the SQL/MM type library.

gis@XE> SELECT mdsys.st_polygon(poly).ST_Centroid()
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6  ) as poly from dual)
  7  /
MDSYS.ST_POLYGON(POLY).ST_CENTROID()(GEOM(SDO_GTYPE, SDO_SRID, SDO_POINT(X, Y, Z), SDO_ELEM_INFO, SDO_ORDINATES))
-----------------------------------------------------------------------------------------------------------------
ST_POINT(SDO_GEOMETRY(2001, NULL, SDO_POINT_TYPE(532.434696, 184.742483, NULL), NULL, NULL))

Where is this in relation to the polygon?

gis@XE> list
  1  SELECT mdsys.st_polygon(poly).ST_Disjoint(mdsys.st_polygon(poly).ST_Centroid())
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6* ) as poly from dual)
gis@XE> /
MDSYS.ST_POLYGON(POLY).ST_DISJOINT(MDSYS.ST_POLYGON(POLY).ST_CENTROID())
------------------------------------------------------------------------
                                                                       1

Again, a similar result (the centroid is not inside the polygon), as it is the same algorithm.

3. MdSys.Sdo_Geom.Sdo_PointOnSurface()

The sdo_geom package has a license restricted point-on-surface function.

gis@XE> SELECT  mdsys.sdo_geom.SDO_PointOnSurface(poly,0.05)
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6* ) as poly from dual)
gis@XE> /
MDSYS.SDO_GEOM.SDO_POINTONSURFACE(POLY,0.05)(SDO_GTYPE, SDO_SRID, SDO_POINT(X, Y, Z), SDO_ELEM_INFO, SDO_ORDINATES)
-------------------------------------------------------------------------------------------------------------------
SDO_GEOMETRY(2001, NULL, SDO_POINT_TYPE(69, 9.5, NULL), NULL, NULL)

Checking we get:

gis@XE> SELECT mdsys.sdo_geom.relate(poly,'mask=DETERMINE',
  2            mdsys.sdo_geom.sdo_PointOnSurface(poly,0.05),0.05)
  3    FROM (select
  4          mdsys.sdo_geometry(2003,null,null,
  5          sdo_elem_info_array(1,1003,1),
  6          sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  7  ) as poly from dual)
  8  /
MDSYS.SDO_GEOM.RELATE(POLY,'MASK=DETERMINE',MDSYS.SDO_GEOM.SDO_POINTONSURFACE(POLY,0.05),0.05)
----------------------------------------------------------------------------------------------
TOUCH

That is, the generated centroid falls on the polygon’s boundary but not inside.

4. MdSys.ST_Polygon.ST_PointOnSurface()

Similarly, the SQL/MM ST_Polygon has a point-on-surface function that, funnily, is not license restricted!

gis@XE> SELECT mdsys.ST_Polygon(poly).ST_PointOnSurface()
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6* ) as poly from dual)
gis@XE> /
MDSYS.ST_POLYGON(POLY).ST_POINTONSURFACE()(GEOM(SDO_GTYPE, SDO_SRID, SDO_POINT(X, Y, Z), SDO_ELEM_INFO, SDO_ORDINATES))
------------------------------------------------------------------------------------------------------------------------
ST_POINT(SDO_GEOMETRY(2001, NULL, SDO_POINT_TYPE(183.006, 134.492, NULL), NULL, NULL))

This is an interesting result as the generated centroid is not the same as the one generated by SDO_GEOM.SDO_POINTONSURFACE(). How does this centroid fair in relation to the actual polygon?

gis@XE> SELECT mdsys.st_polygon(poly).ST_Contains(mdsys.ST_Polygon(poly).ST_PointOnSurface())
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6* ) as poly from dual)
gis@XE> /
MDSYS.ST_POLYGON(POLY).ST_CONTAINS(MDSYS.ST_POLYGON(POLY).ST_POINTONSURFACE())
------------------------------------------------------------------------------
                                                                             1

Finally, we have a centroid inside the polygon. (See image at the end of this article for just where this centroid lies in relation to the polygon.)

5. Codesys.Geom.Sdo_Centroid()

Finally, there is my own (see note below on ownership) humble offering.

gis@XE> SELECT codesys.geom.sdo_centroid(poly,0.05)
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6* ) as poly from dual)
gis@XE> /
CODESYS.GEOM.SDO_CENTROID(POLY,0.05)(SDO_GTYPE, SDO_SRID, SDO_POINT(X, Y, Z), SDO_ELEM_INFO, SDO_ORDINATES)
-----------------------------------------------------------------------------------------------------------
SDO_GEOMETRY(2001, NULL, SDO_POINT_TYPE(494.5, 242.1, NULL), NULL, NULL)

Checking its location reveals it falls within the polygon and is well placed (see image at end of article).

gis@XE> SELECT mdsys.sdo_geom.relate(poly,'mask=DETERMINE',
  1            codesys.geom.sdo_centroid(poly,0.05),0.05)
  2    FROM (select
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)
  6* ) as poly from dual)
gis@XE> /
MDSYS.SDO_GEOM.RELATE(POLY,'MASK=DETERMINE',CODESYS.GEOM.SDO_CENTROID(POLY,0.05),0.05)
---------------------------------------------------------------------------------------
CONTAINS

Excellent. But is that all the story? See the image at the end of this article to see where it is actually located.

6. Rough as Guts SQL Average

One can average the X and Y ordinates of a geometry by extracting them in a table function. Yes, one can use sdo_util.GetVertices() but I will use a function in my own packages that I wrote a few years ago.

gis@XE> SELECT avg(p.x) as x,avg(p.y) as y
  2  FROM table(codesys.geom.getpointset(
  3  mdsys.sdo_geometry(2003,null,null,
  4  sdo_elem_info_array(1,1003,1),
  5  sdo_ordinate_array( 69,9.5,206,86.5,3
  6* ))) p
gis@XE> /
          X           Y
----------- -----------
    466.000     141.250

Where is it located?

gis@XE> SELECT mdsys.sdo_geom.relate(
  2  mdsys.sdo_geometry(2003,null,null,
  3  sdo_elem_info_array(1,1003,1),
  4  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5)),
  5  'mask=DETERMINE',
  6  mdsys.sdo_geometry(2001,null,sdo_point_type(avg(p.x),avg(p.y),NULL),NULL,NULL),0.05)
  7  FROM table(codesys.geom.getpointset(
  8  mdsys.sdo_geometry(2003,null,null,
  9  sdo_elem_info_array(1,1003,1),
 10  sdo_ordinate_array( 69,9.5,206,86.5,397,185.5,553,189.5,698,143.5,920,-7.5,853,105.5,704,259.5,537,307.5,403,271.5,183,134.5,69,9.5))
 11* )) p
gis@XE> /
MDSYS.SDO_GEOM.RELATE(MDSYS.SDO_GEOMETRY(2003,NULL,NULL,SDO_ELEM_INFO_ARRAY(1,1003,1),SDO_ORDINATE_ARRAY(69,9.5,206,86.5,397,185.5,
-----------------------------------------------------------------------------------------------------------------------------------
DISJOINT

Outside the polygon.

Summary

In summary, the best algorithm is the one encapsulated within my geom.sdo_centroid function. It guarantees that the generated centroid falls within the polygon but is “well conditioned” with respect to that location. Also, the algorithm used will not place the centroid inside a hole (inner shell) inside a polygon; also, it will choose the largest of any parts (multiple outer shells) into which it will place the centroid. The original algorithm was not created by myself (though I have modified it for cases the original author missed; I added the code to select the largest part in a multi-part polygon) but I have permission to make it public and have done so for the past 6 years.. The origial coding was in Java: I only converted it to PL/SQL. If anyone wants a Java version contact me via email and I will supply it.

Image

The following image shows the relative locations of each of the centroids generated by the processing above.

Centroid Shoot Out

Creative Commons License

post this at del.icio.uspost this at Diggpost this at Technoratipost this at Redditpost this at Farkpost this at Yahoo! my webpost this at Windows Livepost this at Google Bookmarkspost this to Twitter

Comment [9]

Hi Simon,
Thanks for the comparison of centroid algorithms. This is a problem that has been vexing me for a while. I was wondering if I could take a look at the java version of odesys.Geom.Sdo_Centroid(). I’m really keen to understand how you “condition” the centroid, and whether that works on more anomalous geometries, including those with holes, etc.
Thanks,
Andy

— Andy Martin · 21 February 2008, 05:49 · #

I will prepare an article on the Java code and post it soon. regards Simon

— Simon Greener · 23 February 2008, 19:09 · #

hi simon,
i am still new to the oracle environment. I have a question, how can i update the point. Let’s say i enter the coordinate in the database already, and i want to change it. what command should i use?

— lionel · 23 May 2009, 15:47 · #

Lionel, Let's assume your data is 2D oe 3D point data held in the SDO_POINT_TYPE structure of the SDO_GEOMETRY object. If this is the case you can add 100 to the X coordinate of the point as follows (assume Your Table is LIONEL_POINT, the sdo_geometry column is called GEOM and the row identified by a feature identifier FID of 1234): 
UPDATE LIONEL_POINT a
   SET a.GEOM = MDSYS.SDO_GEOMETRY(a.GEOM.SDO_GTYPE,
                                   a.GEOM.SDO_SRID,
                                   MDSYS.SDO_POINT_TYPE(a.GEOM.SDO_POINT.x + 100,
                                                        a.GEOM.SDO_POINT.y,
                                                        a.GEOM.SDO_POINT.z),
                                   a.GEOM.SDO_ELEM_INFO,
                                   a.GEOM.SDO_ORDINATES)
 WHERE FID = 1234;
If you wanted to do the update in PL/SQL you could do it something like this. 
DECLARE
  v_geom  mdsys.sdo_geometry;
BEGIN
  SELECT GEOM
    INTO v_geom
    FROM LIONEL_POINT
   WHERE FID = 1234;
  v_geom.sdo_point.x := v_geom.sdo_point.x + 100;
  UPDATE LIONEL_POINT A
     SET a.geom = v_geom
   WHERE FID = 1234;
  COMMIT;
END;
If you point data is held in the SDO_ORDINATE_ARRAY then I would suggest you look at my SDO_SetPoint() function as described in this article.

I hope this is helpful to you.

regards
Simon

— Simon Greener · 23 May 2009, 16:29 · #

SDO_GEOMETRY(3003, NULL, NULL, SDO_ELEM_INFO_ARRAY(1, 1003, 1), SDO_ORDINATE_ARR
AY(-9585.1664, -2656.3799, -6, -9567.2255, -2645.8675, 0, -9635.9063, -2528.6542
, 0, -9755.0511, -2598.4668, 0, -9686.3703, -2715.6801, 0, -9640.2214, -2688.639
3, 0, -9559.9876, -2825.5694, 0, -9504.9326, -2793.3101, 0, -9585.1664, -2656.37

this is my data.lets take one point as an example “-9755.0511, -2598.4668, 0”. I want to change the z coordinate from 0 to -3. how can i did that sir?and where can i find thet FID?sorry to border you,but i really new to oracle and this is quite urgent for me.thanks for your help.

— lionel · 23 May 2009, 17:18 · #

Lionel,

The only way I can do this is via the use of my SDO_VertexUpdate function I have blogged about and which is available as a part of my free PL/SQL packages that are downloadable from this site.

Here is your geometry modified as you desire.

select Geom.SDO_VertexUpdate(
                SDO_GEOMETRY(3003, NULL, NULL, 
                             SDO_ELEM_INFO_ARRAY(1, 1003, 1), 
                             SDO_ORDINATE_ARRAY(-9585.1664, -2656.3799, -6, -9567.2255, -2645.8675, 0, -9635.9063, -2528.6542, 0, -9755.0511, -2598.4668, 0, -9686.3703, -2715.6801, 0, -9640.2214, -2688.6393, 0, -9559.9876, -2825.5694, 0, -9504.9326, -2793.3101, 0, -9585.1664, -2656.3799, 0)),
                 mdsys.vertex_type(-9755.0511, -2598.4668, 0, null,1),
                 mdsys.vertex_type(-9755.0511, -2598.4668, -3, null, 1)) as UpdateGeom
 from dual;
====
UPDATEGEOM
----------
MDSYS.SDO_GEOMETRY(3003,null,null,MDSYS.SDO_ELEM_INFO_ARRAY(1,1003,1),MDSYS.SDO_ORDINATE_ARRAY(-9585.1664,-2656.3799,-6,-9567.2255,-2645.8675,0,-9635.9063,-2528.6542,0,-9755.0511,-2598.4668,-3,-9686.3703,-2715.6801,0,-9640.2214,-2688.6393,0,-9559.9876,-2825.5694,0,-9504.9326,-2793.3101,0,-9585.1664,-2656.3799,0))

regards
Simon

— Simon Greener · 23 May 2009, 18:02 · #

Could you please email me
the PL/SQL packages containing the codesys.geom.sdo_centroid
function. I can’t find it on the site.

— Richard Terbraak · 8 October 2010, 21:37 · #

Hi Simon,
I need to get the CENTROID of a linestring.

I tried it, but I did not work fine.

INSERT INTO ERI_CENTROID (OBJECTID, SHAPE) VALUES (1, SDO_GEOM.sdo_centroid( sdo_geom.sdo_buffer(MDSYS.SDO_GEOMETRY (2002, 8292, NULL, SDO_ELEM_INFO_ARRAY 1,2,1), ord_array), v_diminfo, 10), v_diminfo));

Imagine a road, with several segments, I need the middle of the road (linestring).

Must I to convert to LRS system ?

Best Regards
Eriovaldo

— Eriovaldo · 28 March 2011, 10:23 · #

Could you please email me
the PL/SQL packages containing the codesys.geom.sdo_centroid
function. I can’t find it on the site.

— Johan Keurentjes · 1 August 2011, 23:14 · #