Probablemente haría una triangulación de Delaunay, que dividiría el polígono en triángulos. La triangulación de Delaunay evita triángulos delgados, por lo que probablemente ayudará a reducir la cantidad de triángulos. Como cualquier triángulo se puede convertir en dos triángulos rectángulos, tomaría los triángulos generados por la triangulación de Delaunay y los dividiría por la mitad (no haga esto para triángulos que ya son triángulos rectángulos). Eso me dejaría con el polígono original triangulado por triángulos rectángulos.
A continuación, me gustaría convertir pares de triángulos que forman rectángulos en rectángulos. Para hacer esto, iteraría sobre cada par de vértices en cada triángulo. Este bucle construiría una tabla hash que mapea pares de vértices conectados a triángulos que tienen esos vértices (puede haber un máximo de dos triángulos que comparten un par dado de vértices conectados). Luego, recorrería los valores de la tabla hash para obtener pares de triángulos que se tocaran. Para cada par de triángulos que se toca, verificaría si los ángulos en cada vértice compartido son complementarios. Si ambos vértices compartidos producen ángulos complementarios, combinaría los dos triángulos en un rectángulo.
Luego combinaría rectángulos de manera análoga para formar rectángulos más grandes.
- ¿Qué es una explicación intuitiva del teorema de Rice?
- Dado un conjunto de n rectángulos alineados en el eje en el plano, ¿qué tan grande es el subconjunto más grande de estos rectángulos que contienen un punto común en O (n ^ 3) y luego en el orden O (nlogn)?
- ¿Qué es la teoría analítica de números?
- ¿Cuáles son los cursos matemáticos recomendados para el aprendizaje automático y el procesamiento de big data?
- ¿Cuál es el problema P vs. NP y por qué es tan importante?
Esto me dejaría con un polígono dividido en triángulos rectángulos y rectángulos.
Dudo que esta sea una solución óptima, pero puede estar cerca.
