How do I differentiate the paths of a polygon between an "outer" boundary and an "inner" boundary?

[Richard Quadling]

Hello.

When adding a "doughnut" polygon to Google Maps (See http://gmaps-samples-v3.googlecode.com/svn/trunk/poly/pentagon.html as an example), the "outer" boundary is plotted in a clockwise direction. The "inner" boundary has to be plotted anti-clockwise.

That makes sense once you see it.

The problem that exists though is there is no way to determine if a boundary is an inner or an outer boundary.

This becomes an issue when you want to use the paths in WKT queries (I'm using MS SQL Server 2008 R2 which has geography data types, allowing easy querying of this sort of data).

If you look at the sort of things WKT allows (http://en.wikipedia.org/wiki/Well-known_text#Geometric_objects), then the syntax for the polygons is along these lines ...

POLYGON((outer_boundary) [, (inner_boundary) ] )

The polygon requires an outer boundary and an optional inner boundary. The ordering of the points in the boundary is not important.

For a multiple polygon construct (say multiple islands), then the syntax is ...

MULTIPOLYGON(((outer_boundary_1) [, (inner_boundary_1) ] ) [, ((outer_boundary_2) [, (inner_boundary_2) ] ) [, ... ] ] )

This is essentially multiple polygons, so each "island" can be a "doughnut".

I currently take each path, encoded it and pass that to a server-side script (nice and small amount of data which is decoded using a PHP script, based upon the logic described in http://code.google.com/apis/maps/documentation/utilities/polylinealgorithm.html).

It was when I decided to plot Outer London and exclude Inner London that I found that there is no differentiation of the paths.

Given that, there seems to be no way to determine if the result of google.maps.Polygon.getPaths() contains islands, doughnuts or both. There is no connection between the different paths, so it would have to be assumed that each path was a separate polygon. Obviously, this wouldn't work for the paths defined in the Pentagon example.

I have many different ideas on a solution, but I am unable to test any of them due to the closed source nature of the project.

In comparison to this, Google Earth already has this logic within it (See http://code.google.com/apis/kml/documentation/kml_tut.html#polygons as an example of a polygon with 2 distinct boundaries, correctly identified as inner and outer).

So, it seems that this may be a simple (ha - I'm not writing the Google Maps API) oversight.

If there is some determination within Google Maps API that identifies inner / outer for its own use, then if this could be exposed through a suitable mechansism and ideally supported by the encoding library, then that would be a step in the right direction. But I still don't think that would be enough. Without the ability to tag an inner boundary to an outer boundary, the paths still don't quite match the full requirement.

If there was a way of creating polygons for Google Maps with the proper inner/outer boundaries (inner being optional), then that would be perfect.

Having said all of that, I've no idea if you can have an outer boundary and multiple inner boundaries - a swiss cheese effect (lots of holes).

I hope this is the right place to ask this. If not, can you let me know where I should go.

Thank you.

Richard Quadling.

[Ben Appleton]

It sounds like you have a polygon containment forest: a collection of rooted trees whose roots are outer polygons, children are polygonal holes, grand-children are polygonal islands inside holes, etc. You can certainly represent containment in JavaScript, but it's not necessary for rendering. Therefore the Google Maps API does not represent containment.

There is an unfortunate caveat. Many browsers use Canvas to render vector graphics, and Canvas requires that outer vs inner polygons have opposite orientations - it implements only "zero-winding fill". For example, if your outer boundary is clockwise, your holes must be counter-clockwise, islands within holes must be clockwise, and so on. If you need to determine the orientation of a polygon you can use the geometry library's computeSignedArea method
(http://code.google.com/apis/maps/documentation/javascript/reference.html#spherical). You can then traverse your containment tree to ensure that outer vs inner polygons have opposite sign, reversing polygonal loops to negate their sign where necessary.

Incidentally the geometry library also has a method to encode polylines/polygons in the same format as you reference, but compiled so it loads faster.

So I suggest: use google.maps.Polygon to visualize your polygons, but wrap it in another class or datastructure to represent your containment forest. To visualize simply add the google.maps.Polygon to the map. When constructing queries to your server, consult your wrapper class / datastructure to determine which polygonal loops are outside vs inside. Optionally, also switch to using the compiled poly encoder in the geometry library.

Hope that helps
Ben

On May 12, 2011 9:54 PM, "Richard Quadling" <rqua...@gmail.com> wrote:

[Richard Quadling]

> --
> You received this message because you are subscribed to the Google Groups
> "Google Maps JavaScript API v3" group.
> To post to this group, send email to google-map...@googlegroups.com.
> To unsubscribe from this group, send email to
> google-maps-js-a...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/google-maps-js-api-v3?hl=en.
>

Thanks for that.

encodePath only allows for a single path, not a set of paths. I'm
simply concatenating them with | (pipe). And splitting and decoding
them in PHP. How do I access the compiled encoder. I'm currently
using google.maps.geometry.encoding.encodePath()

Very useful. -ve values from computeSignedArea() relate to the outer
polygons and +ve values to the inner ones.

I think the final piece for me now is to determine from 2 polygons if
one is completely within the other.

--
Richard Quadling
Twitter : EE : Zend
@RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY

[Ben Appleton]

Oh great, you're already using it. I thought you meant you were using an older JavaScript poly encoder that had not been compiled.

> Very useful. -ve values from computeSignedArea() relate to the outer
> polygons and +ve values to the inner ones.

That's right.

> I think the final piece for me now is to determine from 2 polygons if
> one is completely within the other.

I thought you already had this structure. Else, how are you currently generating KML and WKT queries as you mention?

Cheers
Ben

>
>
> --
> Richard Quadling
> Twitter : EE : Zend
> @RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY
>

[Richard Quadling]

>> Thanks for that.
>>
>> encodePath only allows for a single path, not a set of paths. I'm
>> simply concatenating them with | (pipe). And splitting and decoding
>> them in PHP.  How do I access the compiled encoder. I'm currently
>> using google.maps.geometry.encoding.encodePath()
>
> Oh great, you're already using it. I thought you meant you were using an
> older JavaScript poly encoder that had not been compiled.
>
>> Very useful. -ve values from computeSignedArea() relate to the outer
>> polygons and +ve values to the inner ones.
>
> That's right.
>
>> I think the final piece for me now is to determine from 2 polygons if
>> one is completely within the other.
>
> I thought you already had this structure. Else, how are you currently
> generating KML and WKT queries as you mention?
>
> Cheers
> Ben
>

I'm still in building/designing/learning/playing phase of the
development. Essentially proving to myself and the team that what we
want to do is possible. I'm working things out manually.

In the last test (test 5) I create a map, added a simple polygon and
send the encoded path to PHP to decode and turn into WTK for SQL to
get the pins to pass back to the map for displaying.

For a single polygon (I've used 2 sliders to allow different number of
points and radius) this is working fine. I have to use a polygon as
whilst I'm only playing with regular ones, the final view of the app
will be to have complex boundaries.

The next test was to add the exclusion polygon. That's where I'm at
now. Though I'm still playing I know that the users will need to be
able to define these complex areas.

The purpose of the tool is to allow our call centre staff to display
the location of a LGV (Large Goods Vehicle) breakdown and, based upon
the contract (essentially who owns or is hiring the vehicle) provide a
ranking of the most appropriate maintenance engineers, nearest to the
breakdown. We have nearly 1,000 service depots in the UK. Each depot
covers an area. Sometimes just as a 30 mile radius, others cover a
specific county, or part of it. Others don't go inside a circular
motorway/ring road, etc. All different. Some will travel over
bridges/ferries/etc. Or have any sort of boundary/exclusion.

The next step in the design is to allow a backoffice user the ability
to plot out these boundaries. The boundaries will be stored in our SQL
Server in 2 ways:

1 - Using the Google Maps encoded form, so when I need to display the
polygon, I can just supply that to the client app, call the decoder
and add each path to the polygon.
2 - As a SQL Server Geography type, so I can use SQL Server to do all
the intersection and find a list of service providers who cover the
point of the breakdown and are attributable to the contract for the
vehicle.

Obviously, there is more to the front end than just the map, but the
map is one of the key players. The map will also show any service
provider that has part of their boundary within the viewport, so, if
the preferred providers are unable to handle the breakdown (some
providers are quite small and only have 2 or 3 maintenance staff), the
user can see that there are other providers in the area who are linked
to the contract and may be able to help, even though it is outside of
their boundary. It's all very fluid, but not a total free for all.
Travelling time for the maintenance people means some driver is
sitting in their cab waiting and having the stock not being delivered.
The vast majority of the contracts are delivering perishables and
delivery times are quite tight.

And I then, on top of all of this, ...

GoogleMaps ...

LatLng(latitude, longiture)
Polygon orientation of points to create a small closed area : clockwise

WTK (as used by SQL Server)
POINT(Longitude, Latitude) <<< Reverse
POLYGON orientation of points to create a small closed area :
anticlockwise. Otherwise the enclosed area encompasses the whole of
the earth, except the small part "outside" the boundary.

And to this, the MS SQL native Geography::Point() method uses
Point(latitude, longitude), the reverse of WTK but matches Google Maps
API.

Don't you just love standards!

[Ben Appleton]

OK - so for this first step, you only need to display a complex polygon (such as a polygon with multiple inner and outer boundaries). That should work fine, so long as exterior vs interior loops wind in opposite directions.

 

The next step in the design is to allow a backoffice user the ability
to plot out these boundaries. The boundaries will be stored in our SQL
Server in 2 ways:

1 - Using the Google Maps encoded form, so when I need to display the
polygon, I can just supply that to the client app, call the decoder
and add each path to the polygon.

So long as your exterior and interior loops wind in opposite directions, I believe you can store a google.maps.Polygon as a pipe-separated sequence of encoded LatLng strings.

2 - As a SQL Server Geography type, so I can use SQL Server to do all
the intersection and find a list of service providers who cover the
point of the breakdown and are attributable to the contract for the
vehicle.

For both of these cases you need to distinguish exterior vs interior loops. In addition, if I understand correctly, for the SQL Server Geography type you need to represent the polygon containment forest I mentioned earlier - that is, which polygonal loops contain which other polygonal loops. So when a backoffice user plots out a boundary, either the UI itself or a post-processing step must construct the polygon containment forest.

The UI could enforce this, by providing a flow where a backoffice user adds a "child loop" to an existing loop - to punch a hole in an exterior loop, for example. Or you could compute this after the fact by testing which loops lie inside which other loops. For non-intersecting loops, loop A contains loop B if and only if the first vertex of loop B lies inside loop A. So long as there are only a handful of loops per polygon this should be fast enough, otherwise you could use a faster (but more complex) scan-line algorithm.

Haha, I'm sorry for you. Lat/lng versus lng/lat seems to be a perennial source of pain in GIS systems.

Cheers

Ben

 

--

Richard Quadling
Twitter : EE : Zend
@RQuadling : e-e.com/M_248814.html : bit.ly/9O8vFY

[Richard Quadling]

Your explanation is excellent. Thank you very much.

Do you know of any tools that provide a user with polygon drawing?
Something I don't want to have to start from scratch?

A library of useful apps that have been generated using the maps API
would be excellent.

[Ben Appleton]

The documentation examples and the "demo gallery" are worth a look:

http://code.google.com/apis/maps/documentation/javascript/examples/index.html

http://code.google.com/apis/maps/documentation/javascript/demogallery.html

The gallery includes this polygon drawing demo:

http://www.the-di-lab.com/polygon/

It's very simple but might be a good starting point.

Cheers

Ben