hilo de 4 años, pero casualmente tropecé al buscar mi problema en Google.
Tengo un problema como este en una aplicación de CV actual. Se me ocurrió una solución simple y algo torpe para encontrar el más grande. No es exactamente lo mismo, porque maximizo el área del rectángulo sin una relación fija de lados.
No sé si mis soluciones encuentran el óptimo o si funciona en todos los casos. También creo que debería haber una manera más eficiente, por lo que espero su opinión.
En primer lugar, asumir un conjunto de 4 puntos que forman nuestro cuadrilátero (convexo):
x y
P1 -2 -5
P2 1 7
P3 4 5
P4 3 -2
Para este procedimiento el punto más a la izquierda es P1, los siguientes puntos se numeran hacia la derecha. Se ve así:
A continuación, crear las funciones lineal entre los puntos. Para cada función, debemos conocer la pendiente k y la distancia desde 0: d. k es simplemente la diferencia en Y de los dos puntos dividido por la diferencia en X. d se puede calcular resolviendo la función lineal a d. Entonces tenemos
k=dy/dx
d=y1-k*x1
También desearemos las funciones inversas.
k_inv = 1/k
d_inv = -d/k
entonces se crea la función y la función inversa para cada lado del cuadrilátero
k d k d
p1p2 4 3 p1p2_inv 0.25 -0.75
p2p3 -0.67 7.67 p2p3_inv -1.5 11.5
p3p4 7 -23 p3p4_inv 0.14 3.29
p4p1 0.6 -3.8 p4p1_inv 1.67 6.33
Si tuviéramos líneas completamente horizontales o verticales que terminarían con un DIV/0 en una de las funciones o funciones inversas, por lo tanto, necesitaríamos manejar este caso por separado.
Ahora pasamos por todas las esquinas que están rodeadas por dos funciones que tienen una k con una pendiente con un signo diferente. En nuestro caso, eso sería P2 y P3.
Comenzamos en P2 e iteramos a través de los valores de y entre P2 y el más alto de P1 y P3 con un tamaño de paso apropiado y usamos las funciones inversas para calcular la distancia entre las funciones en dirección horizontal. Esto nos daría un lado del rectángulo
a=p2p3_inv(y)-p1p2_inv(y)
en los dos x valores x = p2p3_inv (y) y x = p1p2_inv (y) que a continuación, calcular la diferencia en y a las dos funciones opuestas y tomamos la distancia a nuestra posición y actual como candidato para el segundo lado de nuestro rectángulo.
b_candidate_1 = y-p4p1(p2p3_inv(y))
b_candidate_2 = y-p4p1(p1p2_inv(y))
b_candidate_3 = y-P3p4(p2p3_inv(y))
b_candidate_4 = y-P3p4(p1p2_inv(y))
El menor de los cuatro parámetros sería la solución para el lado b. El área obviamente se convierte en a * b.
Hice un ejemplo rápido en Excel para demostrar:
la mínima b aquí es de 6,9, por lo que la esquina superior derecha de la solución está en p2p3 y el rectángulo se extiende a en horizontal y b en dirección vertical a la izquierda e inferior, respectivamente.
Los cuatro puntos del rectángulo son por lo tanto
Rect x y
R1 0.65 -1.3
R2 0.65 5.6
R3 3.1 5.6
R4 3.1 -1.3
voy a tener que poner esto en código C++ y a realizar algunas pruebas para ver si la solución se generaliza o si esto era sólo "suerte".
Creo que también debería ser posible sustituir aa y b en A = a * b por las funciones y ponerlo en una fórmula lineal que debe maximizarse bajo la condición de que p1p2 solo se defina entre P1 y P2, etc. ...
Re. el círculo: puede tratar el cuadrilátero como un triángulo de corte. Es decir. para cada borde del cuadrángulo, haga que los bordes adyacentes sean más largos hasta que se encuentren. Inscribe un círculo en tu nuevo triángulo. Verifica si encaja en tu cuadrilátero original. El círculo más grande así obtenido debería ser el óptimo. Obviamente tendrá que cuidar los cuadrángulos con bordes paralelos por separado. – toochin
Puede tener dificultades con cualquier cuadrilátero arbitrario si permite quads convexos y aquellos cuyos segmentos se superponen. ¿Te refieres a cualquier cuadrilátero arbitrario * convexo *? –
¿Se puede rotar el rectángulo, o tiene que ser paralelo al "horizonte"? – kohlehydrat