Subject: RE: [Geopriv] issues and adoption of draft-thomson-geopriv-geo-shape

From: "Thomson, Martin" <[email-masked]>
Date: Tue, 9 May 2006 18:23:23 -0500

Hi Cullen,

I'm glad that someone is reading and questioning!  This is the first feedback of any detail that I have received.  So, no, the topic has not been discussed to death ;)

I think that I may not have been completely clear about what this draft is trying to solve.  I intend this to be used for personal location/presence - the location of a device, which in this case is likely to be wireless.  Perhaps this was a bad assumption and I need to be more explicit about this in the draft.  What do you think?

Maybe I should also point out, right up front, that one of the joys of uncertainty is that it is an inexact science.  It doesn't have to be completely precise.  In many cases an approximation that is within a 5% margin of error is not going to make that great a difference.  I won't re-run the confidence discussion, but suffice it to say that we are dealing with guesses here.  That might shed a different light on the draft.

On polygons, you raise a good question; the points you include are most definitely not co-planar.  The wriggling is done to make it easier for the users of this information.  One of the major goals of this draft was to make the GML portion of PIDF-LO more accessible.  The up-normal calculation method in the appendix helps with that.

For most applications, providing the distance between any two points is short enough, keeping an identical altitude ensures a pretty good approximation of a co-planar.  A definition of "short enough" is included in the draft; your examples are a fair bit outside of that distance.  Maybe I should be clearer on what happens beyond this distance (geodesic interpolation, or fix altitudes?).

For an arc band - I believe that a planar approximation would be acceptable, given that the distances are "short enough".  Thanks for pointing out my omission on angles - the angle is the one familiar to anyone who has used a compass - Northing (0) to Easting (90).  The picture shows this, but I forgot my 'N' and 'E' markers.

Choice of shapes has been driven by those that are used in existing wireless systems.  In particular, these shapes are produced by 3GPP wireless location services (3GPP TS 23.032).  Interoperability with 3GPP was a major reason that fewer shapes were not included.  Many of these shapes are those that are natively produced by location determination algorithms; where those algorithms produce more complex geometries it is generally accepted that an approximation is used.

I appreciate your point about the spherical interpolation, but I think forcing support of that sort of mathematics would be a prohibitive barrier to implementation.  In reality, inverse flattening makes spherical interpolation infeasible, particularly near the poles.  Geodesic interpolation would be required, which is widely documented as being somewhere between tricky and a right PITA.

So, thanks for the feedback!  You get a gold star for being the first to get into the meat of this.  Has my response helped?  Or did this just pile more confusion on?

Cheers,
Martin

> -----Original Message-----
> From: Cullen Jennings [mailto:[email-masked]]
> Sent: Wednesday, 10 May 2006 3:03 AM
> To: Andrew Newton
> Cc: [email-masked]
> Subject: Re: [Geopriv] issues and adoption of draft-thomson-geopriv-geo-
> shape
> 
> 
> I am going to bring up some issues which I imagine have been
> discussed to death in the WG but are some random thoughts that came
> up when I first read the document. I imagine there are good answers
> to all of them but I did not find them in the draft so help me get up
> to speed on all this stuff. PS - I definitely agree we need a good
> document specifying this type of stuff and I'm all for re-use of GML.
> 
> Let's say I had the polygon specified in WGC 84 lat, Lon,  alt,  and
> the vertex's are
> 
> 120, 45, 0
> 120, 46, 0
> 120, 47, 0
> 115, 46, 0
> 
> Is that a co-planar polygon? The see how the draft says it is not
> then tries to create wiggle room around claiming it is. Pretending
> that a spherical coordinate system is actually a cartesian coordinate
> system is fought with disaster - particularly around the poles.
> 
> What is the shape of the following polygon
> 
> 90,0,0
> -90,0,0
> 0,180,0
> 
> The definition of the arc band used here, when specified in a
> spherical coordinate system results in a shape that is remarkable
> complex to decide if a line intercepts it or not.
> 
> Imagine I am trying to specify the polygon that defines the southern
> hemisphere - the proposed normal algorithm looks like it will have
> some issues. I will be somewhat suspicious off any solution in a
> spherical coordinate system that does not require polygons to be
> specified in CW (or CCW) direction.
> 
> It was unclear to me how the angles for the arc bands where specified.
> 
> It's not clear to me what shapes you need and what operations you
> need on them. Off the top of my head it seams like you need the
> following.
> 
> 0) something that works in all cases
> 
> 1) Specify a point in spherical coordinate system
> 2) Find great circle distance between two points
> 
> 3) Specify a spherical polygon of constant altitude
> - by this I mean great edges are great circle arcs between vertex
> - all vertex have same altitude
> - surface is a subset of a spherical shell
> - correctly specifies and deal with singularities issue and
> degenerate polygons
> (I'm sure there is a better way of saying all this but you get the idea)
> 
> 4) Specify a spherical prism made by the space bounded by a polygon
> at one altitude and an polygon with vertexes with identical lat,lon
> but different altitude.
> 
> 5) decide if point is strictly outside of spherical prism.
> 
> If the Uncertainty stuff is needed, then it seems you would also need
> 
> 6) decide the great circle distance from a point to a spherical prism.
> - I have no idea how hard it is to compute this but I would want to
> know before we decided to do it
> 
> If uncertainly needs to be expressed by something that does not
> locally approximate a circle, well, life is going to get way more
> complex. I can imagine that many of the location approaches would
> give error regions that looked locally like an ellipse or the arc
> band. If we really need this, we need to seriously consider what
> operation we need and the complexity of intersecting the 3d spherical
> version of an arc band or ellipse with a spherical prism. If it is
> possible to leave this out of the first version of the specification,
> well life will be easier.
> 
> I have not seen a need to decide if some line intersects a prism  but
> we should think about if we have a use case for that or not.
> 
> So, forgive me as I still getting up to speed on this. It was not
> clear to me exactly what we needed from a geometry system. That made
> it harder to decide what parts were missing from this draft and what
> parts that are in could be removed.
> 
> Cullen <with my individual contributor hat on>
> 
> 
> 
> On May 9, 2006, at 7:18 AM, Andrew Newton wrote:
> 
> > All,
> >
> > Martin Thomson's document titled "Geodetic Shapes for the
> > Representation of Uncertainty in PIDF-LO" (draft-ietf-geopriv-geo-
> > shape-01.txt) has received positive review and support for adoption
> > as a working group item.
> >
> > As co-chair of the working group, I have two questions for
> > participants who have not voiced their opinion of this document:
> >
> > 1) Are there any unresolved issues with this document?  And if so,
> > is it your opinion that these issues cannot be resolved?
> >
> > 2) Are there any reasons (technical or non-technical) for not
> > adopting this document as a GEOPRIV work item?
> >
> > I would appreciate this feedback no later than 16 May 2006.
> >
> > -andy
> >
> >
> > _______________________________________________
> > Geopriv mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/geopriv
> 
> _______________________________________________
> Geopriv mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/geopriv

------------------------------------------------------------------------------------------------
This message is for the designated recipient only and may
contain privileged, proprietary, or otherwise private information.  
If you have received it in error, please notify the sender
immediately and delete the original.  Any unauthorized use of
this email is prohibited.
------------------------------------------------------------------------------------------------
[mf2]

_______________________________________________
Geopriv mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/geopriv

---

From: Randall Gellens <[email-masked]>
Date: Wed, 10 May 2006 14:45:32 -0700

At 6:23 PM -0500 5/9/06, Martin Thomson wrote:

>  I intend this to be used for personal location/presence - the 
> location of a device, which in this case is likely to be wireless. 
> Perhaps this was a bad assumption and I need to be more explicit 
> about this in the draft.  What do you think?
>
>  Maybe I should also point out, right up front, that one of the joys 
> of uncertainty is that it is an inexact science.  It doesn't have 
> to be completely precise.  In many cases an approximation that is 
> within a 5% margin of error is not going to make that great a 
> difference.  I won't re-run the confidence discussion, but suffice 
> it to say that we are dealing with guesses here.  That might shed a 
> different light on the draft.

It might be good to mention these two things in the draft, just for 
clarity of intent and scope.

---

From: "Thomson, Martin" <[email-masked]>
Date: Thu, 18 May 2006 18:19:19 -0500

It appears that the 16th has passed.  What is the conclusion?

I have a draft here that addresses (I hope) the issues raised by Cullen, and the clarifications below.  The changes are fairly minimal.  Do I submit that as draft-ietf-... or would you like to see another individual contribution first?

Regards,
Martin

> From: Randall Gellens [mailto:[email-masked]]
> Sent: Thursday, 11 May 2006 7:46 AM
> To: Thomson, Martin; Cullen Jennings; Andrew Newton
> Cc: [email-masked]
> Subject: RE: [Geopriv] issues and adoption of draft-thomson-geopriv-geo-
> shape
>

---

From: Andrew Newton <[email-masked]>
Date: Thu, 18 May 2006 20:37:55 -0400

Martin,

The co-chairs and AD need to confer on this first.  In the meantime,  
no harm comes from another revision as an individual submission.

-andy

On May 18, 2006, at 7:19 PM, Thomson, Martin wrote:

> I have a draft here that addresses (I hope) the issues raised by  
> Cullen, and the clarifications below.  The changes are fairly  
> minimal.  Do I submit that as draft-ietf-... or would you like to  
> see another individual contribution first?
>
> Regards,
> Martin
>

---

From: Cullen Jennings <[email-masked]>
Date: Thu, 18 May 2006 18:09:59 +0200

Thanks - this helps a bunch in understanding why the document is the  
way that it is. Few more questions inline ...

On May 10, 2006, at 1:23 AM, Thomson, Martin wrote:

> Hi Cullen,
>
> I'm glad that someone is reading and questioning!  This is the  
> first feedback of any detail that I have received.  So, no, the  
> topic has not been discussed to death ;)
>
> I think that I may not have been completely clear about what this  
> draft is trying to solve.  I intend this to be used for personal  
> location/presence - the location of a device, which in this case is  
> likely to be wireless.  Perhaps this was a bad assumption and I  
> need to be more explicit about this in the draft.  What do you think?

So the shapes that are defined in the draft would be used to specify  
the location of a device is likely to be within some specified shape  
where the shape represents the uncertainty of the device location and  
the device location was determined with some wireless technique? For  
this purpose, lots of the assumptions seem fine. Another usage of  
these shape might be to describe the exact shape of some geopolitical  
region and ask if a given point is inside or outside. This type of  
usage might end up with very large polygons where the assumptions  
might not work as well. Anything that could be done to help people  
understand where it was appropriate to use this and where it might  
not be appropriate. I think people have been thinking about 3G  
wireless locations but would it still make sense for much more  
accurate 802.11 type measurements, or could it work when using wire- 
maps connected to building for location, or perhaps just IP where the  
error polygon might be some irregular region spanning a continent.

In an side conversation with Rohan, he explained that this formed a  
framework then specific usage, like E911 information, might constrain  
things down much more - like specifying coordinate systems and such.  
I might be asking questions here that are actually answered in other  
documents.

> different light on the draft.

I actually really liked a bunch of your discussion of this in the  
draft. It's hard stuff to explain. Yep, I think providing things  
about what level of approximation we are assuming is needed would be  
good.

>
> On polygons, you raise a good question; the points you include are  
> most definitely not co-planar.  The wriggling is done to make it  
> easier for the users of this information.  One of the major goals  
> of this draft was to make the GML portion of PIDF-LO more  
> accessible.  The up-normal calculation method in the appendix helps  
> with that.

Could we get away with just mandating counter clockwise polygons?

>
> For most applications, providing the distance between any two  
> points is short enough, keeping an identical altitude ensures a  
> pretty good approximation of a co-planar.  A definition of "short  
> enough" is included in the draft; your examples are a fair bit  
> outside of that distance.  Maybe I should be clearer on what  
> happens beyond this distance (geodesic interpolation, or fix  
> altitudes?).
>

I think that I missed the definition of short enough. Can you point  
right place. It seems like giving concrete advice on this would be  
good. Perhaps even just specifying a maximum diameter for polygons  
that were small enough for the approximation would be all that is  
needed.

> For an arc band - I believe that a planar approximation would be  
> acceptable, given that the distances are "short enough".  Thanks  
> for pointing out my omission on angles - the angle is the one  
> familiar to anyone who has used a compass - Northing (0) to Easting  
> (90).  The picture shows this, but I forgot my 'N' and 'E' markers.

(was a trivial nit :-)

>
> Choice of shapes has been driven by those that are used in existing  
> wireless systems.  In particular, these shapes are produced by 3GPP  
> wireless location services (3GPP TS 23.032).  Interoperability with  
> 3GPP was a major reason that fewer shapes were not included.  Many  
> of these shapes are those that are natively produced by location  
> determination algorithms; where those algorithms produce more  
> complex geometries it is generally accepted that an approximation  
> is used.

>
> I appreciate your point about the spherical interpolation, but I  
> think forcing support of that sort of mathematics would be a  
> prohibitive barrier to implementation.  In reality, inverse  
> flattening makes spherical interpolation infeasible, particularly  
> near the poles.  Geodesic interpolation would be required, which is  
> widely documented as being somewhere between tricky and a right PITA.

I probably land in the thinking it is a right PITA end of the  
spectrum. Questions is, are we making it simpler or are we sweeping  
something under the rug that is just going to cause buggy  
implementations. Do we need to say something like, this can not be  
used above 70 degrees latitude? Would a constraint like this be  
acceptable? I really don't know the answers to any of these - and I  
am not implying what is here won't work.  It's just not clear to me  
that it will work, or under what constraints it will fail.

Part of the difficulty here is this draft defines a way to specify  
shapes. The things I am talking about failing are computational  
geometry algorithm that operate on the shapes. Right now the draft  
does not indicate requirements for what algorithm we might want to  
compute on the defined shapes and the desired accuracy of theses  
computation so it makes it hard to decide if the shapes we are  
allowing make it to hard to implement the algorithms needed.

>
> So, thanks for the feedback!  You get a gold star for being the  
> first to get into the meat of this.  Has my response helped?  Or  
> did this just pile more confusion on?

Response helped a bunch - I'm sorry that right now I don't have any  
specific suggestions on how to improve. Some thoughts are getting  
crisp on constraints on shapes (such as max diameter and not near  
poles), then perhaps describe (by reference) some algorithm that are  
simple to implement and would produce results with acceptable error.  
I don't know this may be an awful idea, I just throwing stuff out and  
seeing it any of it makes sense to the experts.

---

From: "Thomson, Martin" <[email-masked]>
Date: Fri, 19 May 2006 00:33:00 -0500

Cullen,

I'll be submitting another copy of this draft that should appear some time soon.  In the new version I've made a few minor tweaks:

 - the guidance on when approximations are useful is a little more detailed, including the fact that processing these shapes might require tolerances built into the algorithms;
 - I've also noted that these shapes can be used without these approximations to precisely define shapes, depending on context;
 - text on applicability has been tweaked; and
 - I've also addressed some nits.

More inline with some snips...

Cheers,
Martin

> Sent: Friday, 19 May 2006 2:10 AM
> To: Thomson, Martin
> Cc: Andrew Newton; [email-masked]

This document is intended to provide shapes that are compatible with those used for 2-3G wireless.  I also intended it to cover a range of access technologies:

 - WiMAX is similar to 2-3G when it comes to location, comparable transmission range, etc...

 - the shapes work better as they get smaller, so it covers 802.11, Pringle cans and all.  The benefits of its use in 802.15 are questionable, but I see no reason why it wouldn't apply (location = my right pocket).

 - the shapes are also appropriate for describing a house, a small housing subdivision, a floor or floors of a building.  This suits wiremap type location methods, including DHCP.

I've also looked at cable, broadband over power, blimps with WiFi attached, ad hoc WiFi, you name it.  Defining a polygon that covers an entire country, for instance, requires quite a few points, not to mention complications from the curvature of the earth - I really think that would start to make the document a little too tricky to work with.
 
> I might be asking questions here that are actually answered in other

Rohan knows what he is talking about on this ;)

We actually do have other documents for those sorts of constraints.  More on that later...

> about what level of approximation we are assuming is needed would be

Thanks :)
 
> Could we get away with just mandating counter clockwise polygons?

I would like to leave the flexibility in how polygons are used and leave the only horizontal or only counter-clockwise recommendations to other documents.  That's a good one for PIDF-LO profile, but WGLC is about to finish...  sends another email... ok, just in time.

> that were small enough for the approximation would be all that is

Maximum recommended distances are covered in "4.4. Lines and Distances".  Pointing out the problem that occurs when the location nears the poles is a good suggestion. I have worked out a reasonable point where this degrades and have added notes to that effect: 3%error @ 130km @ 70 degrees.  70 degrees is good because it covers most of the populated area of the globe with only a few places sticking out.

> that it will work, or under what constraints it will fail.

Above.  Thanks for pointing out the latitude thing, I had thought about it, but it required some more calculations to work out some reasonable numbers.
 
> seeing it any of it makes sense to the experts.

From the perspective of algorithms, WGS84 has some nice ones for translating lat/long/alt into Cartesian systems, where you can do all that nice Cartesian geometry on them.  Most of the approximations just make that translation easier.  I.e. you can get a real polygon in Cartesian space, rather than a wonky twisted thing with non-parallel and curved faces.

Aside from that, the algorithms that you need are probably specific to the application.  I think that we are talking containment/overlap determination for LoST, others might just be doing conical or transverse Mercator projections for mapping.

I don't really want to dig too deeply into that area - it's outside what is needed for interoperation and frankly, you are likely to close off possibilities more than anything else.  All this fuzzy science leaves a lot of scope for innovation and unique ideas, which gets all very proprietary, particularly when it touches on location determination technology.  Of course, suggestions and pointers are welcome.

Cheers,
Martin

<snip old stuff>