C++ biblioteca de teselado 2D?

Question

Tengo algunos polígonos convexos almacenados como un vector de puntos STL (más o menos). Quiero tessellate ellos muy rápido, preferiblemente en piezas de tamaño bastante uniforme, y sin "astillas".

Voy a usarlo para hacer estallar algunos objetos en pequeños pedazos. ¿Alguien sabe de una buena biblioteca para teselar polígonos (dividirlos en una malla de polígonos o triángulos convexos más pequeños)?

He visto algunas que ya he encontrado en línea, pero ni siquiera puedo hacer que compilen. Este tipo académico no le da mucha importancia a la facilidad de uso.

Answer 1

CGAL tiene paquetes para resolver este problema. Lo mejor sería probablemente usar el paquete 2D Polygon Partitioning. Por ejemplo, podría generar partición y-monótona de un polígono (funciona para los polígonos no convexos, también) y se podrían obtener algo como esto:

y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Trier_opt_cvx.gif y-monoyone-partitioning http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Partition_2/Idar-Oberstein_appx_cvx.gif

El tiempo runnning es O (log n norte).

En términos de facilidad de uso este es un pequeño ejemplo de código que genera un polígono azar y crear particiones en ella (basado en la this manual example):

typedef CGAL::Exact_predicates_inexact_constructions_kernel K; 
typedef CGAL::Partition_traits_2<K>       Traits; 
typedef Traits::Point_2          Point_2; 
typedef Traits::Polygon_2         Polygon_2; 
typedef std::list<Polygon_2>        Polygon_list; 
typedef CGAL::Creator_uniform_2<int, Point_2>    Creator; 
typedef CGAL::Random_points_in_square_2<Point_2, Creator> Point_generator; 


int main() 
{ 
    Polygon_2 polygon; 
    Polygon_list partition_polys; 

    CGAL::random_polygon_2(50, std::back_inserter(polygon), 
         Point_generator(100)); 

    CGAL::y_monotone_partition_2(polygon.vertices_begin(), 
           polygon.vertices_end(), 
           std::back_inserter(partition_polys)); 

    // at this point partition_polys contains the partition of the input polygons 
    return 0; 
} 

Para instalar CGAL, si usted está en ventanas se puede utilizar el instalador para obtener la biblioteca precompilada, y hay guías de instalación para cada plataforma en this page. Puede que no sea el más sencillo de instalar, pero usted consigue la biblioteca de geometría computacional más usado y robusta que hay por allí, y el cgal mailing list es muy útil para responder preguntas ...

Answer 2

Un poco más de detalle en su entrada y salida deseada podría ser útil.

Por ejemplo, si solo intenta hacer que los polígonos se conviertan en triángulos, probablemente funcione un ventilador de triángulo. Si estás tratando de cortar un polígono en pequeños pedazos, podrías implementar algún tipo de cuadrados de marcha.

---

bien, hice una mala suposición - Supuse que los cuadrados que marchan serían más similares a los cubos de marcha. Resulta que es bastante diferente, y no es lo que quise decir ...: |

En cualquier caso, para responder directamente a su pregunta, no conozco ninguna biblioteca simple que haga lo que está buscando. Estoy de acuerdo con la usabilidad de CGAL.

El algoritmo en el que estaba pensando era básicamente dividir polígonos con líneas, donde las líneas son una cuadrícula, por lo que en su mayoría se obtienen cuadrículas. Si tuviera una intersección de línea de polígono, la implementación sería simple. Otra forma de plantear este problema es tratar el 2do polígono como una función y superponer una grilla de puntos. Entonces solo haces algo similar a los cubos de marcha ... si los 4 puntos están en el polígono, haz un quad, si 3 están en make a triangle, 2 están en make a rectangle, etc. Probablemente overkill. Si querías polígonos de aspecto irregular, podrías aleatorizar las ubicaciones de los puntos de la grilla.

Por otro lado, podría hacer una subdivisión de estilo catmull-clark, pero omita el alisado. El algoritmo es básicamente agregar un punto en el centroide y en el punto medio de cada borde. Luego, para cada esquina del polígono original, se crea un nuevo polígono más pequeño que conecta el punto medio del borde anterior a la esquina, la esquina, el próximo punto medio del borde y el centroide.Esto teja el espacio y tendrá ángulos similares a tu polígono de entrada.

Por lo tanto, un montón de opciones, y me gustaría soluciones de intercambio de ideas, pero todavía no tienen idea de lo que está planeando sobre el uso de este. ¿Esto es para crear mallas destructibles? ¿Estás haciendo algún tipo de procesamiento de malla que requiere elementos más pequeños? ¿Tratando de evitar los artefactos de sombreado de Gouraud? ¿Es esto algo que se ejecuta como un preproceso o en tiempo real? ¿Qué tan importante es la exactitud? Más información resultaría en mejores sugerencias.

Answer 3

Si no quiere construir el conjunto de GCAL en su aplicación - esto es probablemente más sencillo de implementar.

http://www.flipcode.com/archives/Efficient_Polygon_Triangulation.shtml

Answer 4

Como balint.miklos mencionado en un comentario anterior, el paquete de la Shewchuk triangle es bastante bueno. Lo he usado muchas veces; se integra muy bien en los proyectos y existe la interfaz C++ triangle++. Si quiere evitar las astillas, entonces permita que el triángulo agregue puntos de Steiner (interiores), de modo que genere una malla de calidad (generalmente una triangulación de delaunay constreñida).

Answer 5

Si tiene polígonos convexos, y no está demasiado ocupado con la calidad, entonces esto es realmente simple: solo haga ear clipping. No se preocupe, no es O (n^2) para polígonos convexos. Si lo haces de forma ingenua (es decir, recortas los oídos a medida que los encuentres), obtendrás un ventilador de triángulo, que es un poco difícil si tratas de evitar las astillas. Dos heurística triviales que pueden mejorar la triangulación son a

1. Ordenar los oídos, o si eso es demasiado lento
2. Elegir una oreja al azar.

Si desea un triangulador más robusto basado en el recorte de orejas, consulte FIST.

Answer 6

poly2tri parece una muy buena biblioteca ligera C++ para la triangulación de Delaunay en 2D.

Answer 7

Acabo de empezar a investigar el mismo problema y estoy considerando el tessellation de voronoi. El polígono original será obtener una dispersión de puntos aleatorios semi que serán los centros de las celdas de Voronoi, más uniformemente distribuidas que son de tamaño más regularmente las células serán, pero no deben estar en una cuadrícula perfecta de lo contrario los polígonos interiores todos se verán igual. Entonces, lo primero es poder generar esos puntos del centro celular, generarlos sobre el cuadro delimitador del polígono fuente y una prueba interior/exterior no debería ser demasiado difícil.

Los bordes de Voronoi son las líneas de puntos en esta imagen, y son una especie de complemento de la triangulación de Delaunay. Todos los puntos del triángulo agudo embotado:

Boost tiene algunas funciones de Voronoi: http://www.boost.org/doc/libs/1_55_0/libs/polygon/doc/voronoi_basic_tutorial.htm

El siguiente paso es la creación de los polígonos de Voronoi. Voro ++ http://math.lbl.gov/voro++/ está orientado a 3D, pero se sugiere en otro lugar que funcionará aproximadamente una estructura 2d, pero será mucho más lento que el software orientado hacia voronoi 2D. El otro paquete que parece ser mucho mejor que un proyecto huérfano de página de inicio aleatorio es https://github.com/aewallin/openvoronoi.

Parece que OpenCV utiliza para apoyar hacer algo en este sentido, pero ya no se utiliza (pero la API C sigue funcionando?).cv :: distTransform aún se mantiene pero funciona en píxeles y genera salida de píxeles, no vértices y estructuras de datos de polígono de borde, pero puede ser suficiente para mis necesidades si no para las tuyas.

Voy a actualizar esto una vez que haya aprendido más.