K Closest Points

/**
 * @param points a list of points
 * @param origin a point
 * @param k an integer
 * @return the k closest points
 */
public Point[] kClosest(Point[] points, Point origin, int k) {
    final Point global_origin = origin;
    PriorityQueue<Point> priorityqueue = new PriorityQueue<Point>(k, new Comparator<Point>(){
            @Override
            public int compare(Point a, Point b){
                int diff = getDistance(b, global_origin) - getDistance(a, global_origin);
                if(diff == 0){
                    diff = b.x - a.x;
                }
                if(diff == 0){
                    diff = b.y - a.y;
                }
                return diff;
            }
        });
    
    for(int i = 0; i < points.length; i++){
        priorityqueue.offer(points[i]);
        if(priorityqueue.size() > k){
            priorityqueue.poll();
        }
    }
    k = priorityqueue.size();
    Point[] res = new Point[k];
    while(!priorityqueue.isEmpty()){
        res[--k] = priorityqueue.poll();
    }
    return res;
}
private int getDistance(Point a, Point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s