🇬🇧 :
This project focuses on developing algorithms to find the smallest inclusion of one polygon within another. Starting with a basic naive algorithm that checks all polygons, it progresses through various optimizations, including surface-based sorting and the use of polygon quadrants for further efficiency. The goal is to optimize the inclusion algorithm to handle more complex datasets with better performance. Multiple time complexity tests have been conducted to analyze performance, alongside theoretical complexity studies using polygon generators sourced from GitHub. The results demonstrate significant improvements in computational speed, making these algorithms applicable for advanced geometric analysis in both academic and practical contexts.
🇫🇷 :
Ce projet se concentre sur le développement d'algorithmes permettant de trouver la plus petite inclusion d'un polygone dans un autre. En partant d'un algorithme naïf qui parcourt tous les polygones, le projet explore plusieurs optimisations, notamment un tri basé sur la surface et l'utilisation des quadrants des polygones pour améliorer l'efficacité. L'objectif est d'optimiser l'algorithme d'inclusion pour traiter des ensembles de données plus complexes avec de meilleures performances. Plusieurs tests de complexité temporelle ont été effectués, ainsi qu'une étude de la complexité théorique avec des générateurs de polygones trouvés sur GitHub. Les résultats montrent des améliorations significatives en termes de rapidité, rendant ces algorithmes adaptés à des analyses géométriques avancées, tant dans un contexte académique que pratique.