Dada una array arr[] que contiene N puntos del plano 2D y un punto de referencia P 0 (a 0 , b 0 ) , la tarea es clasificar estos puntos según su distancia desde el punto P 0 dado .
Ejemplos:
Entrada: Puntos: [(1, 0), (0, -1), (-1, 0), (0, 1)]
Salida: Después de clasificar con el punto de referencia (0, 0)
[(1, 0), (0, 1), (-1, 0), (0, -1)]
Después de clasificar con el punto de referencia (1, 1)
[(0, 1), (-1, 0), (0, -1) , (1, 0)]Entrada: Puntos: [(-98, -65), (-65, -60), (65, -52), (-10, -47), (-7, -46), (26, -89) , (72, -26), (66, -52), (69, 73), (-64, 0)]
Salida: Después de ordenar con el punto de referencia (0, 0)
[(69, 73), (-64 , 0), (-98, -65), (-65, -60), (-10, -47), (-7, -46), (26, -89), (65, -52), (66, -52), (72, -26)]
Enfoque: este enfoque para resolver este problema es con la ayuda de Polar Angle
El ángulo polar de un punto P 1 con respecto a un punto de origen P 0 es el ángulo del vector P 1 -P 0 en el sistema de coordenadas polares habitual.
Por ejemplo, el ángulo polar de (3, 5) con respecto a (2, 4) es el ángulo del vector (1, 1), que es de 45 grados o π/4 radianes.
En el siguiente diagrama, hay dos vectores.
- Primer vector cuyo extremo es P A (1, 1) forma un ángulo de 45 ° con el eje x.
- Segundo vector cuyo extremo es P B (1, -1) forma un ángulo de 315 ° con el eje x.
- El punto de origen de ambos vectores es P O (0, 0).
Producto cruzado
- El producto cruzado es necesario para calcular si la orientación de un vector con respecto a otro.
- Considere dos puntos cualesquiera P 1 y P 2 .
- Si su producto vectorial es positivo, entonces P 1 es en el sentido de las agujas del reloj a P 2 con respecto al origen.
- Si el producto vectorial es negativo, entonces P 1 es en sentido antihorario desde P 2 .
- En el diagrama anterior,
PA = (1, 1) y PA = (1, -1 )
P A x P B = -2k̂
Por lo tanto, P A es en sentido antihorario a P B con respecto al origen.
- Si el producto vectorial es 0, entonces P A es colineal con P B .
- Para determinar si un segmento de línea P 0 – P 1 está en sentido horario o antihorario hacia el segmento de línea P 0 – P 2, donde P 0 es su punto final común, traslade el punto P 0 como el origen.
Dado P 0 (x 0 , y 0 ), P 1 (x 1 , y 1 ) y P 2 (x 3 , y 3 )
(P 1 – P 0 ) x (P 2 – P 0 ) = (x 1 – x 0 ) (y 2 – y 0 ) – (x 2 – x 0 ) (y 1 – y 0 )
- Si el producto cruzado es positivo, P 0 -P 1 es en sentido horario a P 0 -P 2 , si es negativo, P 0 -P 1 es en sentido antihorario a P 0 -P 2 de lo contrario son colineales.
- En el diagrama anterior,
PA (1, 1), PA B (2, 3) y PA ( 3 , 1)
(PAG – PAG ) = (1, 2)
(PAG – PAG ) = (2, 0)(P B – P A ) x (P C – P A ) = -4k̂
Por lo tanto, el vector P A -P B está en dirección contraria a las manecillas del reloj hacia P A -P C con respecto al punto P A
Inconveniente de los productos cruzados:
- El ángulo entre dos vectores cualesquiera varía entre [0, π). Por lo tanto, usando productos cruzados, solo podemos medir el ángulo entre [0, π). Por lo tanto, si dos puntos cualesquiera tienen una diferencia de ángulo polar mayor que π con respecto a cualquier punto de referencia, no obtendremos una dirección precisa.
- Considere nuevamente el diagrama que se presenta a continuación. Si comparamos el ángulo polar de A con B, encontraremos que B tiene un ángulo polar mayor que A con respecto al origen O(0, 0). Sin embargo, si trasladamos el punto A y B a vectores y encontramos su dirección, encontraremos A x B = -1, lo que significa que A tiene un ángulo polar mayor que B con respecto al punto de origen O. Esto es incorrecto . Esto sucede porque el ángulo polar del vector P B = 315 o y P A = 45 o . Hay diferencia de ángulo polar = 270 0 es mayor que π. Esto da como resultado resultados inexactos.
superando el inconveniente
- Antes de comparar cualquier punto por productos cruzados, compare su coordenada y para verificar si ambos se encuentran en el lado opuesto del eje x o no. Si lo hacemos, entonces el punto sobre el eje y definitivamente tiene un ángulo polar más pequeño. Si se encuentran en el mismo lado, compárelos usando productos cruzados. Esta técnica asegura que la diferencia de ángulo polar entre dos puntos cualesquiera siempre sea menor que π.
Estuches de esquina
- Los casos de esquina surgen cuando dos puntos son colineales. Si ambos puntos se encuentran en el lado opuesto del eje y, entonces el punto en el primer cuadrante tendrá un ángulo polar menor de 0 o en comparación con cualquier otro punto.
- Nota: Considere el punto más cercano al punto de referencia P 0 como más pequeño aunque tengan el mismo ángulo polar.
Algoritmo: el siguiente enfoque utiliza un algoritmo de clasificación por combinación para clasificar N puntos en orden creciente de su ángulo polar desde el punto de referencia P 0 .
- Utilizando la ordenación por fusión, ordene todos los puntos por ángulos polares simplemente comparando la dirección de sus vectores con respecto al punto de referencia P 0 .
- Si cualquier punto P A está en sentido antihorario a P B con respecto al punto de referencia P O , P A tiene un ángulo polar mayor con respecto a P B .
- Utilice el procedimiento de clasificación por fusión en nuestro algoritmo de clasificación.
Ilustración:
Considere 4 puntos [(-1, 0), (0, 1), (1, 0), (0, -1)] y el punto de referencia O(0, 0)
El procedimiento de clasificación por fusión del algoritmo es bastante sencillo.
La comparación y, por lo tanto, el paso central del algoritmo se encuentra en el procedimiento de fusión.
combinar (-1, 0) y (0, 1)
- (-1, 0) y (0, 1) se encuentran en el mismo lado del eje y y su producto vectorial = -1 no es 0.
- Por lo tanto, no son colineales.
- Simplemente compárelos usando su dirección.
- Dado que el producto vectorial es negativo, (-1, 0) se encuentra en sentido contrario a las agujas del reloj con respecto a (0, 1) y, por lo tanto, tiene un ángulo polar mayor.
combinar (1, 0) y (0, -1)
- (1, 0) y (0, -1) se encuentran en el lado opuesto del eje x. Por lo tanto, (1, 0) tiene un ángulo polar más pequeño ya que se encuentra sobre el eje x.
combinar [(0, 1), (-1, 0)] y [(1, 0), (0, -1)]
- El algoritmo primero compara (0, 1) con (1, 0). (0, 1) y (1, 0) se encuentran en el mismo lado del eje y y su producto vectorial = -1 no es 0.
- Por lo tanto, no son colineales.
- Simplemente compárelos usando su dirección.
- Dado que el producto vectorial es negativo, (0, 1) se encuentra en sentido contrario a las agujas del reloj con respecto a (1, 0) y, por lo tanto, tiene un ángulo polar mayor. Nuestra array final hasta ahora es [(1, 0)].
- Luego, el algoritmo compara (0, 1) con (0, -1). (0, 1) y (0, -1) se encuentran en el lado opuesto del eje x. Por lo tanto, (0, 1) tiene un ángulo polar más pequeño ya que se encuentra sobre el eje x. Nuestra array final hasta ahora es [(1, 0), (0, 1)].
- Luego, el algoritmo compara (-1, 0) con (0, -1). (-1, 0) y (0, -1) se encuentran en el lado opuesto del eje x. Por lo tanto, (-1, 0) tiene un ángulo polar más pequeño ya que se encuentra sobre el eje x. Nuestra array final hasta ahora es [(1, 0), (0, 1), (-1, 0)].
- Luego, complete el punto restante (0, -1) en la array. La array final es [(1, 0), (0, 1), (-1, 0), (0, -1)].
A continuación se muestra la implementación del enfoque anterior:
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));
}
}
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.
Salida: Puntos: [(1, 0), (0, -1), (-1, 0), (0, 1)] Después de ordenar con punto de referencia (0, 0) [(1, 0), (0 , 1), (-1, 0), (0, -1)] Después de clasificar con el punto de referencia (1, 1) [(0, 1), (-1, 0), (0, -1), ( 1, 0)] Puntos: [(-98, -65), (-65, -60), (65, -52), (-10, -47), (-7, -46), (26, -89), (72, -26), (66, -52), (69, 73), (-64, 0)] Después de clasificar con el punto de referencia (0, 0) [(69, 73), (- 64, 0), (-98, -65), (-65, -60), (-10, -47), (-7, -46), (26, -89), (65, -52) , (66, -52), (72, -26)]
Complejidad temporal: O(N log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por anujanonymous y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA