Comment lier quatre points à un polygone convexe

Comment lier quatre points à un polygone convexe? Je veux dire comment identifier l'ordre de ces quatre points.Comment lier quatre points à un polygone convexe

Merci.

Zhong

Source

2010-08-06 Fihop

Cette reconnaissance d'image vous donne-t-elle une image et vous devez trouver les points? Qu'avez-vous essayé, quel a été le résultat? –

Closers: Comment n'est-ce pas une vraie question? – paxdiablo

Oui, c'est la reconnaissance d'image. – Fihop

La méthode atan2() est à portée de main pour cela, et se trouve dans la plupart des langues.

atan2(y,x) et convertit les coordonnées rectangulaires (x,y) à l'angle theta à partir des coordonnées polaires (r,theta).

Compte tenu de 4 points, trouver leur moyenne. Calculez ensuite les quatre vecteurs (x, y) obtenus en soustrayant la moyenne de chacun des quatre points.

Pour chacun de ces vecteurs (x, y), calculer l'angle θ = atan2 (y, x). θ sera entre - π/2 et π/2.

Trier les θ. Cela vous donnera l'ordre des points, dans le sens des aiguilles d'une montre.

Cela ne fonctionne que pour les quadrilatères convexes.

Source

2010-08-07 16:33:37 brainjam

Parfait ~. Vous avez répondu à ma question. Est-il nécessaire de normaliser les coordonnées de tous les points en fonction du point central avant de diviser x par y? – Fihop

Aucune opération de division n'est requise. Et il n'est pas nécessaire de normaliser les coordonnées de atan2(). – brainjam

Ici, normaliser les coordonnées signifie calculer les nouvelles coordonnées de ces quatre points par rapport au centre. Mon mauvais anglais. :) – Fihop

prendre le point central (à savoir la moyenne de x et y coords), puis calculer les valeurs x/y pour y<centery, puis pour y>=centery. serait le plus rapide je suppose.

(qui est, si je comprends bien la question en premier lieu ...)

Source

2010-08-06 23:53:41 mvds

OUI! Je suis d'accord. Belle solution Ce qui suit est ma compréhension: En supposant que nous avons quatre points bidimensionnels (a_x, a_y), (b_x, b_y) (d_x, d_y), (e_x, e_y). Nous pouvons calculer le point central, en disant (c_x, c_y). – Fihop

Trouvez les valeurs y pour y> c_y, en disant 4 et 2, et les valeurs y pour y c_x, en disant 1 et 4, et les valeurs x pour x < c_x, en disant 2 et 3. – Fihop

Quant à la façon de lier ces quatre points à un polygone convexe, Premièrement, les liens 4 et 2, puis nous devrions décider le point suivant du point 2, c'est 3 (parce que les x valeurs de 2 et 3 sont inférieur à c_x). Ensuite, 3 et 1. Au dernier, 1 et 4. – Fihop

Trier les verticalement, connectez 2 plus haut sommet les uns aux autres et deux plus bas les uns aux autres.
Triez horizontalement, puis connectez les 2 les plus à gauche les uns aux autres et les deux les plus à droite les uns aux autres.

EDIT: de toute façon, est SO section correspondante fraîche sur la droite suggère une double réponse: Sort Four Points in Clockwise Order

Source

2010-08-06 23:58:47

que si deux les plus à gauche sont les mêmes que les deux plus haut –

cela échoue en effet sur une forme de base de diamant – mvds

ok, prendre deux plus haut, puis sélectionnez le plus à gauche de différentes paires. La forme des losanges est désambiguïsée en disant que s'il y a deux points sur le même niveau vertical, les gains les plus à gauche. Je pense que la solution de mvds est meilleure mais je ne la comprends pas complètement. –

Comment lier quatre points à un polygone convexe

Répondre

Questions connexes