creating a polygon with unsorted coordinates

– 2011/09/25Posted in: Notes, Personal, Programming

i was asked to take a variable number of map coordinates, and create a polygon. Sounds straightforward….and it is if the coordinates are already in a clockwise/counterclockwise order. But what if they are in a random order? You will end up with something like:

badpolygon

enter google/wikipedia/and all the developing community. My workflow was this:

  1. get feed with items and coordinates
  2. translate feed into native objects, each with a true CLLocationCoordinate2d
  3. toss these into an array
  4. sort the array into a clockwise order (ouch…hard part)
  5. draw polygon with the newly sorted array.

i tried many ways to approach this. Given that our earth is seperated into 4 major criteria (90,-90,180,and -180 degreees), i had to think this out in a more 2d sense. Apple / Google have already done the hard work translating the earth’s coordinate system into a flat space…Apple calls these MKMapPoints, and if you have coordinates, you can easily get these. By using these points, we don’t have to compensate for the hemispheres , positives , and/or negatives.

Once i have the desired points, I first place them on the map and find the common cross-section that they would all share:

 -(CLLocationCoordinate2D)coordinateWithOtherCoordinates:(NSArray*)arrayOfAnnotations
 {
 //return value
 CLLocationCoordinate2D coord;
 
 //total in array
 int length  = [arrayOfAnnotations count];
 
 
 float avgLat    = 0;
 float avgLng    = 0;
 
 for (FrientroidAnnotation *annot in arrayOfAnnotations) {
 CLLocationCoordinate2D coord = [annot coordinate];
 
 avgLat += coord.latitude;
 avgLng += coord.longitude;
 
 }
 
 float midLat = avgLat/length;
 float midLng = avgLng/length;
 coord.latitude = midLat;
 coord.longitude = midLng;
 return coord;
 }
<pre>
<p>Now we can lay all our annotations and this newly found center point. However, the annotations are not necessarily in clockwise/ccw order. This will result in funny triangles making our shape. To fix that, i had to attach a sorting method to each annotation to find the angle of that point in relation to the center. Like that we can rearrange our points so that they are calculated in an organized fashion, before we draw our shape:</p?
<pre lang="objc">
CGFloat RadiansToDegrees(CGFloat radians)
{
    return radians * 180 / M_PI;
};
-(NSComparisonResult)compareByPoint:(FrientroidAnnotation*)c
{
    float myAngle = [self radiansFromPoint:_centerCoord];
    float cAngle = [c radiansFromPoint:[c centerCoord]];
 
    float myDeg = RadiansToDegrees(myAngle);
    float cDeg = RadiansToDegrees(cAngle);
 
    if (myDeg<cDeg) {
        return NSOrderedDescending;
    }
 
    if (myDeg>cDeg) {
        return NSOrderedAscending;
    }
    return NSOrderedSame;
 
}

In my controller (handling the array of these objects), i take the unsorted array, and sort them into a clockwise manner:

-(void)addPolygonWithPoints:(NSArray*)pointsArray center:(CLLocationCoordinate2D)centerPoint
{
    int count = [pointsArray count];
    for (int c= 0; c< count; c++) {
       MyClassAnnotation *an = (FrientroidAnnotation*)[pointsArray objectAtIndex:c];
        [an setCenterCoord:centerPoint];
    }
    //get top most   
    NSArray *sorted = [pointsArray sortedArrayUsingSelector:@selector(compareByPoint:)];   
 
    //prepare the polygon based on users
 
    CLLocationCoordinate2D *points = malloc(sizeof(CLLocationCoordinate2D) * count);    
    for (int c= 0; c< count; c++) {
       MyClassAnnotation *an = (FrientroidAnnotation*)[sorted objectAtIndex:c];
        CLLocationCoordinate2D crd;
        crd.latitude = an.coordinate.latitude;
        crd.longitude = an.coordinate.longitude;
        points[c] = crd;
    }
 
    MKMultiPoint *poly;
    if ([pointsArray count]>2) {
        //addoverlay    
        poly = [MKPolygon polygonWithCoordinates:points count:count];        
 
    }
 
    if ([pointsArray count] == 2) {
        poly = [MKPolyline polylineWithCoordinates:points count:2];
    }
    [self performSelector:@selector(onOverlay:) withObject:poly afterDelay:1.0];
}

voila

goodpolygon