So you're think you're good at math?

[Bugs ****ing Bunny]

If the end result of this gibberish is anything short of cold fusion I'm going to be bitterly disappointed.

[KrazyHorse]

I bet it's a GPS/mapping utility on a phone.

[Asher]

It's a desktop web app for the company to define various "tiers" of geographic regions. We're overhauling our back-end to be fully geocentric with polygonal search. Instead of just looking for a given business within X kilometers of the user's current location, it'll use the defined polygon to search within. This is useful for places like Montreal which has something called a "river" that may be annoying in crossing when getting results.

The multipliers exist because if there's few or no results within the polygon, it'll multiply and multiply the polygon size until it reaches a satisfactory number of results. I didn't write the business specs on this...

This tool allows Frenchmen in Quebec to define polygons throughout Canada and then export the polygonal data to our database servers.

[Asher]

Asher, I'm not sure your problem is well-formulated....

An example for why I say this is as follows: Take as your polygon a square "centered" at the north pole with "radius" (distance from north pole to each vertex) of pi/2*R where R is the Earth's radius

First off, the location of the "centroid" is ambiguous; is it the north pole or the south pole?

Secondly, if you "double" this polygon you either end up with 4 overlapping points at the south pole (if you assumed the original polygon was centered at the north pole) or at the north pole (if you assumed a center at the south pole)

Either way, the side lengths have shrunk under a "doubling".

I can take shortcuts here because we'll never draw polygons around the pole. They'll almost always be close to the 49th, or a bit north...Canadian population centres. So I don't think this will be an issue unless I misunderstand you.

For less extreme cases, it is ALWAYS true that "doubling" the polygon using the method you claim here will scale the side lengths by a factor LESS than 2. This is because a sphere is a surface of constant positive curvature. More worryingly, the side lengths will all change by different factors (sides closer to the centroid will increase in length more than sides far from the centroid)

In other words, if I "double" an equilateral triangle of sides 500 km I will end up, using your method, with a triangle of sides less than 1000 km, and for more complex figures not even the ratio of side lengths is constant.

What is the purpose of this function? We need to know what the appropriate sense of "scale" is; is it side lengths? Is it "radius"? Is it something else?

The numbers do not need to be exact in terms of expanded size, just consistent. Think of the multiplication factor as a fudge factor. We need to incrementally make the polygons bigger so we can gather more results, they don't need to be precisely bigger as defined by the multiplier. For whatever reason, the only requirements are (1) the polygons get bigger that is more-or-less specified by a number as to how large it'll get, (2) the shape of the polygon is the same

[Asher]

When presented with the specs I argued that multiplying the polygons made no sense. They're being defined around specific geographic landmarks or attributes, so if we need to get more results than that we may as well fall-back to simple radial searches. There's no point to multiplying the polygon if we're no longer adhering to the geographic landmarks.

But as I said, they were Frenchmen liberal arts-grads and did not understand.

[Ramo]

Well, you're basically looking to scale a polygon in a conformal (angle preserving) map to a cartesian space (i.e the Mercator projection). The easy way to conceptualize this (and minimize error) would probably be to apply the conformal map, scale the polygon, then apply the inverse of the conformal map. This way, BTW, you get every point on the polygon fairly easily.

[KrazyHorse]

Ramo, I don't think conformal mapping is vary important here...

[Elok]

No. No, I do not think I am good at math.

[Ramo]

Ramo, I don't think conformal mapping is vary important here...

Yeah, I suppose you're right. The initial polygon would be one in the sense of an isometric map to a cartesian space.

[Asher]

Got it working. ****ing right!

[Asher]

Here's the code excerpt (in Javascript) to see how I've done it:

var d = distHaversine(centre, point);
d = d * mult;
var brng = bearing(centre, point);
var newpoint = destPoint(centre, brng, d);

    function distHaversine(point1, point2) 
    {
        var lat1 = point1.lat();
        var lon1 = point1.lng();
        var lat2 = point2.lat();
        var lon2 = point2.lng();
        
        var R = 6371; // earth's mean radius in km
        var dLat = (lat2-lat1).toRad();
        var dLon = (lon2-lon1).toRad();
        lat1 = lat1.toRad(), lat2 = lat2.toRad();
        
        var a = Math.sin(dLat/2) * Math.sin(dLat/2) +
                Math.cos(lat1) * Math.cos(lat2) * 
                Math.sin(dLon/2) * Math.sin(dLon/2);
        var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a));
        var d = R * c;
        return d;
    }
    
    function bearing(point1, point2) 
    {
        var lat1 = point1.lat();
        var lon1 = point1.lng();
        var lat2 = point2.lat();
        var lon2 = point2.lng();
        
        lat1 = lat1.toRad(); lat2 = lat2.toRad();
        var dLon = (lon2-lon1).toRad();
        
        var y = Math.sin(dLon) * Math.cos(lat2);
        var x = Math.cos(lat1)*Math.sin(lat2) -
                Math.sin(lat1)*Math.cos(lat2)*Math.cos(dLon);
        return Math.atan2(y, x).toBrng();
    }
    
    function destPoint(centre, brng, d) 
    {
      var R = 6371; // earth's mean radius in km
      var lat1 = centre.lat().toRad(), lon1 = centre.lng().toRad();
      brng = brng.toRad();
    
      var lat2 = Math.asin( Math.sin(lat1)*Math.cos(d/R) + 
                            Math.cos(lat1)*Math.sin(d/R)*Math.cos(brng) );
      var lon2 = lon1 + Math.atan2(Math.sin(brng)*Math.sin(d/R)*Math.cos(lat1), 
                                   Math.cos(d/R)-Math.sin(lat1)*Math.sin(lat2));
      lon2 = (lon2+Math.PI)%(2*Math.PI) - Math.PI;  // normalise to -180...+180
    
      if (isNaN(lat2) || isNaN(lon2)) 
        return null;
        
      return new GLatLng(lat2.toDeg(), lon2.toDeg());
    }
    
    // overloads
    // convert degrees to radians
    Number.prototype.toRad = function() 
    {  
        return this * Math.PI / 180;
    }
    
    // convert radians to degrees (signed)
    Number.prototype.toDeg = function() 
    {  
        return this * 180 / Math.PI;
    }
    
    // convert radians to degrees (as bearing: 0...360)
    Number.prototype.toBrng = function() 
    {  
      return (this.toDeg()+360) % 360;
    }

[Asher]

And thanks for everyone's help. I'm just thrilled there wasn't a simple one-line solution I was missing. I'm not totally retarded.

[loinburger]

If I were given that problem spec I'd just pretend that the world was flat - the user's polygon is imprecise so we can fudge on expanding it. Also, if the polygon is "centered" around a specific location ie the user's location then it may make sense to pretend that location is the centroid when expanding the polygon.

[Asher]

If I were given that problem spec I'd just pretend that the world was flat - the user's polygon is imprecise so we can fudge on expanding it. Also, if the polygon is "centered" around a specific location ie the user's location then it may make sense to pretend that location is the centroid when expanding the polygon.

There's two "users" to this though: the guy creating the polygon using my tool is the user. The guy who uses our apps to find businesses is the end-user, who indirectly uses the polygonal search.

So the polygons are never centered around the end-user, the end user is just within a polygon defined by the user of my tool (heh heh).

The polygons are expanded irrespective of the end-user's position, they're expanded upon their geographic centre as defined by the tool-user.

The polygons defined by my tool are being exported to SQL Server 2008, where my sexy new geolocation-enabled database can use the polygons to perform searches against our data store. The back-end team for this is stupid and couldn't comprehend how to do polygon expansion, so now I get to implement it in the front-end and then export an array of pre-expanded polygons for their stupid asses.

[Ben Kenobi]

Cool, I'm glad I was on the right track.

This is actually similar to some stuff we had to do in Astro way back when. We were always working in Polars (RA + Dec).