Comment simplifier un seul polygone UIBezierPath complexe dans iOS

Problème:

J'ai un polygone généré par l'user (en enregistrant les touches de l'user sur l'écran) qui peut être simple ou complexe (nombre complexe d'intersections inconnues) et je veux avoir un simple polygone résultant des mêmes points sur le polygone d'origine, quelque chose comme contour ou un contour si vous voulez.

image Courtoisie d'un utilisateur inconnu sur débordement de pile

Solutions possibles:

Je l'ai trouvé, mais c'est une solution JavaScript et c'est une illustration parfaite de ce dont j'ai besoin, mais en ActionScript! Je n'ai pas besoin du Chemin lui-même, les points suffiront. Comment aborderiez-vous ce problème?

Mettre à jour:

Comme je regardais plus loin, j'ai vu quelques personnes suggérant que la solution utilise un algorithm de Convex Hull sur les points, mais, convexe shell n'est pas la réponse ici parce que si j'ai raison le résultat sera comme suit:

coque convexe reuslt

L'opération que vous décrivez est une union . Généralement, le calcul de l'union d'un set de polygones est quelque peu compliqué. Le faire de manière efficace et précise est plus compliqué. iOS ne fournit pas d'API publique pour cette opération.

Je vous suggère d'utiliser une bibliothèque C ou C ++ existante pour le faire pour vous. Voilà quelque:

  • Clipper (licence Boost)
  • Boost Geometry (licence Boost)
  • General Polygon Clipper (Gratuit pour un usage non commercial, a déjà un wrapper Objective-C)

Il y en a d'autres que vous pouvez find à partir des liens de ces pages ou en utilisant votre moteur de search préféré. Les termes de search utiles include "polygone", "geometry", "union" et "écrêtage".

METTRE À JOUR

Je comprends que vous dessinez un seul polygone. Néanless, dans le cas de la bibliothèque Clipper au less, l'opération syndicale fait ce que vous requestz:

union des étoiles

Le polygone sur le fond blanc est l'écanvas que j'ai créée en tapant. Il s'intersecte lui-même. J'ai utilisé l'opération d'union de Clipper pour créer le polygone sur le fond vert. J'ai passé le polygone tapé en tant que sujet sans polygones de clip:

- (UIBezierPath *)pathWithManyPoints:(CGPoint const *)points count:(NSUInteger)count { Path subject; for (NSUInteger i = 0; i < count; ++i) { subject << IntPoint(points[i].x, points[i].y); } Clipper clipper; clipper.AddPath(subject, ptSubject, true); Paths solutions; clipper.Execute(ctUnion, solutions, pftNonZero, pftNonZero); UIBezierPath *path = [UIBezierPath bezierPath]; for (size_t i = 0; i < solutions.size(); ++i) { Path& solution = solutions[i]; if (solution.size() > 0) { [path moveToPoint:cgPointWithIntPoint(solution[0])]; for (size_t j = 1; j < solution.size(); ++j) { [path addLineToPoint:cgPointWithIntPoint(solution[j])]; } [path closePath]; } } return path; } 

D'un autre côté, étant donné un polygone d'input plus complexe, il existe plusieurs façons de le modifier:

trou union

L'union simple (simple) vous renvoie un polygone avec un trou dedans. Si vous ne voulez pas de trous dans la sortie, vous devez prendre les loops individuelles (sous-paths) produites par l'union initiale, les orienter de la même manière, puis effectuer une deuxième union de toutes les loops orientées. C'est ainsi que j'ai calculé le polygone "union profonde" sur le fond orange:

 - (UIBezierPath *)pathWithManyPoints:(CGPoint const *)points count:(NSUInteger)count { Path subject; for (NSUInteger i = 0; i < count; ++i) { subject << IntPoint(points[i].x, points[i].y); } Clipper clipper; clipper.AddPath(subject, ptSubject, true); Paths intermediateSolutions; clipper.Execute(ctUnion, intermediateSolutions, pftNonZero, pftNonZero); clipper.Clear(); for (size_t i = 0; i < intermediateSolutions.size(); ++i) { if (Orientation(intermediateSolutions[i])) { reverse(intermediateSolutions[i]); } } clipper.AddPaths(intermediateSolutions, ptSubject, true); Paths solutions; clipper.Execute(ctUnion, solutions, pftNonZero, pftNonZero); UIBezierPath *path = [UIBezierPath bezierPath]; for (size_t i = 0; i < solutions.size(); ++i) { Path& solution = solutions[i]; if (solution.size() > 0) { [path moveToPoint:cgPointWithIntPoint(solution[0])]; for (size_t j = 1; j < solution.size(); ++j) { [path addLineToPoint:cgPointWithIntPoint(solution[j])]; } [path closePath]; } } return path; } 

Clipper a également une fonction SimplifyPolygon qui produit le même résultat pour l'exemple d'écanvas, peut-être avec less de code. Je ne sais pas ce qu'il produit pour le second exemple (avec le trou intérieur). Je n'ai pas essayé.

Vous pouvez download mon application de test autonome depuis ce repository github .

Pour utiliser le code JavaScript, vous pouvez vérifier cette réponse:

L'interface Objective-C dans le framework JavascriptCore introduit avec iOS 7 permet d'appeler des methods Objective-C à partir de Javascript. Pour une introduction intéressante à ces fonctionnalités, consultez la session 2013 de la WWDC sur l'intégration de JavaScript dans les applications natives sur le réseau de développeurs d'Apple: https://developer.apple.com/videos/wwdc/2013/?id=615

Il mentionne JS-> Objective-C mais JSCore fonctionne également dans l'autre sens.

Autrement, comme quelqu'un l'a suggéré, il devrait être assez facile de «traduire» le code JS car il ne s'agirait que de calculs mathématiques.

Avec un peu de reflection:

  1. trouve le sumt le plus à gauche. C'est définitivement à la limite. Commencez là;
  2. regardez le long du bord courant vers le prochain sumt listé;
  3. vérifiez si l'une des autres arêtes coupe celle que vous regardez;
  4. si c'est le cas, trouvez le premier sumt devant votre position actuelle et déplacez-le;
  5. répétez de (2) avec le bord que vous venez de passer sur;
  6. Continuez jusqu'à ce que vous reveniez au sumt en (1).

(et voir le commentaire re: un commentaire précédent erroné que j'avais fait à propos de l'obtention du path d'un UIBezierPath )