Autor Tema: Puntos con coordenadas enteras dentro de un triángulo

0 Usuarios y 1 Visitante están viendo este tema.

18 Septiembre, 2019, 09:06 pm
Leído 444 veces

vandermonde

  • Nuevo Usuario
  • Mensajes: 15
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Supongamos que tenemos un triángulo definido por las coordenadas de sus tres vértices A, B, C. Busco un algoritmo que liste, de forma general, todos los puntos de coordenadas enteras P1, P2,...,Pn que estén en el interior o en la frontera del triángulo.

Para rizar el rizo, supongamos que 2 de los vértices del triángulo dependen de un parámetro: A, B(p), C(p). Entonces el algoritmo daría una serie de puntos también dependientes de dicho parámetro: P1(p), P2(p),...,Pm(p).

Agradezco cualquier pista o sugerencia.

Saludos.

19 Septiembre, 2019, 09:59 am
Respuesta #1

Ignacio Larrosa

  • Moderador Global
  • Mensajes: 2,270
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Actividades con GeoGebra
Supongamos que tenemos un triángulo definido por las coordenadas de sus tres vértices A, B, C. Busco un algoritmo que liste, de forma general, todos los puntos de coordenadas enteras P1, P2,...,Pn que estén en el interior o en la frontera del triángulo.

Lo único que se me ocurre es inscribir el triángulo en un rectángulo de lados paralelos a los ejes, definido por los mínimos y máximos de las coordenadas \( x\textrm{ e }y \) de los vértices y, mediante un doble bucle, comprobar si cada uno de los puntos que contiene están en el triángulo o su frontera.

El test puede consistir en comprobar si los tres ángulos \( \left({\overrightarrow{PA}},\overrightarrow{PB}\right), \left({\overrightarrow{PB}},\overrightarrow{PC}\right) y \left({\overrightarrow{PC}},\overrightarrow{PA}\right) \) están igualmente orientados, mediante el signo del producto vectorial (3ª componente de los vectores nula) correspondiente. Es decir si es \( P=(p_1,p_2), A=(a_1,a_2), B=(b_1,b_2)\textrm{ y }C=(c_1, c_2) \) se trata de ver si las tres expresiones:

\( \left(\overrightarrow{PA} \times{} {\vec{PB}}\right)_1 =(a_1-p_1)(b_2-p_2)-(a_2-p_1)(b_1-p_2) \)
\( \left(\overrightarrow{PB} \times{} {\vec{PC}}\right)_1 =(b_1-p_1)(c_2-p_2)-(b_2-p_1)(c_1-p_2) \)
\( \left(\overrightarrow{PC} \times{} {\vec{PA}}\right)_1 =(c_1-p_1)(a_2-p_2)-(c_2-p_1)(a_1-p_2) \)

tienen el mismo signo, en cuyo caso el punto es interior, o diferente, siendo ahora exterior.
Si uno es cero, el punto está en la recta que contiene a un lado. Si los otros dos tienen el mismo signo, está en el lado, si tienen signo contrario en su prolongación. Si dos son nulos, es que se trata de uno de los vértices. Si los tres son nulos, los vértices están alineados.

Puede ser muy ineficiente si el triángulo es muy alargado (tiene ángulos muy agudos).


Para rizar el rizo, supongamos que 2 de los vértices del triángulo dependen de un parámetro: A, B(p), C(p). Entonces el algoritmo daría una serie de puntos también dependientes de dicho parámetro: P1(p), P2(p),...,Pm(p).

Agradezco cualquier pista o sugerencia.

Saludos.

Lo veo complicado ...

Saludos,
Daría todo lo que se por la mitad de lo que ignoro (R. Descartes)
O incluso por muchísimo menos ...  (yo)

19 Septiembre, 2019, 11:08 am
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,066
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino