Oracle Spatial Centroid Shootout
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.
!/images/13.gif (Centroid Shoot Out)!