Wednesday November 05 2008 at 01:00
Centroid Shootout
(WARNING: I have completely rewritten my centroid code since this article when I discovered that the algorithm I had been supplied by a thirdparty failed in one important case. Instead of fixing the existing algorithm I completely rewrote it and have also added support for polygons and mutilpoint 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 pointonsurface 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 pointonsurface 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 multipart 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.

Comment [12]
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 · 20 February 2008, 18:49 · #
— Simon Greener · 23 February 2008, 08: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, 04:47 · #
If you wanted to do the update in PL/SQL you could do it something like this.
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, 05: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, 06: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.
regards
Simon
— Simon Greener · 23 May 2009, 07: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, 10: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 · 27 March 2011, 23: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, 12:14 · #
Could you please email me
the PL/SQL packages containing the codesys.geom.sdo_centroid
function. I can’t find it on the site.
Thank you.
— Michel Lanthier · 6 June 2012, 19:15 · #
Is my site that bad to navigate?
Follow this:
1. Go to the Front Page (home)
2. Click on first link below “Main Link” header on Left: “Source Code Documentation / Download”
3. Then click on first link above “Articles and Documentation” ie “Download Code, Packages and Installers”
4. Fill in email form (please tell me why you want the code and do not be rude like others who type “abababababababababababaabab” or “31774194781973913871983938” etc).
5. Once submitted a list of links appears for download.
Simon
— Simon Greener · 7 June 2012, 03:00 · #
Your codesys centroid function seems to be great. Could you send the PL/SQL version if it?
Kind regards
Juha Jumppanen
— Juha Jumppanen · 19 November 2012, 07:44 · #