Given an array arr[] containing N points of 2D plane and a reference point P0 (a0 , b0), the task is to sort these points according to their distance from the given point P0.
Examples:
Input: Points: [(1, 0), (0, -1), (-1, 0), (0, 1)]
Output: After sorting with reference point (0, 0)
[(1, 0), (0, 1), (-1, 0), (0, -1)]
After sorting with reference point (1, 1)
[(0, 1), (-1, 0), (0, -1), (1, 0)]Input: Points: [(-98, -65), (-65, -60), (65, -52), (-10, -47), (-7, -46), (26, -89), (72, -26), (66, -52), (69, 73), (-64, 0)]
Output: After sorting with reference point (0, 0)
[(69, 73), (-64, 0), (-98, -65), (-65, -60), (-10, -47), (-7, -46), (26, -89), (65, -52), (66, -52), (72, -26)]
Approach: This approach to solve this problem is with the help of Polar Angle
The polar angle of a point P1 with respect to an origin point P0 is the angle of the vector P1-P0 in the usual polar coordinate system.
For example, the polar angle of (3, 5) with respect to (2, 4) is the angle of the vector (1, 1), which is 45 degrees or π/4 radians.
In the following diagram, there are two vectors.
- First vector whose endpoint is PA(1, 1) makes an angle 45o with the x-axis.
- Second vector whose endpoint is PB(1, -1) makes an angle 315o with the x-axis.
- The origin point for both the vectors is PO(0, 0).
Cross Product
- Cross product is necessary to compute whether orientation of one vector with respect to another.
- Consider any two points P1 and P2.
- If their cross product is positive, then P1 is clockwise to P2 with respect to origin.
- If cross product is negative, then P1 is anti-clockwise from P2.
- In the above diagram,
PA = (1, 1) and PB = (1, -1)
PA x PB = -2k̂
Hence, PA is anti-clockwise to PB with respect to origin.
- If cross product is 0, then PA is collinear to PB.
- To determine if a line segment P0 – P1 is in clockwise or anti-clockwise direction to line segment P0 – P2, where P0 is their common endpoint, translate point P0 as the origin.
Given P0 (x0, y0), P1 (x1 , y1) and P2 (x3, y3)
(P1 – P0) x (P2 – P0) = (x1 – x0) (y2 – y0) – (x2 – x0) (y1 – y0)
- If cross product is positive, P0-P1 is clockwise to P0-P2, if it is negative, P0-P1 is anti-clockwise to P0-P2 else they are collinear.
- In the above diagram,
PA(1, 1), PB(2, 3) and PC(3, 1)
(PB – PA) = (1, 2)
(PC – PA) = (2, 0)(PB – PA) x (PC – PA) = -4k̂
Hence, vector PA-PB is in anti-clockwise direction to PA-PC with respect to point PA
Drawback of cross products:
- The angle between any two vectors varies between between [0, π). Hence using cross products, we can only measure angle between [0, π). Hence, if any two points has a polar angle difference greater than π with respect to any reference point, we will not get accurate direction.
- Consider the diagram given below again. If we compare polar angle of A with B, we will find B has a greater polar angle than A with respect to origin O(0, 0). However, if we translate point A and B to vectors and find their direction, we will find A x B = -1, which means A has greater polar angle than B with respect to origin point O. This is wrong. This happens because polar angle of vector PB = 315o and PA = 45o. There polar angle difference = 2700 is greater than π. This results in inaccurate results.
Overcoming drawback
- Before comparing any points by cross products, compare their y-coordinate to check if they both lie on the opposite side of x-axis or not. If we do, then the point above the y-axis definitely has a smaller polar angle. If they lie on the same side, then compare them using cross products. This technique ensures that polar angle difference between any two points always remain less than π.
Corner cases
- Corner cases arise when two points are collinear. If both the points lie on opposite side of y-axis, then the point in the first quadrant will have a smaller polar angle of 0o in comparison to any other points.
- Note: Consider point closer to the reference point P0 as smaller even though they have same polar angle.
Algorithm: The following approach uses merge-sort algorithm to sort N points in increasing order of their polar angle from reference point P0.
- Using merge sort, Sort all the points by polar angles by simply comparing direction of their vectors with respect to reference point P0.
- If any point PA is in anti-clockwise direction to PB with respect to reference point PO, PA has a greater polar angle with respect to PB.
- Use merge sort procedure in our sorting algorithm.
Illustration:
Consider 4 points [(-1, 0), (0, 1), (1, 0), (0, -1)] and reference point O(0, 0)
The merge sort procedure of the algorithm is quite straight forward.
The comparison and hence the core step of the algorithm lies in the merge procedure.
merge (-1, 0) and (0, 1)
- (-1, 0) and (0, 1) lie on same side of y-axis and their cross product = -1 is not 0.
- Hence they are not collinear.
- Simply compare them using their direction.
- Since cross product is negative, (-1, 0) lies in anti-clockwise direction with respect to (0, 1) and hence has a greater polar angle.
merge (1, 0) and (0, -1)
- (1, 0) and (0, -1) lie on opposite side of x-axis. Hence, (1, 0) has a smaller polar angle since it lies above x-axis.
merge [(0, 1), (-1, 0)] and [(1, 0), (0, -1)]
- The algorithm first compares (0, 1) with (1, 0). (0, 1) and (1, 0) lie on same side of y-axis and their cross product = -1 is not 0.
- Hence they are not collinear.
- Simply compare them using their direction.
- Since cross product is negative, (0, 1) lies in anti-clockwise direction with respect to (1, 0) and hence has a greater polar angle. Our final array so far is [(1, 0)].
- The algorithm then compares (0, 1) with (0, -1). (0, 1) and (0, -1) lie on opposite side of x-axis. Hence, (0, 1) has a smaller polar angle since it lies above x-axis. Our final array so far is [(1, 0), (0, 1)].
- The algorithm then compares (-1, 0) with (0, -1). (-1, 0) and (0, -1) lie on opposite side of x-axis. Hence, (-1, 0) has a smaller polar angle since it lies above x-axis. Our final array so far is [(1, 0), (0, 1), (-1, 0)].
- Then, fill the remaining point (0, -1) in the array. The final array is [(1, 0), (0, 1), (-1, 0), (0, -1)].
Below is the implementation of the above approach:
C++14
// C++ code for the above approach: #include <bits/stdc++.h> #include <vector> using namespace std; // Encapsulates a 2D point class Point { public : int x; int y; Point( int x, int y) : x(x) , y(y) { } }; // Checks if directed line segment pi-pk // is clockwise or anti-clockwise to pi-pj 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); } // Compares polar angle of two // points pk and pj with respect to pi. // In case all three points are // collinear, i.e. vector pi-pk // is collinear to vector pi-pj, // then it compares their // distance from the origin int compare(Point pi, Point pj, Point pk) { // if two points lie on opposite side // of x-axis, then simply return above // point as it has smaller polar angle 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; } // Check if both vectors are collinear if (direction(pi, pj, pk) == 0) { // Check if the vector lies on the y-axis if (pk.x - pi.x == 0 && pj.x - pi.x == 0) { // If vector lie on the y-axis // Then return -1, If vector pk-pi // has smaller magnitude // In comparison to pj-pi // Since vector with smaller // Magnitude has its end-point // Closer to the origin point p0 if ( abs (pk.y - pi.y) > abs (pj.y - pi.y)) { return -1; } else { return 1; } } // If vectors do not lie on the y-axis, // Then, either vector lie on the // x-axis or lie in the Same line. // Check if vectors lie on x-axis // and are on opposite side of y-axis // In such a case, return the vector // which lies on the positive x-axis // since it is in the first quadrant // and closer to origin 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; } // In other cases, return the point // closer to the reference point else if ( abs (pk.x - pi.x) > abs (pj.x - pi.x)) { return -1; } else { return 1; } } // If vectors lie on same side // of y-axis and are not collinear, // Then compare them using Cross product if (direction(pi, pj, pk) > 0) { return 1; } else { return -1; } } // Merge two sorted subarray in // Sorted order in place in // The points array range of // First subarray: p-q range // Of second subarray: q + 1 - r void merge(vector<Point>& points, int p, int q, int r, Point p0) { int n1 = q - p + 1; int n2 = r - q; vector<Point> L, R; for ( int i = 0; i < n1; i++) { L.push_back(points[p + i]); } for ( int j = 0; j < n2; j++) { R.push_back(points[q + 1 + j]); } int i = 0, j = 0; for ( int k = p; k <= r; k++) { if (i == n1) { points[k] = R[j]; j++; } else if (j == n2) { points[k] = L[i]; i++; } else if (compare(p0, L[i], R[j]) < 0) { points[k] = L[i]; i++; } else { points[k] = R[j]; j++; } } } // Arranges the point in ascending // according to their polar angle void merge_sort(vector<Point>& points, int p, int r, Point p0) { if (p < r) { int q = (p + r) / 2; merge_sort(points, p, q, p0); merge_sort(points, q + 1, r, p0); merge(points, p, q, r, p0); } } // Driver code int main() { // EXAMPLE 1 Point O(0, 0); vector<Point> points = { Point(1, 1), Point(2, 2), Point(3, 3), Point(-1, 1), Point(-2, 2), Point(-3, 3), Point(-1, -1), Point(-2, -2), Point(-3, -3), Point(1, -1), Point(2, -2), Point(3, -3) }; merge_sort(points, 0, points.size() - 1, O); for ( auto point : points) cout << "(" << point.x << "," << point.y << ")" << endl; return 0; } |
Java
// Java code for the above approach: import java.util.Arrays; public class SortingPoints { // Encapsulates a 2D point 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 + ")" ; } } // Checks if directed line segment pi-pk // is clockwise or anti-clockwise to pi-pj 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); } // Compares polar angle of two // points pk and pj with respect to pi. // In case all three points are // collinear, i.e. vector pi-pk // is collinear to vector pi-pj, // then it compares their // distance from the origin private static int compare( Point pi, Point pj, Point pk) { // if two points lie on opposite side // of x-axis, then simply return above // point as it has smaller polar angle 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 ; // Check if both vectors are collinear if (direction(pi, pj, pk) == 0 ) { // Check if the vector lies on the y-axis if (pk.x - pi.x == 0 && pj.x - pi.x == 0 ) { // If vector lie on the y-axis // Then return -1, If vector pk-pi // has smaller magnitude // In comparison to pj-pi // Since vector with smaller // Magnitude has its end-point // Closer to the origin point p0 if (Math.abs(pk.y - pi.y) > Math.abs(pj.y - pi.y)) return - 1 ; else return 1 ; } // If vectors do not lie on the y-axis, // Then, either vector lie on the // x-axis or lie in the Same line. // Check if vectors lie on x-axis // and are on opposite side of y-axis // In such a case, return the vector // which lies on the positive x-axis // since it is in the first quadrant // and closer to origin 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 ; // In other cases, return the point // closer to the reference point else if (Math.abs(pk.x - pi.x) > Math.abs(pj.x - pi.x)) return - 1 ; else return 1 ; } // If vectors lie on same side // of y-axis and are not collinear, // Then compare them using Cross product if (direction(pi, pj, pk) > 0 ) return 1 ; else return - 1 ; } // Merge two sorted subarray in // Sorted order in place in // The points array range of // First subarray: p-q range // Of second subarray: q + 1 - r 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++]; } } // Arranges the point in ascending // according to their polar angle 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); } } // Driver code public static void main(String[] args) { // EXAMPLE 1 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(); // EXAMPLE 2 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(); // EXAMPLE 3 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)); } } |
Python3
#Encapsulates a 2D point class Point: def __init__( self , x, y): self .x = x self .y = y def __str__( self ): return f "({self.x}, {self.y})" #Checks if directed line segment pi-pk # is clockwise or anti-clockwise to pi-pj def direction(pi, pj, pk): return (pk.x - pi.x) * (pj.y - pi.y) - (pj.x - pi.x) * (pk.y - pi.y) # Compares polar angle of two # points pk and pj with respect to pi. # In case all three points are # collinear, i.e. vector pi-pk #is collinear to vector pi-pj, # then it compares their # distance from the origin def compare(pi, pj, pk): #if two points lie on opposite side # of x-axis, then simply return above # point as it has smaller polar angle if pk.y - pi.y > = 0 and pj.y - pi.y < 0 : return 1 if pk.y - pi.y < 0 and pj.y - pi.y > = 0 : return - 1 #Check if both vectors are collinear if direction(pi, pj, pk) = = 0 : #Check if the vector lies on the y-axis if pk.x - pi.x = = 0 and pj.x - pi.x = = 0 : # If vector lie on the y-axis # Then return -1, If vector pk-pi # has smaller magnitude # In comparison to pj-pi # Since vector with smaller # Magnitude has its end-point # Closer to the origin point p0 if abs (pk.y - pi.y) > abs (pj.y - pi.y): return - 1 else : return 1 # If vectors do not lie on the y-axis, # Then, either vector lie on the # x-axis or lie in the Same line. # Check if vectors lie on x-axis # and are on opposite side of y-axis # In such a case, return the vector # which lies on the positive x-axis # since it is in the first quadrant # and closer to origin if pk.x - pi.x > 0 and pj.x - pi.x < 0 : return 1 elif pk.x - pi.x < 0 and pj.x - pi.x > 0 : return - 1 elif abs (pk.x - pi.x) > abs (pj.x - pi.x): return - 1 else : return 1 # If vectors lie on same side # of y-axis and are not collinear, # Then compare them using Cross product if direction(pi, pj, pk) > 0 : return 1 else : return - 1 # Merge two sorted subarray in # Sorted order in place in # The points array range of # First subarray: p-q range # Of second subarray: q + 1 - r def merge(points, p, q, r, p0): n1 = q - p + 1 n2 = r - q L = points[p:q + 1 ] R = points[q + 1 :r + 1 ] i = j = 0 for k in range (p, r + 1 ): if i = = n1: points[k] = R[j] j + = 1 elif j = = n2: points[k] = L[i] i + = 1 elif compare(p0, L[i], R[j]) < 0 : points[k] = L[i] i + = 1 else : points[k] = R[j] j + = 1 # Arranges the point in ascending # according to their polar angle def merge_sort(points, p, r, p0): if p < r: q = (p + r) / / 2 merge_sort(points, p, q, p0) merge_sort(points, q + 1 , r, p0) merge(points, p, q, r, p0) #Driver code if __name__ = = '__main__' : # EXAMPLE 1 O = Point( 0 , 0 ) points = [Point( 1 , 1 ), Point( 2 , 2 ), Point( 3 , 3 ), Point( - 1 , 1 ), Point( - 2 , 2 ), Point( - 3 , 3 ), Point( - 1 , - 1 ), Point( - 2 , - 2 ), Point( - 3 , - 3 ), Point( 1 , - 1 ), Point( 2 , - 2 ), Point( 3 , - 3 )] merge_sort(points, 0 , len (points) - 1 , O) for point in points: print (point) |
Javascript
// Encapsulates a 2D point class Point { constructor(x, y) { this .x = x; this .y = y; } toString() { return `(${ this .x}, ${ this .y})`; } } // Checks if directed line segment pi-pk // is clockwise or anti-clockwise to pi-pj function direction(pi, pj, pk) { return (pk.x - pi.x) * (pj.y - pi.y) - (pj.x - pi.x) * (pk.y - pi.y); } // Compares polar angle of two // points pk and pj with respect to pi. // In case all three points are // collinear, i.e. vector pi-pk // is collinear to vector pi-pj, // then it compares their // distance from the origin function compare(pi, pj, pk) { // if two points lie on opposite side // of x-axis, then simply return above // point as it has smaller polar angle 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; // Check if both vectors are collinear if (direction(pi, pj, pk) == 0) { // Check if the vector lies on the y-axis if (pk.x - pi.x == 0 && pj.x - pi.x == 0) { // If vector lie on the y-axis // Then return -1, If vector pk-pi // has smaller magnitude // In comparison to pj-pi // Since vector with smaller // Magnitude has its end-point // Closer to the origin point p0 if (Math.abs(pk.y - pi.y) > Math.abs(pj.y - pi.y)) return -1; else return 1; } // If vectors do not lie on the y-axis, // Then, either vector lie on the // x-axis or lie in the Same line. // Check if vectors lie on x-axis // and are on opposite side of y-axis // In such a case, return the vector // which lies on the positive x-axis // since it is in the first quadrant // and closer to origin 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; // In other cases, return the point // closer to the reference point else if (Math.abs(pk.x - pi.x) > Math.abs(pj.x - pi.x)) return -1; else return 1; } // If vectors lie on same side // of y-axis and are not collinear, // Then compare them using Cross product if (direction(pi, pj, pk) > 0) return 1; else return -1; } // Merge two sorted subarray in // Sorted order in place in // The points array range of // First subarray: p-q range // Of second subarray: q + 1 - r // Merge two sorted subarray in // Sorted order in place in // The points array range of // First subarray: p-q range // Of second subarray: q + 1 - r function merge(points, p, q, r, p0) { let n1 = q - p + 1; let n2 = r - q; let L = new Array(n1); let R = new Array(n2); for (let i = 0; i < n1; i++) { L[i] = points[p + i]; } for (let j = 0; j < n2; j++) { R[j] = points[q + 1 + j]; } let i = 0, j = 0; for (let 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++]; } } } // Arranges the point in ascending // according to their polar angle function mergeSort(points, p, r, p0) { let q; if (p < r) { q = Math.floor((p + r) / 2); mergeSort(points, p, q, p0); mergeSort(points, q + 1, r, p0); merge(points, p, q, r, p0); } } // EXAMPLE 1 let O = new Point(0, 0); let points = [ new Point(1, 0), new Point(0, -1), new Point(-1, 0), new Point(0, 1), ]; document.write( "Points: " + points); document.write( "<br>" ); mergeSort(points, 0, 3, O); document.write( "After sorting with reference point " + O+ "<br>" ); document.write(points); document.write( "<br>" ); // EXAMPLE 2 O = new Point(1, 1); mergeSort(points, 0, 3, O); document.write( "After sorting with reference point " + O+ "<br>" ); document.write(points); document.write( "<br>" ); // EXAMPLE 3 points = [ 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); document.write( "Points: " + points); document.write( "<br>" ); mergeSort(points, 0, 9, O); document.write( "After sorting with reference point " + O + "<br>" ); document.write(points); |
C#
// C# program to implement above approach using System; using System.Collections.Generic; // Encapsulates a 2D point class Point { public int x; public int y; public Point( int x, int y) { this .x = x; this .y = y; } public override String ToString() { return "(" + x + ", " + y + ")" ; } } class GFG { // Checks if directed line segment pi-pk // is clockwise or anti-clockwise to pi-pj 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); } // Compares polar angle of two // points pk and pj with respect to pi. // In case all three points are // collinear, i.e. vector pi-pk // is collinear to vector pi-pj, // then it compares their // distance from the origin private static int compare(Point pi, Point pj, Point pk) { // if two points lie on opposite side // of x-axis, then simply return above // point as it has smaller polar angle 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; } // Check if both vectors are collinear if (direction(pi, pj, pk) == 0) { // Check if the vector lies on the y-axis if (pk.x - pi.x == 0 && pj.x - pi.x == 0) { // If vector lie on the y-axis // Then return -1, If vector pk-pi // has smaller magnitude // In comparison to pj-pi // Since vector with smaller // Magnitude has its end-point // Closer to the origin point p0 if (Math.Abs(pk.y - pi.y) > Math.Abs(pj.y - pi.y)){ return -1; } else { return 1; } } // If vectors do not lie on the y-axis, // Then, either vector lie on the // x-axis or lie in the Same line. // Check if vectors lie on x-axis // and are on opposite side of y-axis // In such a case, return the vector // which lies on the positive x-axis // since it is in the first quadrant // and closer to origin 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; } // In other cases, return the point // closer to the reference point else if (Math.Abs(pk.x - pi.x) > Math.Abs(pj.x - pi.x)){ return -1; } else { return 1; } } // If vectors lie on same side // of y-axis and are not collinear, // Then compare them using Cross product if (direction(pi, pj, pk) > 0){ return 1; } else { return -1; } } // Merge two sorted subarray in // Sorted order in place in // The points array range of // First subarray: p-q range // Of second subarray: q + 1 - r 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 i1 = 0; i1 < n1 ; i1++){ L[i1] = points[p + i1]; } for ( int j1 = 0; j1 < n2; j1++){ R[j1] = points[q + 1 + j1]; } 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++]; } } } // Arranges the point in ascending // according to their polar angle 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); } } // Driver Code 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) }; Console.Write( "Points: [" ); for ( int i = 0 ; i < points.Length ; i++){ Console.Write(points[i]); if (i != points.Length-1){ Console.Write( " " ); } } Console.Write( "]\n" ); Console.Write( "\n" ); mergeSort(points, 0, 3, O); Console.Write( "After sorting with" + " reference point " + O + "\n[" ); for ( int i = 0 ; i < points.Length ; i++){ Console.Write(points[i]); if (i != points.Length-1){ Console.Write( " " ); } } Console.Write( "]\n" ); Console.Write( "\n" ); // EXAMPLE 2 O = new Point(1, 1); mergeSort(points, 0, 3, O); Console.Write( "After sorting with" + " reference point " + O + "\n[" ); for ( int i = 0 ; i < points.Length ; i++){ Console.Write(points[i]); if (i != points.Length-1){ Console.Write( " " ); } } Console.Write( "]\n" ); Console.Write( "\n" ); // EXAMPLE 3 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); Console.Write( "Points: [" ); for ( int i = 0 ; i < points.Length ; i++){ Console.Write(points[i]); if (i != points.Length-1){ Console.Write( " " ); } } Console.Write( "]\n" ); Console.Write( "\n" ); mergeSort(points, 0, 9, O); Console.Write( "After sorting with" + " reference point " + O + "\n[" ); for ( int i = 0 ; i < points.Length ; i++){ Console.Write(points[i]); if (i != points.Length-1){ Console.Write( " " ); } } Console.Write( "]\n" ); } } // This code is contributed by subhamgoyal2014. |
Time complexity: O(N log N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!