convex hull

ViewController.mm

//
//  ViewController.mm
//  convexHull
//
//  Created by Mizushima Yusuke on 8/23/15.
//  Copyright (c) 2015 Yusuke Mizusima. All rights reserved.
//

#import "ViewController.h"

#include <vector>
#include <memory>
using namespace std;

class ConvexHull {
public:
    void solve(vector<CGPoint> pts) {
        
        // swap first point
        int min = 0;
        for (int i=0; i<pts.size(); i++) {
            if (pts[i].y > pts[min].y || (pts[i].y == pts[0].y && pts[i].x > pts[0].x)) min = i;
        }
        swap(pts[0], pts[min]);
        
        sort(pts.begin() + 1, pts.end(), [pts](const CGPoint & a, const CGPoint & b) -> bool {
            return atan2(pts[0].y - a.y, pts[0].x - a.x) > atan2(pts[0].y - b.y, pts[0].x - b.x);
        });
        
        vector<CGPoint> hull;
        hull.emplace_back(pts[0]);
        hull.emplace_back(pts[1]);
        for (int m=1, i=2; i<pts.size(); i++) {
            while (ccw(CGVectorMake(hull[m].x - pts[i].x, hull[m].y - pts[i].y), CGVectorMake(hull[m-1].x - pts[i].x, hull[m-1].y - pts[i].y))) {
                hull.pop_back();
                m--;
            }
            hull.emplace_back(pts[i]);
            m++;
            
            notifyCheck(pts[i], hull);
        }
    }
private:
    bool ccw(CGVector a, CGVector b) {
        float CP = a.dx * b.dy - b.dx * a.dy;
        return CP < 0;
    }
    void notifyCheck(CGPoint p, vector<CGPoint> hull) {
        
        NSMutableArray *arr = [NSMutableArray array];
        for (auto p : hull) [arr addObject:[NSValue valueWithCGPoint:p]];
        
        [[NSNotificationCenter defaultCenter] postNotificationName:@"check node" object:
         @[[NSValue valueWithCGPoint:p], arr]];
    }
};

@interface ViewController () {
    vector<CGPoint> pts;
}
@property (nonatomic, strong) NSMutableArray *myblocks;
@property (nonatomic, strong) NSTimer *timer;
@property (nonatomic, weak) CAShapeLayer *hullLayer;
@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    self.view.backgroundColor = [UIColor purpleColor];
    
    CGPoint o = CGPointMake(CGRectGetMidX(self.view.bounds), CGRectGetMidY(self.view.bounds));
    float r0 = CGRectGetMidX(self.view.bounds) * 0.9;
    for (int i=0; i<100; i++) {
        float r = r0 * ((arc4random() % 45) / 50.0 + 0.1);
        float dw = M_PI * (arc4random() * 100) / 50.0;
        float x = r * cos(dw) + o.x;
        float y = r * sin(dw) + o.y;
        
        UIView *v = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 3, 3)];
        v.backgroundColor = [UIColor yellowColor];
        v.center = CGPointMake(x, y);
        [self.view addSubview:v];
        
        pts.emplace_back(CGPointMake(x, y));
    }
    
    [[NSNotificationCenter defaultCenter] addObserver:self selector:@selector(checkNode:) name:@"check node" object:nil];
}

- (void)touchesBegan:(NSSet *)touches withEvent:(UIEvent *)event {
    
    shared_ptr<ConvexHull> cppClass(new ConvexHull());
    cppClass->solve(pts);
    
}


typedef void (^MyBlock)(void);

- (void)checkNode:(NSNotification *)note {
    
    CGPoint p = [[note.object objectAtIndex:0] CGPointValue];
    NSArray *hull = [note.object objectAtIndex:1];
    
    MyBlock b = ^{
        
        [[self.view viewWithTag:1] removeFromSuperview];
        [self.hullLayer removeFromSuperlayer];
        
        
        UIView *mark = [[UIView alloc] initWithFrame:CGRectMake(0, 0, 5, 5)];
        mark.tag = 1;
        mark.backgroundColor = [UIColor redColor];
        mark.center = p;
        [self.view addSubview:mark];
        
        UIBezierPath *path = [UIBezierPath bezierPath];
        [path moveToPoint:[hull[0] CGPointValue]];
        for (int i=1; i<hull.count; i++) {
            [path addLineToPoint:[hull[i] CGPointValue]];
        }
        [path closePath];
        CAShapeLayer *line = [CAShapeLayer layer];
        line.name = @"my hull";
        line.strokeColor = [UIColor whiteColor].CGColor;
        line.fillColor = [UIColor clearColor].CGColor;
        line.path = path.CGPath;
        [self.view.layer addSublayer:line];
        self.hullLayer = line;
    };
    
    if (!self.myblocks) self.myblocks = [NSMutableArray array];
    
    [self.myblocks addObject:b];
    
    if (!self.timer) {
        self.timer = [NSTimer scheduledTimerWithTimeInterval:0.1 target:self selector:@selector(myfire) userInfo:nil repeats:YES];
    }
}

- (void)myfire{
    if (self.myblocks.count == 0) {
        [self.timer invalidate];
        self.timer = nil;
        return;
    }
    
    MyBlock b = ((MyBlock)self.myblocks[0]);
    b();
    [self.myblocks removeObject:b];
}

@end