¿estructura De Datos Para Almacenar Poligonos 2d?

[Alvaro (Garred)]

 Estoy tratando de hacer un juego de plataformas bidimensional vectorial.

Mi problema es que no se muy bien q estructura de datos utilizar para almacenar los poligonos de los que estara compuesto el escenario (poligonos 2D, compuestos de triangulos). Estoy seguro de que sera uno tipo arbol, pero no me decanto por ninguno ya q se muy poco del tema.

Las operaciones que necesitaria realizar en el arbol con esos poligonos, por orden de importancia, serian:
- Hallar los poligonos que ocupan una region rectangular cualquiera (para saber que poligonos entran en el area de la camara).
- Hallar si 2 poligonos poligonos se solapan (no necesito hallar la interseccion en si).
- Hallar el punto/arista/poligono mas cercana a un punto/arista/poligono.
- Sacar y meter poligonos.

Si alguien me puede guiar un poco se lo agradeceria. Un saludo.

[senior wapo]

 Si no necesitas eliminar poligonos individuales durante el desarrollo (solo al final del nivel para borrar todos), te recomiendo un vector (array dinamico) de puntos 2D que sea global para todos los polígonos. Los poligonos los defines por indice del punto inicial y numero de puntos (los guardas todos consecutivos en el array global) y los guardas a su vez en otro array.

Es la forma más compacta y simple.

[Alvaro (Garred)]

 Gracias, es una buena idea. La utilizare para los poligonos estaticos. Para los que se desplacen por el escenario creo q utilizare un quadtree normalito que almacene cada poligono como el rectangulo que lo contiene.