Réduire 2d formes irrégulières aux primitives régulières

Question

Je recherche un algorithme ou essayé & méthode testée pour analyser polgygons irréguliers et les réduire en primitives (carrés, rectangles, trapèzes). Une façon de regarder de façon récurrente les formes pour déterminer le meilleur ajustement pour les polygones réguliers.

voir l'image coup

Les formes noires sont les polygones irréguliers et le bleu représente la regualar souhaitée, ce qui correspond à l'intérieur. L'exemple de gauche devrait être simple, mais c'est parce qu'il s'agit de trouver le rectangle qui peut tenir dans la forme la plus grande. Les polygones seront d'une taille indéterminée (mais disons qu'ils ont moins de 32 côtés). Ce que j'espère, c'est de pouvoir diviser les polys en plusieurs regualar - ce qui me laisse un peu perdu. Malheureusement, je n'ai pas de code pour le moment car je suis bloqué pour savoir la meilleure façon d'avancer. Le script sera fait en JavasScript pur. Ce n'est pas un devoir :)

Answer 1

Tout d'abord, vous devez vérifier si votre polygone est convexe ou concave. Si c'est le dernier, alors vous devez le voir comme plusieurs polygones convexes "mis ensemble" et les manipuler séparément. (Il est facile à votre esprit d'imaginer une grande paire de ciseaux qui coupe le polygone en plusieurs polygones plus petits). Lorsque cela est fait, vous avez un seul polygone, ou plusieurs polygones. Calculez le point de gravité du polygone pour chaque polygone et (P (i), P ((i + 1) mod n), G) formera une forme triviale, un triangle. Ces triangles vont résoudre votre problème.

Si vous avez besoin de formes avec quatre angles, puis quatre points consécutifs forment une forme de quatre angles. Mais cette approche pourrait vous laisser avec un plus petit polygone avec un plus petit nombre d'angles au milieu du polygone principal, qui devra être manipulé.