Géométrie computationnelle en Python : de la théorie à l'application

Lorsque les gens pensent à la géométrie computationnelle, d'après mon expérience, ils pensent généralement à l'une des deux choses suivantes :

1. Wow, ça a l'air compliqué.
2. Oh oui, coque convexe.

Dans cet article, j'aimerais faire la lumière sur la géométrie computationnelle, en commençant par un bref aperçu du sujet avant de passer à quelques conseils pratiques basés sur mes propres expériences (passez à autre chose si vous maîtrisez bien le sujet).

Pourquoi une telle agitation?

Alors que les algorithmes de géométrie computationnelle de coque convexe sont généralement inclus dans un cours d'introduction aux algorithmes, la géométrie computationnelle est un sujet beaucoup plus riche qui reçoit rarement suffisamment d'attention de la part du développeur/informaticien moyen (à moins que vous ne fassiez des jeux ou autre).

Théoriquement intrigant…

D'un point de vue théorique, les questions de géométrie computationnelle sont souvent extrêmement intéressantes ; les réponses, convaincantes ; et les chemins par lesquels ils sont atteints, variés. Ces qualités en font à elles seules un domaine qui mérite d'être étudié, à mon avis.

Par exemple, considérons le problème de la galerie d'art : nous possédons une galerie d'art et souhaitons installer des caméras de sécurité pour protéger nos œuvres d'art. Mais nous avons un budget serré, nous voulons donc utiliser le moins de caméras possible. De combien de caméras avons-nous besoin ?

Lorsque nous traduisons cela en notation géométrique informatique, le "plan d'étage" de la galerie n'est qu'un simple polygone. Et avec un peu d'huile de coude, nous pouvons prouver que n/3 caméras suffisent toujours pour un polygone sur n sommets, aussi désordonné soit-il. La preuve elle-même utilise des graphes doubles, une théorie des graphes, des triangulations, etc.

Ici, nous voyons une technique de preuve astucieuse et un résultat suffisamment curieux pour être apprécié par lui-même. Mais si la pertinence théorique ne vous suffit pas…

Et important dans la pratique

Comme je l'ai mentionné plus tôt, le développement de jeux s'appuie fortement sur l'application de la géométrie computationnelle (par exemple, la détection de collision repose souvent sur le calcul de l'enveloppe convexe d'un ensemble d'objets) ; tout comme les systèmes d'information géographique (SIG), qui sont utilisés pour stocker et effectuer des calculs sur des données géographiques ; et la robotique aussi (par exemple, pour les problèmes de visibilité et de planification).

Pourquoi est-ce si dur ?

Prenons un problème de géométrie informatique assez simple : étant donné un point et un polygone, le point se trouve-t-il à l'intérieur du polygone ? (C'est ce qu'on appelle le problème du point dans le polygone ou PIP.)

PIP fait un excellent travail pour démontrer pourquoi la géométrie computationnelle peut être (trompeusement) difficile. Pour l'œil humain, ce n'est pas une question difficile. Nous voyons le diagramme suivant et il est immédiatement évident pour nous que le point est dans le polygone :

Même pour des polygones relativement compliqués, la réponse ne nous échappe pas plus d'une seconde ou deux. Mais lorsque nous transmettons ce problème à un ordinateur, il peut voir ce qui suit :

 poly = Polygon([Point(0, 5), Point(1, 1), Point(3, 0), Point(7, 2), Point(7, 6), Point(2, 7)]) point = Point(5.5, 2.5) poly.contains(point)

Ce qui est intuitif pour le cerveau humain ne se traduit pas si facilement en langage informatique.

Plus abstraitement (et en ignorant la nécessité de représenter ces choses dans le code), les problèmes que nous voyons dans cette discipline sont très difficiles à rigoriser ('rendre rigoureux') dans un algorithme de géométrie computationnelle. Comment décririons-nous le scénario du point dans le polygone sans utiliser un langage tautologique tel que « Un point est à l'intérieur d'un polygone s'il est à l'intérieur du polygone » ? Beaucoup de ces propriétés sont si fondamentales et si élémentaires qu'il est difficile de les définir concrètement.

Difficile, mais pas impossible. Par exemple, vous pouvez rigoriser un point dans un polygone avec les définitions suivantes :

• Un point est à l'intérieur d'un polygone si un rayon infini commençant au point coupe un nombre impair d'arêtes de polygone (connue sous le nom de règle paire-impaire).
• Un point est à l'intérieur d'un polygone s'il a un numéro d'enroulement différent de zéro (défini comme le nombre de fois que la courbe définissant le polygone parcourt le point).

À moins que vous n'ayez une certaine expérience de la géométrie computationnelle, ces définitions ne feront probablement pas partie de votre vocabulaire existant. Et c'est peut-être emblématique de la façon dont la géométrie computationnelle peut vous pousser à penser différemment .

Présentation de CCW

Maintenant que nous avons compris l'importance et la difficulté des problèmes de géométrie computationnelle, il est temps de nous mouiller les mains.

À l'épine dorsale du sujet se trouve une opération primitive d'une puissance trompeuse: dans le sens antihoraire, ou «CCW» en abrégé. (Je vous préviens maintenant : CCW apparaîtra encore et encore.)

CCW prend trois points A, B et C comme arguments et demande : ces trois points composent-ils un virage dans le sens antihoraire (vs un virage dans le sens des aiguilles d'une montre) ? En d'autres termes, est-ce que A -> B -> C est un angle dans le sens inverse des aiguilles d'une montre ?

Par exemple, les points verts sont CCW, alors que les points rouges ne le sont pas :

Pourquoi la CCW est importante

CCW nous donne une opération primitive sur laquelle nous pouvons construire. Cela nous donne un point de départ pour rigoriser et résoudre les problèmes de géométrie computationnelle.

Pour vous donner une idée de sa puissance, considérons deux exemples.

Détermination de la convexité

La première : étant donné un polygone, pouvez-vous déterminer s'il est convexe ? La convexité est une propriété inestimable : savoir que vos polygones sont convexes vous permet souvent d'améliorer les performances par ordre de grandeur. À titre d'exemple concret : il existe un algorithme PIP assez simple qui s'exécute en temps Log(n) pour les polygones convexes, mais échoue pour de nombreux polygones concaves.

Intuitivement, cet écart a du sens : les formes convexes sont "sympa", tandis que les formes concaves peuvent avoir des arêtes vives qui font saillie vers l'intérieur et vers l'extérieur - elles ne suivent tout simplement pas les mêmes règles.

Un algorithme de géométrie computationnelle simple (mais non évident) pour déterminer la convexité consiste à vérifier que chaque triplet de sommets consécutifs est CCW. Cela ne prend que quelques lignes de code de géométrie Python (en supposant que les points sont fournis dans le sens inverse des aiguilles d'une montre - si les points sont dans le sens des aiguilles d'une montre, vous voudrez que tous les triplets soient dans le sens des aiguilles d'une montre):

 class Polygon(object): ... def isConvex(self): for i in range(self.n): # Check every triplet of points A = self.points[i % self.n] B = self.points[(i + 1) % self.n] C = self.points[(i + 2) % self.n] if not ccw(A, B, C): return False return True

Essayez ceci sur papier avec quelques exemples. Vous pouvez même utiliser ce résultat pour définir la convexité. (Pour rendre les choses plus intuitives, notez qu'une courbe CCW de A -> B -> C correspond à un angle inférieur à 180, ce qui est une manière largement enseignée de définir la convexité.)

Intersection de ligne

Comme deuxième exemple, considérons l'intersection de segments de ligne, qui peut également être résolue en utilisant uniquement CCW :

 def intersect(a1, b1, a2, b2): """Returns True if line segments a1b1 and a2b2 intersect.""" return ccw(a1, b1, a2) != ccw(a1, b1, b2) and ccw(a2, b2, a1) != ccw(a2, b2, b1)

pourquoi est-ce le cas? L'intersection de segments de droite peut également être formulée comme suit : étant donné un segment avec les extrémités A et B, les extrémités C et D d'un autre segment se trouvent-elles du même côté de AB ? En d'autres termes, si les virages de A -> B -> C et A -> B -> D sont dans la même direction, les segments ne peuvent pas se croiser. Lorsque nous utilisons ce type de langage, il devient clair qu'un tel problème est le pain quotidien de CCW.

Une définition rigoureuse

Maintenant que nous avons compris l'importance du CCW, voyons comment il est calculé. Étant donné les points A, B et C :

 def ccw(A, B, C): """Tests whether the turn formed by A, B, and C is ccw""" return (Bx - Ax) * (Cy - Ay) > (By - Ay) * (Cx - Ax)

Pour comprendre d'où vient cette définition, considérons les vecteurs AB et BC. Si nous prenons leur produit croisé, AB x BC, ce sera un vecteur le long de l'axe z. Mais dans quelle direction (c'est-à-dire +z ou -z) ? Il s'avère que si le produit croisé est positif, le virage se fait dans le sens antihoraire ; sinon, c'est dans le sens des aiguilles d'une montre.

Cette définition ne semblera pas intuitive à moins que vous n'ayez une très bonne compréhension de l'algèbre linéaire, de la règle de la main droite, etc. Mais c'est pourquoi nous avons une abstraction - quand vous pensez CCW, pensez simplement à sa définition intuitive plutôt qu'à son calcul. La valeur sera immédiatement claire.

Ma plongée dans la géométrie computationnelle et la programmation à l'aide de Python

Au cours du dernier mois, j'ai travaillé sur l'implémentation de plusieurs algorithmes de géométrie computationnelle en Python. Comme je vais m'en inspirer tout au long des prochaines sections, je vais prendre une seconde pour décrire mes applications de géométrie computationnelle, qui peuvent être trouvées sur GitHub.

Remarque : Mon expérience est certes limitée. Comme je travaille sur ce genre de choses depuis des mois plutôt que des années, suivez mes conseils avec un grain de sel. Cela dit, j'ai beaucoup appris au cours de ces quelques mois, alors j'espère que ces conseils s'avéreront utiles.

Algorithme de Kirkpatrick

Au cœur de mon travail se trouvait une implémentation de l'algorithme de Kirkpatrick pour la localisation de points. L'énoncé du problème serait quelque chose comme : étant donné une subdivision plane (un groupe de polygones non superposés dans le plan) et un point P, quel polygone contient P ? Pensez point dans le polygone sur les stéroïdes - au lieu d'un seul polygone, vous en avez un plan plein.

En tant que cas d'utilisation, considérons une page Web. Lorsqu'un utilisateur clique sur la souris, la page Web doit comprendre ce sur quoi l'utilisateur a cliqué le plus rapidement possible. Était-ce le bouton A ? Était-ce le lien B ? La page Web est composée de polygones qui ne se chevauchent pas, donc l'algorithme de Kirkpatrick serait bien placé pour aider.

Bien que je ne discute pas de l'algorithme en profondeur, vous pouvez en apprendre plus ici.

Triangle englobant minimal

En tant que sous-tâche, j'ai également implémenté l'algorithme d'O'Rourke pour calculer un triangle englobant/limitant minimum (c'est-à-dire trouver le plus petit triangle qui enferme un ensemble de points convexes) en temps linéaire.

Remarque : le calcul du triangle de délimitation minimum n'aide ni ne nuit aux performances asymptotique de l'algorithme de Kirkpatrick car le calcul lui-même est en temps linéaire, mais il est utile à des fins esthétiques.

Conseils pratiques, applications et préoccupations

Les sections précédentes se sont concentrées sur les raisons pour lesquelles la géométrie computationnelle peut être difficile à raisonner de manière rigoureuse.

En pratique, nous devons faire face à une toute nouvelle série de préoccupations.

Vous vous souvenez de CCW ? En guise de belle transition, voyons encore une autre de ses grandes qualités : elle nous protège contre les dangers des erreurs en virgule flottante.

Erreurs à virgule flottante : pourquoi CCW est roi

Dans mon cours de géométrie computationnelle, Bernard Chazelle, un professeur estimé qui a publié plus d'articles que je ne peux en compter, a établi une règle selon laquelle nous ne pouvions pas mentionner les angles lorsque nous tentons de décrire un algorithme ou une solution.

Pourquoi? Les angles sont désordonnés. Les angles sont "sales". Lorsque vous devez calculer un angle, vous devez diviser ou utiliser une approximation (tout ce qui implique Pi, par exemple) ou une fonction trigonométrique.

Lorsque vous devez calculer un angle dans code , vous serez presque toujours approximatif. Vous serez faussé par un petit degré de précision en virgule flottante, ce qui est important lorsque vous testez l'égalité. Vous pouvez résoudre un point du plan par deux méthodes différentes et, bien sûr, vous attendre à ce que p1.x == p2.x and p1.y == p2.y . Mais, en réalité, cette vérification échouera souvent . De plus (et bien évidemment), ces points auront alors des hachages différents.

Pour aggraver les choses, votre degré d'erreur augmentera à mesure que vos petites différences se propageront dans vos calculs. (Pour quelques exemples plus scientifiques, cet article passe en revue ce qui peut mal tourner lors du calcul de la coque convexe ou de la triangulation de Delaunay.)

Alors, que pouvons-nous faire à ce sujet ?

presque égal

Une partie du problème de la géométrie computationnelle Python est que nous exigeons l' exactitude dans un monde où les choses sont rarement exactes. Cela deviendra un problème plus souvent que lors de la manipulation des angles. Considérer ce qui suit:

 # Define two random points p1 = RandomPoint() p2 = RandomPoint() # Take the line through them l1 = Line(p1, p2) # Shift both points up by sqrt(2) p1.y += sqrt(2) p2.y += sqrt(2) l2 = Line(p1, p2) # Slope 'should' be the same? if abs(l1.slope - l2.slope) > 0: print "Error!" # Error!

En fait, ce code affichera "Erreur!" environ 70 % du temps (empiriquement). Nous pouvons répondre à cette préoccupation en étant légèrement plus indulgents avec notre définition de l'égalité ; c'est-à-dire en sacrifiant un degré de précision.

Une approche que j'ai utilisée (et vue, par exemple, dans certains modules OpenCV) consiste à définir deux nombres comme égaux s'ils ne diffèrent que par une petite valeur epsilon. En Python, vous pourriez avoir :

 def almostEqual(x, y, EPSILON=1e-5): return abs(x - y) < EPSILON class Point(object): ... def __eq__(self, that): return (almostEqual(self.x, that.x) and almostEqual(self.y, that.y))

En pratique, cela est très utile. Vous calculeriez rarement, voire jamais, deux points qui diffèrent de moins de 1e-5 et qui sont en fait censés être des points différents. Je recommande fortement la mise en œuvre de ce type de remplacement. Des méthodes similaires peuvent être utilisées pour les lignes, par exemple :

 class Line(object): ... def __eq__(self, that): return (almostEqual(self.slope, that.slope) and almostEqual(self.intercept, that.intercept))

Des solutions plus avancées ont bien sûr été proposées. Par exemple, l'école de pensée du « calcul géométrique exact » (décrite dans cet article) vise à ce que tous les chemins de décision dans un programme dépendent uniquement du signe d'un calcul, plutôt que de sa valeur numérique exacte, supprimant de nombreuses préoccupations liées aux calculs en virgule flottante. Notre approche de quasi-égalité ne fait qu'effleurer la surface, mais sera souvent suffisante dans la pratique.

CCW est roi

À un niveau supérieur, il est (sans doute) problématique que nous définissions même nos solutions en termes de quantités de calcul exactes telles que des angles ou des coordonnées de points. Plutôt que de s'attaquer uniquement aux symptômes (c'est-à-dire, laver les erreurs en virgule flottante avec almostEqual ), pourquoi ne pas s'attaquer à la cause ? La solution : au lieu de penser en termes d'angles, pensez en termes de CCW , ce qui aidera à faire abstraction des préoccupations associées au calcul en virgule flottante.

Voici un exemple concret : supposons que vous ayez un polygone convexe P , un sommet v et un point u à l'extérieur du polygone. Comment savoir si la droite uv coupe P au-dessus ou au-dessous de v , ou pas du tout, en temps constant ?

La solution de force brute (en plus d'être linéaire, plutôt que constante) serait problématique car vous devriez calculer des points d'intersection de ligne exacts.

Une approche à temps constant que j'ai vue implique:

• Calcul de certains angles avec arctan2 .
• Convertir ces angles en degrés en multipliant par 180/Pi.
• Examiner les relations entre ces différents angles.

Heureusement, l'auteur a utilisé la technique almostEqual ci-dessus pour lisser les erreurs en virgule flottante.

À mon avis, il serait préférable d'éviter complètement le problème des erreurs en virgule flottante. Si vous prenez quelques minutes pour examiner le problème sur papier, vous pouvez obtenir une solution entièrement basée sur CCW. L'intuition : si les sommets adjacents à v sont du même côté de uv , alors la droite ne se coupe pas ; sinon, voyez si u et v sont du même côté de la ligne entre les sommets adjacents et, selon le résultat, comparez leurs hauteurs.

Voici le code Python pour tester l'intersection au-dessus de v (l'intersection ci-dessous inverse simplement le sens des comparaisons):

 def intersectsAbove(verts, v, u): """ Returns True if uv intersects the polygon defined by 'verts' above v. Assumes v is the index of a vertex in 'verts', and u is outside of the polygon. """ n = len(verts) # Test if two adjacent vertices are on same side of line (implies # tangency) if ccw(u, verts[v], verts[(v - 1) % n]) == ccw(u, verts[v], verts[(v + 1) % n]): return False # Test if u and v are on same side of line from adjacent # vertices if ccw(verts[(v - 1) % n], verts[(v + 1) % n], u) == ccw(verts[(v - 1) % n], verts[(v + 1) % n], verts[v]): return uy > verts[v].y else: return uy < verts[v].y

La solution n'est pas immédiatement évidente à l'œil nu, mais elle est dans le langage d'un algorithme de géométrie computationnelle : "du même côté de la ligne" est un élément classique de cet algorithme de confiance.

Mieux vaut fait que parfait

Dans la littérature géométrique computationnelle, il y a souvent une bonne quantité de magie impliquée dans des opérations apparemment simples. Cela vous donne le choix : vous pouvez faire les choses à la dure, en suivant un article qui définit une solution incroyablement avancée à un problème pas si avancé, ou vous pouvez faire les choses de manière simple avec un peu de force brute.

Encore une fois, je vais utiliser un exemple : échantillonner un point intérieur aléatoire à partir d'un polygone arbitraire. En d'autres termes, je vous donne un polygone simple et vous me donnez un point aléatoire à l'intérieur (uniformément réparti sur le polygone).

Souvent, des points intérieurs sont nécessaires pour les tests. Dans ce cas, vous n'avez aucune exigence d'exécution spécifique sur l'algorithme de géométrie de calcul qui les produit (dans des limites raisonnables). La solution rapide et sale, qui prend environ 2 minutes à mettre en œuvre, serait de choisir un point aléatoire dans une boîte contenant le polygone et de voir si le point lui-même se trouve dans le polygone.

Par exemple, nous pouvons manquer deux fois et trouver un échantillon valide uniquement sur le troisième point :

Voici le code :

 class Polygon(object): ... def interiorPoint(self): """Returns a random point interior point""" min_x = min([px for p in self.points]) max_x = max([px for p in self.points]) min_y = min([py for p in self.points]) max_y = max([py for p in self.points]) def x(): return min_x + random() * (max_x - min_x) def y(): return min_y + random() * (max_y - min_y) p = Point(x(), y()) while not self.contains(p): p = Point(x(), y()) return p def contains(self, p): for i in range(self.n): p1 = self.points[i] p2 = self.points[(i + 1) % self.n] p3 = self.points[(i + 2) % self.n] if not ccw(p1, p2, p3): return False return True

C'est ce qu'on appelle l' échantillonnage par rejet : prenez des points au hasard jusqu'à ce qu'un réponde à vos critères. Même s'il peut falloir plusieurs échantillons pour trouver un point répondant à vos critères, en pratique, la différence sera négligeable pour votre suite de tests. Alors pourquoi travailler plus dur ? En résumé : n'ayez pas peur d'emprunter la voie sale lorsque l'occasion l'exige.

Au fait : si vous voulez un algorithme exact pour l'échantillonnage aléatoire, il y en a un astucieux ici que j'ai implémenté ci-dessous. L'essentiel :

1. Triangulez votre polygone (c'est-à-dire divisez-le en triangles).
2. Choisissez un triangle dont la probabilité est proportionnelle à son aire.
3. Prenez un point aléatoire à l'intérieur du triangle choisi (une opération à temps constant).

Notez que cet algorithme vous oblige à trianguler votre polygone, ce qui impose immédiatement une limite d'exécution différente à l'algorithme, ainsi que la nécessité d' avoir une bibliothèque pour trianguler des polygones arbitraires (j'ai utilisé poly2tri avec des liaisons Python).

 from p2t import CDT class Triangle(object): ... def area(self): return abs((Bx * Ay - Ax * By) + (Cx * By - Bx * Cy) + (Ax * Cy - Cx * Ay)) / 2 def interiorPoint(self): r1 = random() r2 = random() # From http://www.cs.princeton.edu/~funk/tog02.pdf return (1 - sqrt(r1)) * A + sqrt(r1) * (1 - r2) * B + r2 * sqrt(r1) * C class Polygon(object): ... def triangulate(self): # Triangulate poly with hole cdt = CDT(poly.points) triangles = cdt.triangulate() def convert(t): A = Point(tax, tay) B = Point(tbx, tby) C = Point(tcx, tcy) return Triangle(A, B, C) return map(convert, triangles) def interiorPoint(self): # Triangulate polygon triangles = self.triangulate() areas = [t.area() for t in triangles] total = sum(areas) # Calculate normalized areas probabilities = [area / total for area in areas] weighted_triangles = zip(triangles, probabilities) # Sample triangles according to area r = random() count = 0 for (triangle, prob) in weighted_triangles: count += prob # Take random point from chosen triangle if count > r: return triangle.interiorPoint()

Espérons que l'effort supplémentaire est évident à partir du code. N'oubliez pas : comme on dit sur Facebook, "fait vaut mieux que parfait". Il en va de même pour les problèmes de géométrie computationnelle.

Tests visuels et automatisés

Comme de nombreux problèmes sur lesquels vous travaillez en géométrie computationnelle sont définis en termes de qualités ou de quantités facilement visualisables, les tests visuels sont particulièrement importants, bien qu'insuffisants en eux-mêmes. La suite de tests idéale combinera des tests automatisés visuels et aléatoires.

Encore une fois, nous procédons par l'exemple. Envisagez de tester notre implémentation de l'algorithme de Kirkpatrick. À une étape, l'algorithme doit délimiter le polygone donné par un triangle et trianguler la région entre le polygone et le triangle extérieur. Voici un exemple visuel, où la ligne verte continue définit le polygone initial et les lignes en pointillés définissent la région triangulée :

Confirmer que cette triangulation a été exécutée correctement est très difficile à vérifier par le code, mais est immédiatement évident à l'œil humain. Remarque : Je suggère fortement d'utiliser Matplotlib pour vous aider dans vos tests visuels - il y a un bon guide ici.

Plus tard, nous voudrons vérifier que l'algorithme localise correctement les points. Une approche aléatoire et automatisée consisterait à générer un ensemble de points intérieurs pour chaque polygone et à s'assurer que nous renvoyons le polygone souhaité. Dans du code:

 class TestLocator(unittest.TestCase): ... def runLocator(self, polygons): # Pre-process regions l = Locator(polygons) # Ensure correctness for polygon in polygons: # Test 100 random interior points per region for k in range(100): target = polygon.interiorPoint() target_polygon = l.locate(target) self.assertEqual(polygon, target_polygon) self.assertTrue(target_polygon.contains(target))

Nous pourrions ensuite utiliser la méthode runLocator sur différents ensembles de polygones, ce qui nous donnerait une suite de tests bien diversifiée.

Solutions Open Source

La géométrie computationnelle dispose d'une belle suite de bibliothèques et de solutions open source disponibles quel que soit le langage de programmation de votre choix (bien que les bibliothèques C++ semblent surgir en quantité disproportionnée).

Les avantages de l'utilisation de solutions open source existantes (comme avec le calcul scientifique en Python) sont bien connus et ont été largement discutés, donc je ne m'étendrai pas là-dessus ici. Mais j'ai pensé mentionner quelques ressources centrées sur Python que j'ai trouvées utiles :

• poly2tri : une excellente bibliothèque pour les triangulations rapides de polygones. Prend également en charge (et c'est souvent crucial) les polygones avec des trous . Écrit en C++, poly2tri a également des liaisons Python et était assez facile à utiliser. Voir ma méthode de triangulate ci-dessus pour un avant-goût des appels de fonction.
• scipy.spatial : comprend des fonctions pour le calcul des coques convexes, des triangulations de Delaunay, etc. Rapide (comme toujours), fiable, etc. Remarque : j'ai trouvé utile d'utiliser mon propre type de données Point avec une méthode toNumpy : def np(self): return [self.x, self.y] . Ensuite, je pourrais facilement appeler les méthodes scipy.spatiales, par exemple: scipy.spatial.ConvexHull(np.array(map(lambda p: p.np()), points)) .
• OpenCV : la bibliothèque de vision par ordinateur open source contient de jolis modules de géométrie computationnelle autonomes. En particulier, j'ai utilisé sa fonction de triangle englobant minimum pendant un certain temps avant de l'implémenter moi-même.

Conclusion

J'espère que cet article vous a donné un avant-goût de la beauté de la géométrie computationnelle en tant que développeur Python, un sujet riche en problèmes fascinants et en applications tout aussi fascinantes.

En pratique, les implémentations géométriques computationnelles présentent des défis uniques qui vous pousseront à exercer de nouvelles compétences passionnantes en résolution de problèmes.

Si vous souhaitez en savoir plus ou si vous avez des questions à me poser, je peux être contacté à [email protected].