Programación en C++, preguntas sobre polígonos convexos
Primero hablemos del principio de graficar polígonos.
Si todos los lados de un polígono están en el lado derecho de la línea de extensión de uno de los lados, entonces el polígono es un polígono gráfico, como extender el lado ab, luego todos los demás lados del polígono gráfico están en un lado de ab, entonces puede ser un polígono gráfico y luego determinar si los otros lados están en un lado de un lado determinado. , como extender el lado bc para determinar si los otros lados están en el lado bc, haga un bucle así hasta que se juzgue que todos los lados están en el mismo lado, es un polígono gráfico; no.
Algoritmo:
Según la ecuación en línea recta (y-y1)/(x-x1)=(y1-y2)/(x1-x2); en ambos lados, obtenemos x(y2 -y1)+y(x1-x2)-x1y2+x2y1=0, luego establecemos t=x(y2-y1)+y(x1-x2)-x1y2+x2y1 donde (x , y) es el punto que se está probando, y (x1, y1) y (x2, y2) son dos puntos conocidos, por lo que cuando el punto probado (x, y) está ubicado en la línea recta, entonces t=0; están todos en el mismo lado, entonces t es todo mayor que 0 o t es todo menor que 0. Luego intercambie (x1, y1) y (x2, y2) en secuencia y mida otros puntos en secuencia para determinar si todos los puntos pueden formar un polígono gráfico.
A continuación se explican las partes relevantes del programa
La primera declaración for en la función tt es determinar si un determinado punto está en el mismo lado de la línea recta del programa. es
for(int i=0;i { if(i==a||i==b) { continuar;} t=p[i][0]*(p[b][1]-p[a][1])+(p[a][0]-p[b][0])*p [i ][1]-p[a][0]*p[b][1]+p[b][0]*p[a][1]; if(t= =0 ) devuelve 0; más si(t>0) temp[k++]=1; más temp[k++]=-1; } Declaración 1 if(i==a||i==b) {continuar;} se utiliza para determinar si el punto de coordenadas entrante a medir es consistente con el dos puntos conocidos en la línea recta Las coordenadas x coinciden. Si coinciden, significa que son dos puntos conocidos en la línea recta. Deje que el programa continúe haciendo un bucle para probar otros puntos. Por ejemplo, los dos puntos que forman una línea recta son (p[a][0], p[a][1]) y (p[b][0], p[b][1]). Para probar i y aob son iguales, se puede concluir que es uno de los dos puntos conocidos. Estos dos puntos no necesitan ser probados. Por ejemplo, si i = a, el resultado es (p [. i][0], p[i][1]) y Es obvio que los puntos conocidos coinciden. Declaración 2 t=p[i][0]*(p[b][1]-p[a][1])+(p[a][ 0]-p[b][0])*p[i][1]-p[a][0]*p[b][1]+p[b][0]*p[a][1 ]; Esta oración es la fórmula presentada anteriormente. Esta fórmula se utiliza para determinar si el punto a medir está en el mismo lado de la línea recta. Declaración 3 if(t==0) return 0; Obviamente, si un determinado t=0, significa que el punto a medir está ubicado en la línea recta, y se puede juzgar directamente. Si no se puede formar un polígono gráfico, se puede devolver a 0 y no es necesario volver a probarlo. Declaración 4 else if(t>0) temp[k++]=1; si todo t es mayor que 0, asigne el valor de la variable de matriz temporal a 1. Nota , Aún no es posible determinar si se puede formar un polígono gráfico, porque a menos que los valores en temp sean todos 1, es decir, todos los puntos a medir estén ubicados en el mismo lado de la línea recta, un gráfico Se puede formar un polígono. Declaración 5 else temp[k++]=-1; El principio es el mismo que el de la declaración 4. Si el punto a medir está al otro lado de la línea recta, asigne un determinado elemento en la matriz a -1. La segunda declaración for en la función tt for(int j=1;j La función es: si el primer valor en la matriz temporal no es igual a ningún valor posterior, significa que no se puede formar el polígono del gráfico y devuelve 0; de lo contrario, devuelve 1. Por ejemplo, el primer juicio es que temp [0] = 1 o -1, luego, si se puede formar un polígono gráfico, todos los valores posteriores deben ser iguales al valor de temp [0], por lo que este es un juicio de si todos los puntos son declaraciones en el mismo lado de la línea. Veamos las partes clave de la función real La primera declaración for for(int i=0;i La función de esta declaración es inicializar el indicador de matriz de bits de bandera. La segunda declaración for (declaración clave) for(int i=0;i { for(int j=1; j { if(bandera[j]) continuar; if(tt(p,m,j)) {bandera[m]=1; =j; break; } } } Nota: El punto j y la variable m en la segunda declaración for aquí son los dos puntos que forman una línea recta. entonces Estos dos puntos son (pp[m][0], pp[m][1]) y (pp[j][0], pp[j][1] Por lo tanto, estos dos puntos forman una línea recta). , Entre ellos, 0 en dos dimensiones representa la coordenada X y 1 representa la coordenada Y. Así es como se pasan estos dos parámetros a la función tt. if(tt(p,m,j)) {flag[m]=1;m=j; break } significa pasar el primer punto a la función tt para determinar todos los puntos a medir; ¿Está en el mismo lado de la línea recta formada por los puntos my j? Si está en el mismo lado, significa que es posible formar un polígono gráfico. La función tt devuelve 1 y luego establece el bit de bandera en. flag[m] a 1, porque m =0, entonces flag[0]=1 luego asigna j a m y usa un bucle para determinar si otros puntos están en el mismo lado cuando la línea recta formada por los siguientes dos puntos; se encuentra. Luego saltamos del bucle interno. Debido a que hemos encontrado dos puntos que pueden formar un polígono, saltamos del bucle interno la próxima vez usaremos este punto como punto de partida para juzgar si la línea recta comienza desde este punto. otros puntos pueden formar un gráfico. Los polígonos, como la línea recta formada por los dos puntos m = 0 y j = 1, pueden cumplir con los requisitos del polígono de la figura. Por lo tanto, el valor de j se asigna a m. En este momento, se agrega i al bucle por 1, y luego se considera que el punto m, que es 1, es diferente de los otros puntos. En este momento, si la línea recta formada por los puntos puede cumplir con los requisitos, j =. 1. Juzgue si m = 1 y j = 1 están satisfechos. Obviamente no está satisfecho. Debido a que son el mismo punto, la declaración en if no se ejecuta (por lo que no es necesario juzgar que j es igual al valor de m). ), y luego ejecute el j ++ interno. En este momento, continúe juzgando si la línea recta formada por los dos puntos m = 1 y j = 2 puede cumplir con los requisitos. Si es así, establezca la posición de la bandera en 1 y continúe. Se asigna j = 2 a m y se hace el mismo juicio. Si no se puede satisfacer, continúe juzgando si los puntos de m = 1 y j = 3 cumplen con los requisitos. Si se pueden satisfacer, realice un bucle, si no, entonces j + 1 hasta que se juzguen todos los puntos. a todos los demás puntos. Si las líneas rectas formadas no pueden cumplir con los requisitos, significa que el polígono del gráfico no se puede formar porque hay un elemento con un valor de 0 en el indicador de bits de la matriz de banderas. Si se encuentran N aristas (es por eso que hago N veces) que cumplen con este requisito, significa que es posible formar un polígono gráfico. Tenga en cuenta que es posible, porque todavía queda la última arista que no se ha juzgado. y este borde es el punto de partida. Si la línea recta formada por el punto final puede cumplir con los requisitos, esta línea recta debe juzgarse al final. Si se encuentran N-1 aristas que pueden formar un polígono, el valor de los elementos de N bits en el bit de la matriz de banderas es 1, lo que significa que N-1 aristas cumplen los requisitos. ¿Por qué solo hay N-1 bordes? Suponga que, por ejemplo, el punto 0 y el punto 1 cumplen con los requisitos, y el bucle exterior i = 1. requisitos, entonces bucle externo i = 2; si los puntos 2 y 3 cumplen con los requisitos, entonces i = 3. En este momento, tenga en cuenta que debido a que m = 3 y el valor máximo de j es 3, el punto 0 es. No juzgado cuando el primer punto y el tercer punto forman una línea recta, es decir, la línea recta formada por el punto inicial y el punto final, hay que hacer un juicio final para llegar a la conclusión correcta, y en este momento m. =3; no importa cuál sea el valor de j, no se puede comparar con m. El punto =3 forma una línea recta que cumple con los requisitos, por lo que el valor de la bandera [3] también es 0. Es por eso que hay una declaración flag[m]=1 al final, y por qué hay una declaración if(tt(p,0,m)) return 1. Esta declaración es el juicio del punto final; y el punto de partida. , pero esta declaración debe estar después de la declaración for(int i=0;i Finalmente, veamos la función de la declaración if(flag[j]) continue; Suponiendo que la línea recta formada por m=0 y j=1 cumple con los requisitos. , luego flag[0]=1; En este momento, asigne el valor de j a m, por lo que m = 1, y luego i++. Luego asumimos que m = 1 y j = 2 cumplen con los requisitos, luego marcamos [1]. =1; Asigne j a m nuevamente, luego m =2; luego i++, luego m=2 entonces if(flag[j]) se ejecutará y podrá ver flag[j] porque j=1 tiene; asignó flag[1] a 1 antes, por lo que no es necesario juzgar la línea recta formada por j=1 y m=2, y j=1 y m=2 representan la misma línea recta que m=1 y j=. 2, por lo que no se permite juzgar si la misma línea recta puede formarse dos veces en el polígono gráfico, por lo que esta afirmación es necesaria y no puede faltar. Finalmente, dejemos que j++ juzgue directamente m = 2 y j = 2, y así sucesivamente hasta que se juzguen todas las líneas rectas. En una palabra, la función de esta afirmación es evitar que se repitan los juicios sobre la misma recta. El contenido del programa principal ha sido explicado, creo que otros lugares deberían poder entenderlo. Método de entrada dinámica: Cree una variable global N, como int N; Ingrese el valor N antes del bucle while en la función principal, que es, cin >>N; Luego modifica la matriz temporal en la función tt y declarala como int *temp=new int; Modifica la matriz de banderas en la función real y declaralo como int *flag= new int; Los demás lugares permanecen sin cambios, ahora puedes ingresar tanto como quieras.