algorithm - computational - cgal
Dividir un plano de puntos en dos mitades iguales (10)
Crea una línea arbitraria en ese plano. Proyecte cada punto en esa línea, también conocida como la de cada punto, obtenga el punto más cercano en esa línea hasta ese punto.
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.
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, las proyecciones vectoriales serán muy útiles.
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)
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).
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) 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 ángulos posibles:
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 tienes superposición puntos, para un enfoque de fuerza bruta.
Hay casos obvios donde no hay solución posible. Por ejemplo, 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.
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 encontrarla usando un algoritmo de tiempo O (nlogn) determinista .
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.
La median divide equitativamente 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 escritura en Cormen et al es mejor, por lo que puede querer para mirar allí en su lugar). Entonces, encuentra la mediana de tus valores x M x (o tu y valores M y si lo prefieres) y establece x = M x (oy = M y ) y esa línea se alineará axialmente y dividirá tus 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.
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.
Entonces, una línea se constituiría al expresar una variable en términos de la otra, de modo que encontrarías 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.
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 sea cualquier punto en el eje y, es decir. Q = (0,b) - algunas buenas elecciones pueden ser (0,0) o (0, (y max -y min ) / 2).
Ahora comprueba si hay dos puntos (x 1 , y 1 ), (x 2 , y 2 ) colineales con Q. La línea entre cualquier punto y Q es y = mx + b ; dado que b es constante, esto significa que dos puntos son colineales con Q si sus pendientes m son iguales. Por lo tanto, determine las pendientes m i para todos los puntos y compruebe si hay algún duplicado: ( O(n) 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 pequeña cantidad ε, Q new = (0, b + ε), y mostraremos que Q new no será colineal con otros dos puntos.
El criterio para ε, derivado a continuación, es:
ε < mminΔ*xmin
Para empezar, nuestros m se ven así:
mi = yi/xi - b/xi
Busquemos la diferencia mínima entre dos m i distintos y llámenos m minΔ ( O(n log n) , por ejemplo, ordenando y luego comparando las diferencias entre m i e i + 1 para todos i)
Si modificamos b por ε, la nueva ecuación para m se convierte en:
mi,new = yi/xi - b/xi - ε/xi = mi,old - ε/xi
Como ε> 0 y x i > 0, todos los m se reducen, y todos se reducen en un máximo de ε / x min . Por lo tanto, si
ε/xmin < mminΔ, ie. ε < mminΔ*xmin
es cierto, entonces se garantizará que dos m i que anteriormente eran desiguales seguirán siendo desiguales.
Todo lo que queda es mostrar que si m 1, viejo = m 2, viejo , luego m 1, nuevo = / = m 2, nuevo . Como ambos m i se redujeron en una cantidad ε / x i , esto es equivalente a mostrar x 1 = / = x 2 . Si fueran iguales, entonces:
y1 = m1,oldx1 + b = m2,oldx2 + b = y2
Contradiciendo nuestra suposición de que todos los puntos son distintos. Por lo tanto, m 1, new = / = m 2, new y no hay dos puntos colineales con Q.
Recogí la idea de Moron y Andand y seguí formando un algoritmo O (n) determinista.
También asumí que los puntos son distintos yn es par (se cree que el algoritmo puede cambiarse de manera que también se admite n desigual con un punto en la línea divisoria).
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 obtener el punto con el 8vo mayor valor de x y el punto con el 9 ° mayor valor de 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 eso 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 <x a ), en el medio (x = x a ) y el del lado derecho (x> x a ). La idea ahora es contar los puntos en el lado izquierdo y calcular cuántos puntos del medio deben 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 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 necesito, 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 ahora son inútiles, porque solo están determinados por el valor xy pueden ser cualquiera de los puntos intermedios.
Queremos los 5 puntos del centro con el valor y más bajo en el lado izquierdo y el punto con el valor y más alto en el lado derecho. Usando de nuevo el algoritmo de selección, obtenemos el punto con el quinto valor y más grande y el punto con el sexto valor y más grande. Ambos puntos tendrán el valor de x igual a x a , 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 (b h ) entre la línea vertical en x a y la línea determinada por ese punto y Q. También necesitamos ese punto del lado derecho ( con ángulo a g ). El nuevo punto R está entre el punto con el ángulo inferior 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 para 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 convierta 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.
- obtener esos dos puntos P a (x a , y a ) y P b (x b , y b )
cuáles son las medianas basadas en los valores x> O(n) - si x a ! = x b puede detenerse aquí
porque una línea paralela del eje y entre esos dos puntos es el resultado> O(1) - obtener todos los puntos donde el valor de x es igual a x a
> O(n) - contar puntos con x valor menor que x a como c
> O(n) - obtener el punto más bajo P c basado en los valores y de los puntos de 3.
> O(n) - obtener el mayor punto P d en función de los valores y de los puntos de 3.
> O(n) - obtener el (n / 2-c) el punto más grande P e basado en los valores y de los puntos de 3.
> O(n) - también obtiene el siguiente punto más grande P f basado en los valores y de los puntos de 3.
> O(n) - crea un nuevo punto Q (x a , (y e + y f ) / 2) entre P e y P f
> O(1) - para todos los puntos P calculo
el ángulo a i entre P c , Q y P i y
el ángulo b i entre P d , Q y P i> O(n) - obtener el punto P g con el ángulo más bajo a g (con a g > 0 ° y a g <180 °)
> O(n) - obtener el punto P h con el ángulo más bajo b h (con b h > 0 ° y b h <180 °)
> O(n) - si no hay ningún P g o P h (todos los puntos tienen el mismo valor de x)
cree un nuevo punto R (x a +1, 0) en cualquier lugar pero con un valor de x diferente que x a
de lo contrario, si un g es menor que b h
crea un nuevo punto R ((x c + x g ) / 2, (y c + y g ) / 2) entre P c y P g
más
crea un nuevo punto R ((x d + x h ) / 2, (y d + y h ) / 2) entre P d y P h> O(1) - la línea determinada por Q y R divide los puntos
> O(1)
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.