algorithm - que - Dadas dos líneas en un avión, ¿cómo encontrar los puntos enteros más cercanos a su intersección?

youtube google (18)

No puedo resolverlo:

Le dan 8 enteros:

A, B, C representa una línea en un plano con la ecuación A x + B y = C
a, b, c representando otra línea
x, y representa un punto en un avión

Las dos líneas no son paralelas, por lo tanto, divide el plano en 4 piezas. El punto (x, y) se encuentra dentro de una de estas piezas.

Problema:
Escribe un algoritmo rápido que encuentre un punto con coordenadas enteras en la misma pieza que (x, y) que está más cerca del punto de cruce de las dos líneas dadas.

Nota:
Esto no es una tarea, esta es una vieja tarea tipo Euler que no tengo ni idea de cómo acercarme.

Actualización: puede suponer que los 8 números en la entrada son enteros con signo de 32 bits. Pero no puede suponer que la solución será de 32 bits.

Actualización 2: caso difícil - cuando las líneas son casi paralelas - es el corazón del problema

Actualización 3: el autor del problema afirma que la solución es el algoritmo lineal O (n). Donde n es el tamaño de la entrada (en bits). Es decir: n = log (A) + log (B) + ... + log (y)
Pero todavía no puedo resolverlo.

Indique las complejidades de los algoritmos publicados (incluso si son exponenciales).

Aquí hay una idea parcial que puede ser útil para obtener una solución completa. Imagina que las dos líneas están muy, muy cerca la una de la otra. Entonces, cualquier solución integral entre ellos también sería un punto integral que está muy cerca de cada línea. Intentemos encontrar puntos integrales cercanos a la línea ax+by=c . Como y = (c - ax)/b , necesitamos tener y muy cerca de un entero, por lo que b divide aproximadamente c-ax . En otras palabras, c-ax+D == 0 mod b para un entero pequeño D

Podemos resolver c-ax+D == 0 mod b para x : x = a^-1(c+D) mod b (a ^ -1 existirá si a y b son relativamente primos, no estoy seguro de si ese es el caso aquí).

Entonces el algoritmo es evaluar x = a^-1(c+D) mod b para D = 0, + 1, -1, + 2, -2, ... y prueba los x resultantes para ver si funcionan. Si hay puntos integrales cercanos a la intersección de las dos líneas, deberían aparecer temprano en esta iteración. Por supuesto, es posible que deba alcanzar D=b-1 en el peor de los casos ...

Bueno, depende de lo que se considere lo suficientemente rápido.

Vamos a nombrar el punto [x, y] P. También voy a llamar a puntos con coordenadas enteras ''puntos enteros''.

Algoritmo que propongo:

Encuentra el punto Q donde se cruzan estas dos líneas. (Q = [x_q, y_q])
Obtenga la función de la línea entre Q y P, y = f (x) o inversa x = g (y);
Determine si QP es más vertical u horizontal según su ángulo. Digamos que es vertical para simplificar la siguiente solución (si es horizontal, los ejes simplemente se invertirían y donde escribo x sería y y viceversa).
Tome la primera coordenada entera y_1 avanzamos a lo largo de la línea de Q a P.
Calcula la segunda coordenada de ese punto: x_1 = f (y_1). Ese punto está en nuestro segmento.
Encuentre si los puntos enteros circundantes con coordenadas [piso (x_1); y_1] y [piso (x_1 + 1); y1] están en el segmento que nos interesa.

6.1 En caso afirmativo, iteramos a través de la línea horizontal x_3 = f (y_1) para encontrar el punto entero que todavía está en nuestro segmento y tiene (x_3-x_q) -> min. Ese punto es nuestra respuesta.

6.2 De lo contrario, incremente y_1 en uno y repita desde el paso 5.

Como algunos otros han señalado, este es un problema en la programación lineal entera (también conocida como desigualdades diofánticas lineales).

Vea esta referencia: Algoritmo ABS para resolver una clase de desigualdades diophantinas lineales y problemas de LP enteros . Los autores afirman ser capaces de resolver sistemas como

max (c ^T x) para Ax≤b, x∈Z ⁿ , donde c∈Z ⁿ , b∈Z ^m , A∈Z ^{m, n} , m≤n.

En particular, al establecer m = 2, n = 2, obtenemos el problema de encontrar

max (c ^T x) para Ax ≤ b, x∈Z ² , donde c∈Z ² , b∈Z ² , A∈Z ^2,2 .

Aquí, A es una matriz de 2x2, yb, cyx son vectores de columna de 2x1.

El problema planteado por el PO puede reformularse de esta manera (si se me solicita, intentaré deletrearlo con más detalle).

El algoritmo de matriz presentado en el documento puede parecer peludo para los no iniciados, pero los algoritmos de la matriz son así. No es que lo haya visto línea por línea, o lo entiendo, pero parece bastante manso en comparación con algunas cosas que he visto.

Esto parece ser algo en la clase general de métodos ABS , que parece estar ganando tracción en varios dominios problemáticos.

La última oración de la sección 2 del documento también se refiere a otro método de solución.

Como señala @Alan, mientras que el problema general de ILP es NP-Hard, el problema aquí indicado puede no serlo. No estoy seguro de por qué es así, pero puede ser porque la matriz A es 2x2 (en lugar de nx2), y porque las restricciones se pueden expresar como enteros.

Edit1 : la complejidad del algoritmo parece ser O (1) (Parece ser O (d), donde d es la dimensión del enrejado. En este caso, d = 2). Mi sorpresa al respecto es O (!!) y entender e implementar esto sigue siendo O (??), aunque lo he repasado varias veces y parece más sencillo de lo que pensaba.

Creo que hay 3 piezas para esto.

calcule la intersección de las 2 líneas y mantenga las coordenadas X e Y de ese punto
encuentre la sección en la que se encuentra el punto dado. Esto debería ser bastante fácil, porque tiene la pendiente de las 2 líneas y la pendiente de la línea creada por el punto dado y el punto de intersección. m_line1 , m_line2 y m_intersect . Si m_intersect Hay una fórmula para descubrir la sección que usa estos valores y la ubicación del punto dado.
encuentra el entero más cercano. También hay un cálculo sencillo de esto una vez que conozca los valores del n. ° 1 anterior y las pendientes del n. ° 2. Puedes usar fuerza bruta, pero hay una elegante solución matemática.

Estos son los pasos que tomé, al menos.

Actualizado para agregar más sustancia

OK, comenzaremos con una discusión sobre el # 2.

Si calcula la pendiente del punto dado y el punto de intersección, entonces llega a m_intersection . Esta es la pendiente de una línea que pasa por el punto de intersección. Supongamos que m_line1 es la mayor de las 2 pendientes, de modo que la línea 1 está "arriba" de la línea 2 a medida que x aumenta después de la intersección. Hace que sea más fácil pensar en los nombres de las secciones. Llamaremos a la sección A la sección dada por la astilla entre la línea1 y la línea2 para x más grande que la coordenada de intersección x, y luego nombraremos las otras 3 secciones en el sentido de las agujas del reloj, de modo que A y C estén opuestas entre sí.

Si m_intersection está entre m_line1 y m_lin2 , entonces debe estar en una de las 2 secciones A o C. ¿Qué sección es una prueba simple del valor de la coordenada x contra la coordenada x de la intersección? Definimos A como la sección con mayor valor. Se puede hacer un cálculo similar si la pendiente está fuera de m_line1 o m_line2 .

Esto le da la sección en la que se basa su punto. Todo lo que hizo fue calcular 1 intersección (5 multiplicaciones, 2 divisiones y un puñado de sustracciones si lo hace de la manera tradicional), 3 pendientes y luego un par de comparaciones enteras.

Editar # 3 - ¡De vuelta por (no) demanda popular!

Así que aquí es cómo calculé # 3, el punto entero más cercano a la intersección. Puede que no sea el mejor, pero utiliza la búsqueda binaria, por lo que es O (log n) donde n está relacionado con el inverso de la diferencia de las pendientes de la línea. Cuanto más cerca están juntos, más grande es n.

Primero, toma la diferencia entre las pendientes de las dos líneas. Digamos que es 1/8. Esto significa que desde el punto de intersección, debe salir 8 unidades a lo largo del eje x antes de que se le garantice que hay un entero entero en el eje y entre las dos líneas (puede estar en una de las líneas). Ahora, si la intersección en sí no está en una coordenada x entera, entonces tendrá que seguir adelante para garantizar que su punto de partida se encuentre en una coordenada x entera, pero está delimitada. Si la intersección está en x = 1.2, entonces en el ejemplo anterior, en el peor comenzaría en x = 41, luego bajaría ~ 5 unidades a lo largo del eje y. Elija el cielo raso o el piso del valor y que obtiene. No es terriblemente crítico.

Ahora que tiene un punto de partida, el punto más cercano se puede aproximar mediante la búsqueda binaria. Su nuevo segmento de línea se encuentra entre la intersección y el punto de inicio, y sus unidades de movimiento son múltiplos de la pendiente de ese segmento de línea. Calcule el punto medio del segmento de línea y vea si se encuentra entre las dos líneas. Suma o resta 1 si no es un golpe directo, y si alguno de esos golpes, reduce la distancia restante a la mitad y vuelve a hacerlo. De lo contrario, busque la otra mitad del segmento.

Si no tiene una diferencia de pendiente <1, creo que el problema puede ser más simple (fuerza bruta el espacio alrededor de la intersección). Pero es solo un caso especial de la búsqueda anterior, donde no necesita ir tan lejos para encontrar un punto de partida.

Cuanto más pienso en esto, más parece que se convierte en Integer Linear Programming, que es NP-completa en el caso general. http://en.wikipedia.org/wiki/Linear_programming#Integer_unknowns

Mi línea de razonamiento comenzó como la respuesta de TheMachineCharmer hasta que llegué a ese punto. El problema es que el enfoque de examinar las líneas a lo largo del cielo raso / piso del punto de intersección solo funciona si la sección está alineada con el eje vertical u horizontal a través del punto de intersección. Lo más probable es que la sección delgada esté inclinada en algún ángulo alejado del eje y que los vecinos del cielo raso / piso no se crucen con la sección en coordenadas enteras.

En ese punto, estamos buscando una combinación entera de vectores de unidades naturales que satisfaga las desigualdades que definen nuestra sección seleccionada y también minimiza la distancia al punto de intersección. Para mí, eso parece un problema de programación lineal entero.

Hay casos especiales de programación lineal entera que son más fáciles que NP-hard y este problema podría ser uno de ellos, ya que parece ser más limitado que el caso de programación lineal general. El artículo de Wikipedia vincula a algunos métodos, pero está más allá de mi nivel de matemáticas para postularse.

El problema de verificar si un punto es parte de un cono matemático es bastante simple. Dado 2 vectores, v , w , cualquier punto en el cono definido por ( v , w ) estará en la forma: z = a *** v ** + b *** w **, donde a, b> = 0. Nota, para que esto funcione, tendrás que mover a Origo a la intersección de las 2 líneas. Como no podemos suponer la precisión finita de la intersección, tendrá que hacer cálculos en coma flotante y decidir si algo está lo suficientemente cerca de lo que desea.

Encuentre vectores que definan los 4 conos (hay infinitos de ellos, solo necesitamos 2 para cada cono), que están definidos por las 2 líneas.
Averigüe qué cono contiene nuestro punto, llame a ese cono para C.
Tome los 2 vectores que definen C , y encuentre el vector mediano (el vector que dividiría C en 2 conos idénticos), llámelo m .
Ahora es el momento de iniciar el ciclo. Por simplicidad, voy a suponer que nos limitamos a n bits en los ejes xey. Tenga en cuenta que necesitará un número entero mayor que n bits para la longitud de m . Ahora haga una búsqueda binaria a lo largo de m , y revise los 2 anillos cada vez (sospecho que 1 timbre será suficiente). Cuando haya encontrado la longitud más pequeña que contiene puntos C , verifique cuáles de esos puntos son los más cercanos.

El peor caso de crecimiento sería O (log (sqrt (2 * n ^ 2)), donde n es la longitud que usamos para representar el eje xey.

Es posible hacer una "búsqueda binaria inversa" por así decirlo, si no conoce la longitud de * m . Simplemente siga doblando la longitud hasta que encuentre puntos en C. Entonces sabes 2 puntos en m y puedes hacer una búsqueda binaria entre ellos.

El principal problema con todo esto es la precisión, así que ten esto en cuenta. Las formas alternativas de seguir podrían incluir los 2 semiplanos que forman un cono. Cada cono de arriba está definido por la intersección de 2 semiplanos, y es posible que verifique si un punto es miembro de un medio plano es bastante simple, no estoy seguro.

Editar: de hecho es mucho más fácil con los medios planos, las 2 líneas dividen R ^ 2 en 2 medios planos cada uno, esto da las 4 combinaciones que serían los 4 conos. Entonces, cada vez que desee verificar si un punto es miembro de un cono, debe verificar si es un miembro de los 2 semiplanos que conforman ese cono en particular. Cómo hacerlo se explican aquí:

http://www.mathsteacher.com.au/year9/ch04_linear_graphs/07_half/planes.htm

and would be easier than moving Origo and fiddling around with precision. Replacing the method of checking membership and keeping everything else the same, you arrive at the same growth.

En realidad, puede ser posible resolver esto con un algoritmo modificado de dibujo de líneas de Bresenham. Por lo general, se usa para realizar la conversión de escaneo de líneas, y solo requiere incrementos de algún paso dentro de un ciclo si conoce los puntos finales de la línea.

Una vez que haya determinado en qué sector se encuentra el punto, mueva el origen a la intersección manteniendo la nota del error no entero. Calcula la pendiente de la línea desde la intersección hasta la línea inferior, luego haz una normal a la horizontal en un valor entero x (si la pendiente es pequeña) o una normal desde la y (la pendiente es alta) y encuentra dónde se cruza con el otro eje y un punto entero.

Debería poder verificar cada paso entero en un eje para determinar si el punto que está probando está por encima o entre sus dos líneas (cree un nuevo vector en ese punto desde la intersección y determine la pendiente). Si el punto está arriba, incremente su paso entero. Como está probando desde la más pequeña diferencia de gradiente de una de las líneas, debería ser O (n). En el algoritmo de Bresenhams, hay 8 sectores y no solo 4.

Estaba haciendo algo similar cuando tuve que encontrar un punto para etiquetar un polígono.

El resultado final fue de 70000 polígonos en 5 segundos en el pentium 3 en Autocad. Eso es alrededor de 3 segundos si excluye Autocad.

Primero necesitas encontrar un punto de intersección. A continuación, debe encontrar dónde se encuentra su punto (x, y) y dibujar una línea horizontal o vertical a través de él, de modo que sus 2 líneas (A, B, C) y (a, b, c) y una nueva horizontal / línea verical forma un triángulo. Cómo encontrar si es una línea vertical u horizontal: Dibuje líneas horizontales y verticales a través de su punto (x, y) y luego verifique: -para horizontal: - si las intersecciones para la línea A, B, C y su línea horizontal y línea a, b, c hacen que esta ecuación funcione (intersección con A, B, C) .x <x <(intersección con a, b, c) .x, entonces conoces tu interior. (Puedes cambiar A, B, C y a, b, c, siempre que x esté dentro. - similar para y, solo busca y y no x.

Entonces ahora tienes un triángulo y sabes dónde está (izquierda, derecha, arriba, abajo). por ejemplo, si se trata de un triángulo rectángulo (como el gráfico anterior). Tomas la x del punto de intersección y la cecas (si está a la izquierda la piso) ... similar a la coordenada y si tienes un triángulo arriba / abajo. Luego dibuja una línea de exploración a través de ella, que es paralela a su línea de exploración a través de su punto (x, y) y verifica si tiene un punto dentro de las intersecciones (similar a x <x <x arriba, pero con una nueva línea). Si no tiene un número entero dentro, entonces tiene que mover su punto de ceil más lejos del punto de intersección. Debe calcular un ''paso'' apropiado según el ángulo entre sus dos líneas (si las líneas son paralelas y muy cercanas entre sí, entonces el ángulo será pequeño, por lo que debe aumentar el paso, si el ángulo es ancho, paso pequeño es requerido.

Cuando encuentras un punto, puede que no sea el más cercano. Así que tendrás que hacer una bisección entre el último punto no bueno (cuando estás aumentando el paso) y el último punto (donde encontraste un número entero).

Este problema entra en la categoría de Optimización Convexa Integer .

Presentamos aquí una forma matemática para abordar el problema. No espero que realmente lo uses: se requieren muchas técnicas complicadas, y otros enfoques algorítmicos (como "buscar" el punto apropiado) probablemente funcionarán bien. Sin embargo, el interés se ha expresado en la solución "verdadera", así que aquí está.

Se puede resolver en tres etapas:

Primero, determine en qué lado de cada línea estará la respuesta, como lo ilustra la respuesta de TheMachineCharmer.
Una vez que se sabe, el problema puede reescribirse como un problema de optimización convexa (ver Wikipedia para más detalles). La función a optimizar es minimizar (x - x0) ^ 2 + (y - y0) ^ 2, con x0 y y0 las coordenadas de la intersección de las dos líneas. Las dos líneas se convierten en una desigualdad lineal, por ejemplo, "x + y> = 0", formando la región convexa en la que se puede encontrar la respuesta. Notaré que la solución será (x = x0, y = y0) - qué usted necesita a partir de esta etapa una forma de expresar el problema, análoga a un cuadro factible para el método símplex .
En tercer lugar, se puede encontrar una solución entera añadiendo repetidamente cuts para restringir aún más la región factible hasta que la solución al problema de optimización convexa sea integral. Esta etapa puede tomar muchas iteraciones en el caso general, pero mirando el problema presentado, y en particular la naturaleza bidimensional de la misma, creo que se resolverá con un máximo de dos cortes.

Investigué el problema en el pasado (tanto porque es divertido como porque encontré algo relacionado en un lugar donde trabajé).

Que yo sepa, no existe un algoritmo eficiente (FPTIME) para este problema.

La única solución conocida (para mí) es enumerar básicamente las coordenadas enteras (comenzando desde alrededor de la intersección) hasta que encuentre la que desea. Esto, por supuesto, no es para nada eficiente cuando el ángulo entre las dos líneas es muy pequeño. Puede hacer una poda para mejorar la eficiencia y, cuando la pendiente es pequeña, la eficiencia es decente.

Se sabe que una generalización de esto (ILP - programación lineal entera) es NP-completa.

Muestro aquí cómo se puede resolver una instancia "difícil" de este problema. Creo que este método puede generalizarse. He puesto otra instancia más simple en los comentarios de la publicación original.

Considera las dos líneas:

10000019 * X - 10000015 * Y + 909093 >= 0 (L1) -10000022 * X + 10000018 * Y + 1428574 >= 0 (L2) A = 10000019, B = -10000015, C = -909093

El punto de intersección es H:

Hx = -5844176948071/3, Hy = -5844179285738/3

Para un punto M (X, Y), la distancia cuadrada HM ^ 2 es:

HM^2 = (9*X^2+35065061688426*X +68308835724213587680825685 +9*Y^2+35065075714428*Y)/9

g = gcd (A, B) = 1: la ecuación de L1 A*X+B*Y+909093 puede tomar cualquier valor entero.

Los coeficientes de Bezout, U = 2500004 y V = 2500005 verifican:

A * U + B * V = 1

Ahora reescribimos el problema en la base "dual" (K, T) definida por:

X = T*U - K*B Y = T*V + K*A

Después de la sustitución, obtenemos:

T+909093 >= 0 2*T+12*K+1428574 >= 0 minimize 112500405000369*T^2 +900003150002790*T*K +1800006120005274*K^2 +175325659092760325844*T +701302566240903900522*K +Constant

Después de traducir más (primero en T, luego en K para minimizar la constante en la segunda ecuación), T = T1-909093, K = K1 + 32468:

T1 >= 0 2*T1+4+12*K1 >= 0 minimize 112500405000369*T1^2 +300001050000930*T1 +900003150002790*T1*K1 +1200004080003516*K1 +1800006120005274*K1^2 +Constant

El algoritmo que propuse es hacer un ciclo en T1. En realidad, no necesitamos hacer un bucle aquí, ya que el mejor resultado viene dado por T1 = K1 = 0, que corresponde a:

X = -1948055649352, Y = -1948056428573

Mi publicación inicial a continuación.

Aquí hay otra idea de algoritmo. Puede funcionar, pero no lo implementé ...

Con el cambio apropiado de signos para que coincida con la posición de (x, y), el problema puede escribirse:

A*X+B*Y>=C (line D) a*X+b*Y>=c (line d) minimize the distance between M(X,Y) and H, the intersection point A*b != a*B (intersection is defined) A,B,C,a,b,c,X,Y all integers

El conjunto de todos los valores alcanzados por (A X + B Y) es el conjunto de todos los múltiplos de g = gcd (A, B), y existen enteros (u, v) tales que A u + B v = g (Bezout teorema). Desde un punto con coordenadas enteras (X0, Y0), todos los puntos con coordenadas enteras y el mismo valor de A X + B Y son (X0-K B / g, Y0 + K A / g), para todos los enteros K.

Para resolver el problema, podemos hacer un bucle en líneas paralelas a D a una distancia creciente desde H, y que contiene puntos con coordenadas enteras.

Calcule g, u, v, y H (las coordenadas de H probablemente no sean necesarias, solo necesitamos los coeficientes de la forma cuadrática correspondiente a la distancia).
T0 = ceil (C / g)
Loop de T = T0
a. Encuentre K el entero más pequeño (o más grande, según el signo de un B-b A) que verifique a * (T u-K B / g) + b * (T v + K A / g)> = c
segundo. Mantener el punto (T u-K B / g, T v + K A / g) si está más cerca de H
do. Salga del lazo cuando (T-T0) corresponde a una distancia de D mayor que el mejor resultado hasta el momento; de lo contrario, continúe con T + = 1

Ustedes están perdiendo el punto! jaja, lo siento, no pude resistir.

Oye, imaginemos una situación un poco más simple.

Tienes una línea que emana del origen formando un ángulo de menos de 90 grados con el eje x. Encuentra el punto entero más cercano.

El problema con solo buscar puntos de celosía hasta que llegue a uno que está en el cuadrante que queremos es que uno no sabe qué tan lejos debe buscar. En el caso de un ángulo muy, muy agudo, podríamos considerar un bazillón de puntos antes de llegar a uno que está en nuestra región.

Solución:

Resolver: (Slope of Line) * Delta(x) = 1 .

es decir, Delta(x) = 1/(Slope of Line) , es donde comenzamos a buscar. Sujeto a la restricción Delta(x) > 1 .

En otras palabras, vamos lo suficientemente lejos como para que haya habido al menos una diferencia entera entre las coordenadas xey.

En nuestro problema, tendríamos que transformarnos adecuadamente y ajustar los números para obtener un rango de error apropiado. Delta(x) >= 2 , Delta(x) = 2/(Slope of Line) Creo que lo haré fuera de mi cabeza, pero no tengo un lápiz.

¿No?

texto alternativo http://imagebin.ca/img/yhFOHb.png

Diagram

Después de encontrar la intersección de las líneas L1:Ax+By=C y L2:ax+by=c es decir, el punto A(x1,y1) .

Defina dos líneas más y = ceil(y1) y = floor(y1) paralelo al X-axis y encuentre su intersección con L1 y L2 es decir, los puntos B(x2,y2) y C(x3,y3) .

Entonces el punto que requieres es D o E lo que esté más cerca del punto A Un procedimiento similar se aplica a otras partes del avión.

D ( ceil(x2), ceil(y1) ) E ( ceil(x3), floor(y1) )

Here is a linear time (ie, O(# bits of A, B, C, etc.), assuming the bits fit into O(1) words of memory) solution using line-side tests and binary search:

Suppose wlog that B != 0 (else we swap A with a, B with b, and C with c). Perform a line-side test to see which side of line (A, B, C) the point is on. Assume wlog that the point is below (or on) the line.

Note that for an arbitrary x-coordinate x'', we can compute the smallest y'' such that (x'', y'') is above the line (A, B, C) in O(1) time via y'' = (C - A * x'') / B.

Now, assume wlog that the input point (x, y) is to the right of (a, b, c), or below in the case of a horizontal line. We can then perform a line-side test of (x'', y'') relative to line (a, b, c) and determine whether we need to increase x'' or decrease x'' to find the minimum x'' such that (x'', y'') falls on the correct side of (a, b, c).

Binary searching for this point takes at most O(w) time where w is the number of bits in A, B, etc. Note that because the input coordinates x and y each fit in an integer, so will the return value. Even if x and y were not necessarily within these bounds and the lines were nearly parallel, a suitable x will be found within O(w) time because the difference in slopes is A / B - a / b = (Ab - aB) / Bb <= 1 / 2^(2w), so the x-coordinate of the answer will fit within O(1) words of memory. We still need to find the y-coordinate of the answer, which can also be found via binary search.

I suspect this is a mathematical optimization problem that can be solved with a Lagrange multiplier...

My proposal is this. Assume that the section of the plane which contains our target point spans entirely in lower left quadrant, looking from the cross point of two lines (other quadrants are analogous, and case when section of plane spans more than one quadrant will be considered later).

Let the two given lines be l ₁ and l ₂ (l ₁ is ''less steep'' than l ₂ )

find X = (a, b), the cross point of l ₁ and l ₂ .
let k = 0
let v _k be vertical line with the x coordinate x _k = floor(ak)
find cross points of v _k with l ₁ and l ₂ (points V ₁ = (x ₁ , y ₁ ), V ₂ = (x ₂ , y ₂ )).
if floor(y ₁ ) != floor(y ₂ ), target point is (x ₁ , floor(y ₁ )) END.
if floor(y ₁ ) == floor(y ₂ ), increment k and go to step 3.

Since l ₁ and l ₂ are not parallel, abs(y ₁ - y ₂ ) must grow with k. When abs(y ₁ - y ₂ ) gets larger than 1, algorithm will surely stop (it might stop earlier though).

Now let us consider the (easy) case when our section of plane spans more than one quadrant, looking from the cross point of two lines (it may span two or three quadrants).

find X = (a, b), the cross point of l ₁ and l ₂ .
find A, the set of four closest points to X that have integer coordinates
find B, the set of points from A which are in the target section of the plane.
punto de B que está más cerca del punto de cruce de l ₁ y l ₂ es el punto de destino

(Este caso se ejecuta en tiempo constante).

Of those four pieces of the plane, one is to the left of both lines, one is to the right of both lines, one is to the right of one and to the left of the other line, and the last one is to the left of one and to the right of the other line. It''s easier to see if you draw it.

The relative position of a point from a line depends on the result of this determinant:

[1 p1x p1y; 1 p2x p2y; 1 p3x p3y], where p1 and p2 are two arbitrary points in the line and p3 is the given point.

If it equals zero, the point is in the line, if it''s greater of lower than zero, it''s to a side, the side depends on the relative position of p1 and p2 in the line and what you consider left and right on the plane.

The problem is choosing two points that follow the same criteria in both lines, so that results are consistent, maybe p1 always has lower value of x coordinate than p2 (y coordinate if the line is vertical).

When you have both points for each line, calculate both determinants and you are done.

EDITAR

Ups, this solves the problem partially. Anyway you can calculate the side the XY point is in with this, calculate the intersection, and then calucate the relative position of all valid points (floor(x), floor(y)), (floor(x), ciel(y)), ...

line 1 is defined as y1 = m1 * x1 + b1. line 2 is defined as y2 = m2 * x2 + b2.

m1, m2, b1, b2 are all known values [constants].

make sure m1 <> m2.

find point of intersection, ie where y1 == y2 and x1 == x2 , defined as (X,Y).

Y = ((m1*b2)/m2)/(m1/m2-1)

X = (Y-b1)/m1

the nearest point can be found by rounding X and Y to the nearest integers. you decide what to do with .5