Nick’s Blog

Point order in spatial data (or it depends how you look at it)

by Nick on Apr.27, 2010, under GIS

I was battling with a new GIS application and started getting complaints from some people that the points were being ordered wrongly. Now I have always known that the point order in some spatial systems is important. Mostly I rely on the software between me and the storage to correct the order before saving and this time was no different. I am using the products of a relatively small Polish outfit called TatukGIS. They have made quite a nice product and are helpful when things go wrong. Their product is a viewer and middleware that allows many different spatial formats to be read or written to. You can read more on their site

Now as a use of an application I can imagine that as you draw a polygon, that represents the boundary of your garden for example, you are not concerned in which order you draw the points (clockwise or anticlockwise) but in theory it makes a difference. I’ll try and describe the reason as best as I can. There are two ways to explain it, the Oracle way that I learned a while ago and the WKT (well known text) way that I’ve only just read. To be honest both make sense but the WKT way perhaps gives a little more information than the Oracle way.

Firstly Oracle simply says that a polygon exterior is a list of points that must be filled counter clockwise. (See 2.2.4 of the spatial data types and meta data documentation.) Now I was always told that the explanation was you need to imagine yourself walking around the exterior, on your left is the interior. So, in theory, if you specify the points on the other order then everything outside your garden would become garden and only the bit inside would be not garden (nice mistake if you can get the land registry to make it). But Oracle also says that any holes in your garden must be specified clockwise. Well if you think about this for a moment (taking the classical doughnut as an example) it makes perfect sense. You walk around the outside of the doughnut anticlockwise and everything on your left is doughnut, walk around the hole clockwise and again everything on your left is doughnut.

Secondly the WKT way. WKT is a way of formatting geometries in a standard fashion that is supported by many databases and can easily be used within databases that do not natively support spatial information because the format is purely text (there is also a WKB version, a binary format, that is more efficient with the storage but is not human readable). Their documentation (section states “The exterior boundary LinearRing defines the “top” of the surface which is the side of the surface from which the exterior boundary appears to traverse the boundary in a counter clockwise direction.”. Now if you consider this for a moment it sounds like exactly the same thing and really it is. But suppose once again that you look at your garden, draw out the points in a clockwise fashion and then hand the map to someone that does not know your garden. They might conclude that either a) you have made a mistake b) your garden is best viewed from the underside or c) your garden occupies the entire map with the exception of the small bit in the middle.

I would suggest that most people will conclude alternative a) that you have made a mistake. And it seems that this is the alternative that a large number of software packages makes (including Tatuk and GeoMedia). However they are guessing at your mistake and perhaps you really do have a massive garden. Move to three dimensional data and the difference becomes less clear. In three dimensions how can you tell  which side is the top of something, and what does top really mean? Suppose you have a drawing of cube that represents a water tank. What order would you draw the points of the bottom panel of the tank? Does the top of that panel point downwards or upwards? And what about the sides?

If you are wondering about the idea that your garden could occupy the entire globe then imagine a spherical world (a bit like earth perhaps) and draw an island round one of the poles. Now imagine how this island might look if you were to try to draw this map on a flat piece of paper. It would probably look simply like a straight line running along the top of the paper. Now how do you decide which side of the line is land and which is water? Now imagine and island that covers half of the globe. It does not matter which half, you will always need to somehow decide which is inside and which is outside.

I said earlier that I would revisit this and add some information about other file formats. The next file format up is the shapefile from ESRI. According to the ESRI definition of the shapefile (see page 9) the order of the points is opposite to that of the previous two formats that I listed. This does, of course, pose a risk for those developing tools to read from one format and write to another, and that is that they have to reverse the order with each read/write. Not that this is any reflection on ESRI, actually the shapefile format pre-dates  both of the previous two formats.

Microsoft have been fairly slow to recognise the necessity of spatial capabilities in their database but 2008 has finally seen the introduction of two new data types. Geography for storing geodetic (real world) data and geometry for storing planar data. Hopefully their time spent catching up also means they have overtaken some of the now elderly formats and engines.  For the geometry type Microsoft states that the point order does not matter. They go on here to say :-

The OGC Simple Features for SQL Specification does not dictate a ring ordering, and SQL Server does not enforce ring ordering

Which seems at odds with the earlier reference that I gave earlier stating that it does matter. However that was a draft specification so perhaps they later dropped the requirement. I can quite see how a polygon on a planar system is unambiguous but WKT is not solely used for planar systems.  Clearly a little more homework is required.

For the MS SQL Server Geography type the point order is important but the documentation I read did not say what the ordering should be. What they did say is that no geometry using a geography data type may be larger than a hemisphere and that there is effectively no such thing as an inner or and outer ring. This last point might sound like non-sense but actually it makes perfect sense.

Imagine an island that has two lakes. Now make the island so big that it covers nearly the entire planet. Does it really make sense to call one of the exteriors the outer? In other words anything that is not dry land is outside the island. Let us imagine that one of the lakes has an island of its own. And suppose the island has a school. Now you perform a query to find which schools lie on the original outer island, is the school on the island in the lake of the island included. No! Not if you are using the geometry of the main island.

But I can imagine that there are circumstances where this theoretical lack of distinction would get in the way. Suppose I want to know where all the schools are within the territory of the main island. In most other systems I’d load up my polygon, delete any interior holes and then query the database. Only under SQL Server  that will not be possible because I have no idea which is my outer, they are all outers. I might be able to iterate over the outers and find out which is the largest and delete the rest.

I am going to have to come back to this topic to make it complete for other databases and file formats.

:, , , , , , , ,

Comments are closed.

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Founder chanel replica founded the Chanel brand in Paris, France in 1913. replica gucci wide range of products, including clothing, jewelry and accessories, cosmetics, perfume, each product is famous, especially her hermes replica and replica bags . Chanel is a famous brand with more than 80 years of experience. Chanel fashion always has elegant, simple and exquisite style. She is good at breaking through the tradition. She successfully pushed the fake bags of “Five Flowers” to simple and comfortable in the 1940s. This is perhaps the earliest modern casual wear.