He buscado en Google hasta que estoy azul en la cara, y a menos que me falta algo realmente obvio, no puedo encontrar ningún algoritmo para calcular el cuadro delimitador de un sector en 2D.Cuadro delimitador 2D de un sector?
Dado el punto central del círculo circundante, el radio y los ángulos de la extensión del sector, ¿cuál es el mejor algoritmo para calcular el rectángulo delimitador alineado con el eje de ese sector?
Ah sí. Lo entiendo. ¡Gracias! –
Voy a reformular la respuesta de yairchu para que quede más clara (para mí, de todos modos).
Ignore las coordenadas del centro por ahora y dibuje el círculo en el origen. Convéncete de lo siguiente:
Ahora tiene como máximo 4 + 1 + 2 puntos para encontrar. Encuentra el máximo y el mínimo de esas coordenadas para dibujar el rectángulo.
El rectángulo se traduce fácilmente al círculo original al agregar las coordenadas del centro del círculo original a las coordenadas del rectángulo.
+1 buena redacción (y razonamiento) :) – yairchu
+1 para ti también Glenn. Obtuve la esencia de la explicación de Yairchu, pero lo hiciste un poco más claro. Aclamaciones. –
En primer lugar, me disculpo si cometo errores al escribir pero el inglés no es mi primer idioma, ¡el español en realidad es!
Me enfrenté a este problema, y creo que encontré una solución eficiente.
En primer lugar vamos a ver una imagen de la situación
Así que tenemos una elipse (en realidad un círculo) y dos puntos (C, D) que indica nuestro sector. También tenemos el centro de nuestro círculo (B) y el ángulo del arco alpha.
Ahora, en este caso lo hice pasar por 360º en porpouse para ver si funcionaría.
Digamos alpha -> -251.1º (es negativa causa de su horario), permite transformarlo a un valor positivo 360º - 251.1º = 108.9º Ahora nuestro objetivo es encontrar el ángulo de la bisectriz de ese ángulo para que podamos encontrar el punto máximo de la caja de contorno (E en la imagen), de hecho, como habrás notado, la longitud del segmento BE es igual al radio del círculo, pero debemos tener el ángulo para obtener las coordenadas reales del punto E.
Así que 108.9º/2 -> 54.45º ahora tenemos el ángulo.
para encontrar las coordenadas de E usamos coordenadas polares por lo
x = r * Cos(theta)
y = r * Sin(theta)
tenemos r y theta por lo que podemos calcular x e y
en mi ejemplo r = 2.82 ... (en realidad es irational pero di los dos primeros dígitos decimales como una cuestión de facilidad)
sabemos que nuestra primera radios es 87.1º por lo theta habría 87.1 - 54.45º -> 32.65º
sabemos * theta * se 32.65º así que vamos a hacer algunos cálculos
x = 2.82 * Cos(32.65º) -> 2.37552
y = 2.82 * Sin(32.65º) -> 1.52213
Ahora tenemos que ajustar estos valores para el centro real del círculo de modo
x = x + centerX
y = y + centerY
En el ejemplo, el círculo se centra en (1.86, 4.24)
x -> 4.23552
y -> 5.76213
en esta etapa se debe utilizar algún cálculo. Sabemos que uno de los bordes del cuadro delimitador será una tangente del arco que pasa por el punto que acabamos de calcular, así que busquemos esa tangente (la línea roja).
Sabemos que la tangente pasa por nuestro punto (4.23, 5.76) ahora necesitamos una pendiente.
Como puede ver, la pendiente es la misma que la pendiente del rect que pasa a través de nuestros radios, así que tenemos que encontrar esa pendiente.
Para hacer eso necesitamos obtener las coordenadas de nuestros radios (una conversión rápida a coordenadas cartesianas desde coordenadas polares).
x = r * Cos(theta)
y = r * Sin(theta)
Así
p0 = (centerX + 2.82 * Cos(87.1º), centerY + 2.82 * Sin(87.1º))
p1 = (centerX + 2.82 * Cos(-21.8º), centerY + 2.82 * Sin(-21.8º))
(21.8º es el ángulo medido en sentido horario desde el eje horizontal a los radios que está debajo de ella y por lo tanto lo puse negativo)
p0 (2, 7.06)
p1 (4.48, 3.19)
ahora vamos a encontrar la pendiente:
m = (y - y0)/(x - x0)
...
m = (3.19 - 7.06)/(4.48-2) = -3.87/2.48 = -1.56048
...
m = -1.56
tener la pendiente que necesitamos para calcular la ecuación de la tangente, básicamente es un rect con una pendiente ya conocido (m = -1.56) que pasa a través de un punto ya saben (E -> (4.23, 5.76))
Así que tenemos Y = mx + b donde m = -1.56, y = 5.76 y x = 4.23b debe haber por lo
b = 5.76 - (-1.56) * 4.23 = 12.36
Ahora tenemos la ecuación completa para nuestra tangente ->Y = -1.56X + 12.36 Todos debemos hacer saber es los puntos del proyecto C y D sobre eso rect.
Necesitamos las ecuaciones de las rectas CH y DI así que vamos a calcular 'em
Vamos a empezar con CH:
sabemos (a partir de la ecuación de la tanget) que nuestro vector de dirección es (1.56, 1)
tenemos que encontrar un rect que pasa por el punto C -> (2, 7.06)
(x - 2)/1.56 = (y - 7.06)/1
Haciendo un poco de álgebra ->y = 0.64x + 5.78
Sabemos que tiene la ecuación de la rect CH debemos calcular el punto H.
tenemos que resolver un sistema lineal de la siguiente manera
y = -1.56x + 12.36
y = 1.56x + 5.78
La solución de este vamos a encontrar el punto H (3, 7.69)
que tenemos que hacer lo mismo con el rect DI por lo que vamos a hacerlo
Nuestro vector de dirección es (1.56, 1) una vez más
D -> (4.48, 3.19)
(x - 4.48)/1.56 = (y -3.19)/1
Haciendo un poco de álgebra ->y = 0.64x + 0.32
Permite resolver el sistema lineal
y = -1.56x + 12.36
y = 0.64x + 0.32
I (5.47, 3.82)
En esta etapa ya tenemos los cuatro puntos que hacen que nuestro cuadro delimitador ->C, H, D , I
En caso de que don 't saber o recordar cómo resolver un sistema lineal en un lenguaje de programación, le daré un pequeño ejemplo
Es álgebra pura
Supongamos que tenemos el siguiente sistema
Ax + By = C
Dx + Ey = F
continuación
Dx = F - Ey
x = (F - Ey)/D
x = F/D - (E/D)y
sustitución en la otra ecuación
A(F/D - (E/D)y) + By = C
AF/D - (AE/D)y + By = C
(AE/D)y + By = C - AF/D
y(-AE/D + B) = C - AF/D
y = (C - AF/D)/(-AE/D + B)
= ((CD - AF)/D)/((-AE + BD)/D))
por lo
y = (CD - AF)/(BD - AE)
y para x hacemos lo mismo
Dx = F - Ey
Dx - F = -Ey
Ey = F - Dx
y = F/E - (D/E)x
sustitución en la otra ecuación
Ax + B(F/E - (D/E)x) = C
Ax + (BF/E - (DB/E)x) = C
Ax - (DB/E)x = C - BF/E
x (A-(DB/E)) = C - BF/E
x = (C - BF/E)/(A-(DB/E))
= ((CE - BF)/E)/((AE-DB)/E)
x = (CE - BF)/(AE - DB)
Me disculpo por el alcance de mi respuesta, pero destinado a ser lo más claro posible y por lo tanto, lo hice casi paso a paso.
Steve, ¿qué hay de http://stackoverflow.com/questions/622140/calculate-bounding-box-coordinates-from-a-rotated-rectangle-picture-inside? –
@Matt: no es exactamente lo que estaba buscando, pero me dio algunas ideas. –