Sort an Array of Points wrt distance from Reference Point | Set 2 (using Polar Angles)

 

import java.util.Arrays;

 

public class SortingPoints {

 

    

    public static class Point {

        int x;

        int y;

 

        public Point(int x, int y)

        {

            this.x = x;

            this.y = y;

        }

 

        @Override

        public String toString()

        {

            return "(" + x + ", " + y + ")";

        }

    }

 

    

    

    private static int direction(

        Point pi, Point pj, Point pk)

    {

        return (pk.x - pi.x) * (pj.y - pi.y)

            - (pj.x - pi.x) * (pk.y - pi.y);

    }

 

    

    

    

    

    

    

    

    private static int compare(

        Point pi, Point pj, Point pk)

    {

 

        

        

        

        if (pk.y - pi.y >= 0 && pj.y - pi.y < 0)

            return 1;

        if (pk.y - pi.y < 0 && pj.y - pi.y >= 0)

            return -1;

 

        

        if (direction(pi, pj, pk) == 0) {

 

            

            if (pk.x - pi.x == 0 && pj.x - pi.x == 0) {

 

                

                

                

                

                

                

                

 

                if (Math.abs(pk.y - pi.y)

                    > Math.abs(pj.y - pi.y))

                    return -1;

                else

                    return 1;

            }

 

            

            

            

 

            

            

            

            

            

            

            if (pk.x - pi.x > 0

                && pj.x - pi.x < 0)

                return 1;

            else if (pk.x - pi.x < 0

                     && pj.x - pi.x > 0)

                return -1;

 

            

            

            else if (Math.abs(pk.x - pi.x)

                     > Math.abs(pj.x - pi.x))

                return -1;

            else

                return 1;

        }

 

        

        

        

        if (direction(pi, pj, pk) > 0)

            return 1;

        else

            return -1;

    }

 

    

    

    

    

    

    private static void merge(

        Point[] points,

        int p, int q,

        int r, Point p0)

    {

        int n1 = q - p + 1;

        int n2 = r - q;

 

        Point[] L = new Point[n1];

        Point[] R = new Point[n2];

 

        for (int i = 0; i < n1; i++)

            L[i] = points[p + i];

        for (int j = 0; j < n2; j++)

            R[j] = points[q + 1 + j];

 

        int i = 0, j = 0;

 

        for (int k = p; k <= r; k++) {

            if (i == n1)

                points[k] = R[j++];

            else if (j == n2)

                points[k] = L[i++];

            else if (compare(p0, L[i], R[j]) < 0)

                points[k] = L[i++];

            else

                points[k] = R[j++];

        }

    }

 

    

    

    public static void mergeSort(

        Point[] points, int p,

        int r, Point p0)

    {

        int q;

        if (p < r) {

            q = (p + r) / 2;

            mergeSort(points, p, q, p0);

            mergeSort(points, q + 1, r, p0);

            merge(points, p, q, r, p0);

        }

    }

 

    

    public static void main(String[] args)

    {

        

        Point O = new Point(0, 0);

        Point[] points

            = { new Point(1, 0),

                new Point(0, -1),

                new Point(-1, 0),

                new Point(0, 1) };

 

        System.out.println(

            "Points: "

            + Arrays.toString(points));

        System.out.println();

 

        mergeSort(points, 0, 3, O);

        System.out.println(

            "After sorting with"

            + " reference point " + O);

        System.out.println(

            Arrays.toString(points));

        System.out.println();

 

        

        O = new Point(1, 1);

        mergeSort(points, 0, 3, O);

        System.out.println(

            "After sorting with"

            + " reference point " + O);

        System.out.println(

            Arrays.toString(points));

        System.out.println();

 

        

        points = new Point[] {

            new Point(-98, -65),

            new Point(-65, -60),

            new Point(65, -52),

            new Point(-10, -47),

            new Point(-7, -46),

            new Point(26, -89),

            new Point(72, -26),

            new Point(66, -52),

            new Point(69, 73),

            new Point(-64, 0)

        };

        O = new Point(0, 0);

 

        System.out.println(

            "Points: "

            + Arrays.toString(points));

        System.out.println();

 

        mergeSort(points, 0, 9, O);

        System.out.println(

            "After sorting with"

            + " reference point " + O);

        System.out.println(

            Arrays.toString(points));

    }

}

Leave a Comment