[Desafio/Duda]: Dibujar area geometrica (PROGRAMACION)

Archivado
Esto es una pregunta o bien para programadores o bien para delineantes, etc. Estoy haciendo un proyecto personal y necesito esto. Obtengo una serie de puntos X,Y y necesito dibujar el area que forma dichos puntos. Es decir:

- Tengo una coleccion de coordenadas X-Y que se dibujaran sobre un PictureBox en blanco. Bien, estos puntos necesito unirlos para que formen el area que representan. Estoy rebanandome el seso pero no se la forma de programarlo ni como llegar a eso.

El lenguaje en el que estoy programando esto es en C#, pero para este caso me es igual. Porque lo que no tengo es el metodo para llegar a unir los puntos de forma adecuada.

Si alguien tiene alguna idea me vendria muy bien. Gracias.
¿Cual es la forma correcta ? Aquella en la que no haya cruces y te quede un polígono? La ruta mas corta que pase por todos los puntos?

Puedes empezar a buscar por el problema "TSP" (Traveller Salesman Problem), en este problema se busca la ruta más corta entre los puntos.

Un saludo.
Puedes empezar a buscar por el problema "TSP" (Traveller Salesman Problem), en este problema se busca la ruta más corta entre los puntos.


Excepto que no :)

- ferdy
Se busca formar un poligono.
Sigues siendo muy poco concreto: http://es.wikipedia.org/wiki/Pol%C3%ADgono
Lo más fácil que se me ocurre es utilizando OpenGL (en 2D ojo), que con una serie de puntos (glVertex2i o glVertex2f según sean las coordenadas enteras o floats respectivamente) te dibuja un polígono (GL_POLYGON)...

http://usuarios.lycos.es/andromeda_stud ... utgl02.htm


EDITO: Una imagen bastante ilustrativa de los polígonos que puedes hacer en OpenGL con el método de arriba y los que no:
Imagen

Así por ejemplo, y si las coordeandas son enteros, el código sería tal que así (faltaría las líneas de inicialización del OpenGL):

glBegin(GL_POLYGON);   
    glVertex2i(x1,y1);
    glVertex2i(x2,y2);
    glVertex2i(x3,y3);
    ....   
glEnd();


EDITO2: No había leído lo de que programas en C#... Si no quieres cambiar de lenguaje hay un binding del OpenGL (también de SDL, Cg y varias más) para .NET y MONO llamado Tao Framework:
http://www.taoframework.com/
Ferdy escribió:
Puedes empezar a buscar por el problema "TSP" (Traveller Salesman Problem), en este problema se busca la ruta más corta entre los puntos.


Excepto que no :)

- ferdy

Excepto que no ... ?:S No te termino de entender, la ruta mas corta que recorra todos los puntos y forme un ciclo sin pasar 2 veces por el mismo punto. Eso es un polígono por definición :).

Para el autor del hilo... Si tienes mas de 4 puntos tienes varios polígonos posibles, todos ellos polígonos válidos.Por eso te pregunto que polígono quieres, te falta una condición para definir un polígono único con N puntos de entrada (área mínima, área máxima, perimetro mínimo, perimetro máximo, etc).
Sertinell escribió:
Ferdy escribió:
Puedes empezar a buscar por el problema "TSP" (Traveller Salesman Problem), en este problema se busca la ruta más corta entre los puntos.


Excepto que no :)

- ferdy

Excepto que no ... ?:S No te termino de entender, la ruta mas corta que recorra todos los puntos y forme un ciclo sin pasar 2 veces por el mismo punto. Eso es un polígono por definición :).

Para el autor del hilo... Si tienes mas de 4 puntos tienes varios polígonos posibles, todos ellos polígonos válidos.Por eso te pregunto que polígono quieres, te falta una condición para definir un polígono único con N puntos de entrada (área mínima, área máxima, perimetro mínimo, perimetro máximo, etc).


El problema del viajante es que a la hora de dibujar te permite cruces de caminos (que no bucles) lo que hace que no puedas dibujar bien el polígono, igual esto para el es un problema. Es decir, que puedes cruzar por un camino entre dos ciudades por el que ya has pasado y yo creo que el creador del hilo lo que busca es la figura sin ningún tipo de cruce, bucle o nada que se le parezca, no?

Un saludo

EDITO: Igual el problema del viajante lo puedes enfocar como un problema de optimización de transporte que hasta donde creo recordar ahí evita a toda costa ningún tipo de cruce de camino y solo pasas 1 vez por cada punto.

La idea básica sería esta:
http://es.wikipedia.org/wiki/Problema_de_rutas_de_vehículos
El camino mas corto es imposible de alcanzar en el caso de que haya cruces, si hay cruces puedes intercambiar los enlaces que se cruzan y tendrás una nueva ruta mas corta que la anterior.
Sertinell escribió:El camino mas corto es imposible de alcanzar en el caso de que haya cruces, si hay cruces puedes intercambiar los enlaces que se cruzan y tendrás una nueva ruta mas corta que la anterior.


Visto así, tiene sentido xD
bueno gente muchas gracias por la ayuda, de verdad no esperaba tantas respuestas. Pues al final la cosa se ha simplificado muchisimo, porque me pasaran los puntos con un numero, correspondiendo a su orden. Ya me lo podian haber dicho antes, porque me pase toda una mañana pensando en como se podia hacer a pelo, sin saber teorias ni na xD. Solo llegue a la conclusion de se podia dar varias figuras geometricas.
tualotuyo escribió:bueno gente muchas gracias por la ayuda, de verdad no esperaba tantas respuestas. Pues al final la cosa se ha simplificado muchisimo, porque me pasaran los puntos con un numero, correspondiendo a su orden. Ya me lo podian haber dicho antes, porque me pase toda una mañana pensando en como se podia hacer a pelo, sin saber teorias ni na xD. Solo llegue a la conclusion de se podia dar varias figuras geometricas.


tu CREES que te lo han simplificado muchisimo, porque si vas a realizar el rasterizado por ti mismo aun te queda lo mas complicado (o laborioso). si vas a realizar el rasterizado por software 100% mirate el algoritmo de bresenham (http://en.wikipedia.org/wiki/Bresenham% ... _algorithm), el Scanline-rendering (http://es.wikipedia.org/wiki/Scanline_Rendering), el algoritmo del pintor (http://es.wikipedia.org/wiki/Algoritmo_del_pintor) y su sucesor el Z-buffer (http://es.wikipedia.org/wiki/Z-Buffer).

en general, si necesitas ayuda, postea tu pregunta y enviame un MP, que no suelo visitar mucho ultimamente software-libre.
aunque ya no lo necesites , a lo mejor a alguien en el futuro le puede ser útil.
Calcular el Área máxima que forman una serie de puntos (convex hull) http://es.wikipedia.org/wiki/Envoltura_convexa . La lista de algoritmos: http://en.wikipedia.org/wiki/Convex_hul ... lanar_case.

Espero haberme enterado bien de tu pregunta.
12 respuestas
Archivado
Volver a Software libre