Pregunta Dividir un plano de puntos en dos mitades iguales


Dado un plano bidimensional en el que hay n puntos. Necesito generar la ecuación de una línea que divide el plano de tal forma que haya n / 2 puntos en un lado y n / 2 puntos en el otro. (Por cierto, esto no es trabajo a domicilio, solo estoy tratando de resolver el problema)


32
2018-06-23 23:36


origen


Respuestas:


He supuesto que los puntos son distintos, de lo contrario tal vez no exista tal línea.

Si los puntos son distintos, entonces tal línea siempre existe y es posible encontrar usando un determinista Algoritmo de tiempo O (nlogn).

Diga que los puntos son P1, P2, ..., P2n. Supongamos que no están todos en la misma línea. Si lo fueran, entonces podemos formar fácilmente la línea divisoria.

Primero traduzca los puntos para que todas las coordenadas (xey) sean positivas.

Ahora supongamos que mágicamente tenemos un punto Q en el eje y de tal manera que ninguna línea formada por esos puntos (es decir, cualquier línea infinita Pi-Pj) pasa a través de Q.

Ahora bien, dado que Q no se encuentra dentro del casco convexo de los puntos, podemos ver fácilmente que podemos ordenar los puntos mediante una línea giratoria que pasa por Q. Para un cierto ángulo de rotación, la mitad de los puntos estarán en un lado y la otra mitad estará en el otro lado de esta línea giratoria, o, en otras palabras, si consideramos que los puntos están ordenados por la pendiente de la línea Pi-Q, podríamos elegir una pendiente entre la (mediana) th y (mediana + 1) los puntos Esta selección se puede realizar en tiempo O (n) mediante cualquier algoritmo de selección de tiempo lineal sin necesidad de ordenar los puntos.

Ahora para elegir el punto Q.

Diga Q fue (0, b).

Supongamos que Q es colineal con P1 (x1, y1) y P2 (x2, y2).

Entonces tenemos eso

(y1-b) / x1 = (y2-b) / x2 (tenga en cuenta que traducimos los puntos para que xi> 0).

Resolviendo para b da

b = (x1y2 - y1x2) / (x1-x2)

(Tenga en cuenta que si x1 = x2, entonces P1 y P2 no pueden ser colineales con un punto en el eje Y).

Considera | b |.

| b | = | x1y2 - y1x2 | / | x1 -x2 |

Ahora, deje que xmax sea la coordenada x del extremo derecho y ymáx la coordenada del extremo superior.

También deje que D sea la diferencia de coordenadas x distinta de cero entre dos puntos (esto existe, ya que no todos los xis son iguales, ya que no todos los puntos son colineales).

Entonces tenemos eso | b | <= xmax * ymax / D.

Por lo tanto, elija nuestro punto Q (0, b) para que sea tal que | b | > b_0 = xmax * ymax / D

D se puede encontrar en el tiempo O (nlogn).

La magnitud de b_0 puede ser bastante grande y podríamos tener que lidiar con problemas de precisión.

Por supuesto, una mejor opción es elegir Q aleatoriamente. Con la probabilidad 1, encontrará el punto que necesita, lo que hace que el tiempo de ejecución esperado sea O (n).

Si pudiéramos encontrar una manera de elegir Q en O (n) tiempo (encontrando algún otro criterio), entonces podemos hacer que este algoritmo se ejecute en O (n) tiempo.


26
2018-06-24 02:17



  1. Crea una línea arbitraria en ese plano. Proyecte cada punto en esa línea a.k.a para cada punto, obtenga el punto más cercano en esa línea hasta ese punto.

  2. Ordene esos puntos a lo largo de la línea en cualquier dirección, y elija un punto en esa línea de modo que haya una cantidad igual de puntos en la línea en cualquier dirección.

  3. Obtenga la línea perpendicular a la primera línea que pasa por ese punto. Esta línea tendrá la mitad de los puntos originales en cada lado.

Hay algunos casos para evitar al hacer esto. Lo más importante es que si todos los puntos se encuentran en una sola línea, no elija una línea perpendicular que la atraviese. De hecho, elige esa línea para que no tengas que preocuparte de proyectar los puntos. En términos de las matemáticas reales detrás de esto, proyecciones vectoriales será muy útil.


10
2018-06-23 23:45



Esta es una modificación de Dividir un plano de puntos en dos mitades iguales que permite el caso con puntos superpuestos (en cuyo caso, dirá si la respuesta existe o no).

If number of points is odd, return "impossible".

Pick a random line (two random points)
Project all points onto this line (`O(N)` operation)
    (i.e. we pretend this line is our new X'-axis, and write down the
     X'-coordinate of each point)
Perform any median-finding algorithm on the X'-coordinates
    (`O(N)` or faster-if-desired operation)
    (returns 2 medians if no overlapping points)
Return the line perpendicular to original random line that splits the medians

In rare case of overlapping points, repeat a few times (it would take
a pathological case to prevent a solution from existing).

Esto es O(N) a diferencia de otras soluciones propuestas.

Suponiendo que existe una solución, el método anterior probablemente terminará, aunque no tengo una prueba.

Pruebe el algoritmo anterior algunas veces a menos que detecte puntos superpuestos. Si detecta una gran cantidad de puntos superpuestos, es posible que se encuentre en una situación difícil, pero existe una solución de fuerza bruta terriblemente ineficiente que implica verificar todos los puntos posibles. anglos:

For every "critical slope range", perform the above algorithm 
  by choosing a line with a slope within the range.
If all critical slope ranges fail, the solution is impossible.

Un ángulo crítico se define como el ángulo que posiblemente podría cambiar el resultado (imagine la solución a una respuesta previa, rote todo el conjunto de puntos hasta que uno o más puntos intercambien posición con uno o más puntos diferentes, cruzando la línea divisoria. solo un número finito de estos, y creo que están limitados por la cantidad de puntos, por lo que probablemente estés viendo algo en el rango O(N^2)-O(N^2 log(N)) si tiene puntos superpuestos, para un enfoque de fuerza bruta.


4
2018-05-10 10:47



Supongo que una buena manera es ordenar / secuenciar / ordenar los puntos (por ejemplo, de izquierda a derecha), y luego elegir una línea que atraviesa (o entre) el punto medio [s] de la secuencia.


1
2018-06-23 23:40



Hay casos obvios donde no hay solución posible. P.ej. cuando tienes tres montones de puntos Un punto en la ubicación A, dos puntos en la ubicación B y cinco puntos en la ubicación C.

Si espera una distribución decente, probablemente pueda obtener un buen resultado con el algoritmo de tlayton. Para seleccionar la inclinación de línea inicial, puede determinar la extensión del conjunto de puntos completo y elegir el ángulo de la diagonal más grande.


1
2018-06-23 23:53



los mediana igualmente divide un conjunto de números de manera similar a lo que está tratando de lograr, y se puede calcular en tiempo O (n) usando un algoritmo de selección (la descripción en Cormen et al es mejor, por lo que es posible que desee buscar allí). Entonces, encuentra la mediana de tus valores x MX (o tu y valora My si lo prefiere) y establecer x = MX (o y = My) y esa línea se alineará axialmente y dividirá sus puntos por igual.

Si la naturaleza de su problema requiere que no haya más de un punto en la línea (si tiene un número impar de puntos en su conjunto, al menos uno de ellos estará en la línea) y descubre que eso es lo que sucedió (o solo quiere protegerse de la posibilidad), rotar todos sus puntos con un ángulo aleatorio, θ, y calcular la mediana de los puntos girados. A continuación, gira la línea mediana calculada por -θ y dividirá los puntos por igual.

La probabilidad de elegir aleatoriamente θ de modo que el problema se manifieste de nuevo es muy pequeña con un número finito de puntos, pero si lo hace, inténtelo de nuevo con un θ diferente.


1
2018-06-24 02:18



No sé qué tan útil es esto. He visto un problema similar ...

Si ya tienes el vector direccional (también conocido como los coeficientes de las dimensiones de tu avión).

Luego puede encontrar dos puntos dentro de ese plano, y simplemente usando la fórmula del punto medio puede encontrar el punto medio de ese plano.

Luego, usando los coeficientes de ese plano y el punto medio, puede encontrar un plano que está a igual distancia de ambos puntos, usando la ecuación general de un plano.

Una línea entonces constituiría al expresar una variable en términos de la otra para que pueda encontrar una línea con la misma distancia entre ambos planos.

Hay diferentes métodos para hacer esto, como la proyección usando la ecuación de distancia desde un avión, pero creo que eso complicaría mucho tu matemática.


0
2018-06-24 00:08



Para agregar a la respuesta de M: un método para generar una Q (que no está tan lejos) en O(n log n).

Para empezar, deje Q ser alguna punto en el eje y, es decir. Q = (0,b) - algunas buenas elecciones pueden ser (0,0) o (0, (ymáximo-ymin) / 2).

Ahora comprueba si hay dos puntos (x1, y1), (X2, y2) colineal con Q. La línea entre cualquier punto y Q es y = mx + b; ya que b es constante, esto significa que dos puntos son colineales con Q si sus pendientes m son iguales. Así que determina las pendientes myo para todos los puntos y verificar si hay duplicados: (amorizado O(n) usando una tabla hash)

Si todos los m son distintos, hemos terminado; encontramos Q, y el algoritmo de M arriba genera la línea en O(n) pasos.
Si dos puntos son colineales con Q, moveremos Q solo una minúsculo cantidad ε, Qnuevo = (0, b + ε), y muestra que Qnuevo no será colineal con otros dos puntos.

El criterio para ε, derivado a continuación, es:

ε <mminΔ*Xmin

Para empezar, nuestros m se ven así:

metroyo = yyo/Xyo - b / xyo

Vamos a encontrar la diferencia mínima entre dos distinto metroyo y llámalo mminΔ  (O(n log n)  por, por ejemplo, ordenar y luego comparar las diferencias entre myo y i + 1 para todos i)

Si modificamos b por ε, la nueva ecuación para m se convierte en:

metroyo nuevo = yyo/Xyo - b / xyo - ε / xyo
       = myo viejo - ε / xyo

Desde ε> 0 yxyo > 0, todos los m se reducen, y todos se reducen en un máximo de ε / xmin. Por lo tanto, si

ε / xmin <mminΔ, es decir.
ε <mminΔ*Xmin

es cierto, luego dos myo que anteriormente eran desiguales, se garantizará que permanecen desiguales.


Todo lo que queda es mostrar que si m1, viejo = m2, viejo, entonces m1, nuevo = / = m2, nuevo. Como ambos myose redujeron en una cantidad ε / xyo, esto es equivalente a mostrar x1 = / = x2. Si ellos fueron igual, entonces:

y1 = m1, viejoX1 + b = m2, viejoX2 + b = y2

Contradiciendo nuestra suposición de que todos los puntos son distintos. Por lo tanto, m1, nuevo = / = m2, nuevo, y no hay dos puntos colineales con Q.


0
2018-06-24 21:12



Aquí es cómo me acerco a este problema (con la suposición de que n es par y NO hay tres puntos colineales):

1) Levante el punto con el valor Y más pequeño. Llamémoslo punto P.

2) Tome este punto como el nuevo punto de origen, de modo que todos los demás puntos tengan valores Y positivos después de esta transformación.

3) Para cada otro punto (quedan n - 1 puntos), créelo en el sistema de coordenadas polares. Cada otro punto se puede representar con un radio y un ángulo. Podría ignorar el radio y solo enfocarse en el ángulo.

4) ¿Cómo puedes encontrar una línea que divida los puntos de manera pareja? Encuentra la mediana de (n - 1) ángulos. La línea desde el punto P hasta el punto con ese ángulo medio dividirá los puntos de manera pareja.

La complejidad del tiempo para este algoritmo es O (n).


0
2017-08-03 13:27



Recogí la idea de Moron y andand y continuó formando un algoritmo determinista O (n).

También asumí que los puntos son distintos y n es par (pensado que el algoritmo puede ser cambiado para que n desigual con un punto en la línea divisoria también son compatibles).

El algoritmo intenta dividir los puntos con una línea vertical entre ellos. Esto solo falla si los puntos en el medio tienen el mismo valor de x. En ese caso, el algoritmo determina cuántos puntos con el mismo valor de x tienen que estar en el sitio izquierdo y el inferior y, en consecuencia, rota la línea.

Trataré de explicarlo con un ejemplo. Supongamos que tenemos 16 puntos en un avión. Primero necesitamos entender el punto con el 8vo mayor valor de x y el punto con el noveno mayor valor x. Con un algoritmo de selección esto es posible en O (n), como se señala en otra respuesta. Si el valor x de esos puntos es diferente, hemos terminado. Creamos una línea vertical entre esos dos puntos y que divide los puntos iguales

Problema ahora es si los valores de x son iguales. Entonces tenemos 3 conjuntos de puntos. Eso en el lado izquierdo (x <xun), en el medio (x = xun) y eso en el lado derecho (x> xun) La idea ahora es contar los puntos en el lado izquierdo y calcule cuántos puntos del centro debe ir allí, de modo que la mitad de los puntos están en ese lado. Podemos ignorar el lado derecho aquí porque si tenemos la mitad de los puntos en el lado izquierdo, la mitad superior debe estar en el lado derecho.

Así que supongamos que tenemos 3 puntos (c = 3) en el lado izquierdo, 6 en el medio y 7 en el lado derecho (el algoritmo no conoce el recuento desde el lado medio o derecho, porque no lo necesita, pero también podríamos determinarlo en O (n)). Necesitamos 8-3 = 5 puntos desde el medio para ir en el lado izquierdo. Los puntos que ya obtuvimos en el primer paso son inútiles ahora, porque solo están determinados por el valor de x y puede ser cualquiera de los puntos en el medio.

Queremos los 5 puntos del centro con el menor valor y en el lado izquierdo y el punto con el valor y más alto en el lado derecho. De nuevo, usando el algoritmo de selección, obtenemos el punto con el quinto mayor valor y y el punto con el sexto mayor valor y. Ambos puntos tendrán el valor x igual a xun, de lo contrario, no llegaríamos a este paso, porque habría una línea vertical

Ahora podemos crear el punto Q en el medio de esos dos puntos. Eso es un punto de la línea resultante. Se necesita otro punto, para que no se dividan puntos del lado izquierdo o derecho. Para obtener ese punto, necesitamos el punto del lado izquierdo, que tiene el ángulo más bajo (bh) entre la línea vertical en xun  y la línea determinada por ese punto y Q. También necesitamos ese punto del lado derecho (con ángulo agramo) El nuevo punto R está entre el punto con el ángulo más bajo y un punto en la línea vertical (si el ángulo inferior está en el lado izquierdo un punto arriba de Q y si el ángulo inferior está en el lado derecho un punto debajo de Q).

La línea determinada por Q y R divide los puntos en el medio de modo que haya un número par de puntos en ambos lados. No divide ningún punto en el lado izquierdo o derecho, porque si fuera ese punto tendría un ángulo más bajo y habría sido elegido para calcular R.

Desde la perspectiva de un matemático que debería funcionar bien en O (n). Para los programas de computadora es bastante fácil encontrar un caso donde la precisión se convierte en un problema Un ejemplo con 4 puntos sería A (0, 100000000), B (0, 100000001), C (0, 0), D (0,0000001, 0). En este ejemplo, Q sería (0, 100000000.5) y R (0.00000005, 0). Lo que da B y C en el lado izquierdo y A y D en el lado derecho. Pero es posible que A y B estén ambos en la línea divisoria, debido a errores de redondeo. O tal vez solo uno de ellos. Por lo tanto, pertenece a los valores de entrada si este algoritmo se ajusta a los requisitos.

  1. obtener esos dos puntos Pun(Xun, yun) y Psegundo(Xsegundo, ysegundo)
    que son las medianas basadas en los valores x > O(n)
  2. si xun ! = xsegundo puedes parar aquí
    porque una línea paralela del eje y entre esos dos puntos es el resultado > O(1)
  3. obtener todos los puntos donde el valor x es igual a xun  > O(n)
  4. contar puntos con x valor menor que xun como c > O(n)
  5. obtener el punto más bajo Pdo basado en los valores y de los puntos de 3. > O(n)
  6. obtener el mayor punto Pre basado en los valores y de los puntos de 3. > O(n)
  7. obtener el (n / 2-c) el punto más grande Pmi basado en los valores y de los puntos de 3. > O(n)
  8. también obtener el siguiente punto más grande PF basado en los valores y de los puntos de 3. > O(n)
  9. crear un nuevo punto Q (xun, (ymi+ yF) / 2) entre Pmi y PF  > O(1)
  10. para todos los puntos Pyo calcular
    el ángulo ayo entre Pdo, Q y Pyo y
    el ángulo byo entre Pre, Q y Pyo  > O(n)
  11. obtener el punto Pgramo con el ángulo más bajo agramo (con ungramo> 0 ° y agramo<180 °) > O(n)
  12. obtener el punto Ph con el ángulo más bajo bh (con Bh> 0 ° ybh<180 °) > O(n)
  13. si no hay ningún Pgramo o Ph (todos los puntos tienen el mismo valor x)
      crea un nuevo punto R (xun+1, 0) en cualquier lugar pero con un valor x diferente que xun
    de lo contrario sigramo es más bajo que bh
      crear un nuevo punto R ((xdo+ xgramo) / 2, (ydo+ ygramo) / 2) entre Pdo y Pgramo
    más
      crear un nuevo punto R ((xre+ xh) / 2, (yre+ yh) / 2) entre Pre y Ph  > O(1) 
  14. la línea determinada por Q y R divide los puntos > O(1)

0
2018-06-24 16:13