[Gridflow-dev] polygon comparator (fwd)

[Mathieu Bouchard]

Hey, some cool news: there are now four more polygon-related classes in 
GridFlow:

[#polygon_each_edge] - outputs N grids of size 2x2 representing each edge 
in the polygon which is a grid of size Nx2.

[#polygon_moment] - finds the centroïd of a polygon (without rendering 
it).

[#polygon_radial_map] - renders a 1-D panorama from a polygon

[#polygon_comparator] - finds similarities in two polygons using those 
panoramas, and finds the optimal rotations for aligning the polygons.

Note that the last of those classes depends on [#fft], so you need 
libfftw. None of those classes depend on ltilib.

I developed the technique for comparing polygons by myself, and I'm afraid 
that this might be original research...

This supplements the other polygon-related classes,
   [#polygon_perimetre]
   [#polygon_area]
   [#draw_polygon]
   [#edit_polygon] (unfinished)
   [#draw_rect]    (unfinished)

---------- Forwarded message ----------
Date: Sat, 7 Oct 2006 10:57:03 -0400 (EDT)
From: Mathieu Bouchard <matju at artengine.ca>
To: Alexandre Castonguay <acastonguay at artengine.ca>
Cc: heri at artengine.ca
Subject: Re: polygon comparator

On Sat, 7 Oct 2006, Alexandre Castonguay wrote:

> Je viens d'essayer [#polygon_comparator] en passant deux grilles de 
> dimensions differentes mais je n'obtiens pas de sortie.

Il faut envoyer le polygon deux fois dans l'inlet de droite. C'est pas supposé, 
c'est un bug de séquençage, mais j'ai pas le temps de chercher maintenant.

Ensuite tu peux ouvrir la patch pour voir le data sous forme d'array pd, ou 
encore tu peux le prendre sous forme de grid float32 à l'outlet. J'avais pensé 
mettre un outlet plus simple avec juste un nombre de 0 à 1 mais je suis pas sûr 
de ce que je devrais faire.

Ensuite tu dois savoir qu'il y a une distinction entre les polygones horaires 
et anti-horaires (ce n'est pas une caractéristique vraiment du polygone, mais 
plutôt de sa liste de points). Le sens est appelé positif ou négatif 
dépendemment du signe du résultat de [#polygon_area]. Lequel est le sens 
horaire, dépend des axes. Le résultat de [#polygon_radial_map] va être négatif 
si tu vas dans le sens négatif. Le résultat de [#polygon_comparator] va être 
négatif si le sens des deux polygones est différent.

Ensuite, dans la grille il va y avoir un peak. Tu peux trouver sa hauteur avec 
[# abs-] [#fold max]. Si c'est 1, les deux polygones sont égaux. Ça prend des 
polygones très différents ou décentrés pour donner des valeurs vraiment basses.

L'endroit où le peak est dans la grille va te donner l'angle de rotation qui 
alignerait les deux formes optimalement.

S'il y a plusieurs peaks de même hauteur c'est à cause de symétrie: pour un 
triangle équilatéral et un carré ça donne 12 peaks pcq le ppcm de 3 et 4 est 
12; ça veut dire qu'il y a 12 rotations possibles qui alignent ces deux formes 
optimalement. (Note que pour bien voir il faut zoomer les valeurs pcq elles 
sont toutes entre 0.97 et 0.98 pour cet exemple.)

> Est-ce que ce cas est permis? J'essaie de figurer comment l'utiliser.

Oui, les polygones à nombres de sommets différents sont permis, c'était dans 
mon design dès le début. [#polygon_radial_map] enlève toute notion de nombre de 
sommets lors de sa transformation (qui est une forme de rendering).

On Sat, 7 Oct 2006, Alexandre Castonguay wrote:

> L'as-tu essaye avec les polys que j'ai prepare, et est-ce qu'on a des 
> resultats negatifs avec ceux qui ne sont pas des matches et positifs avec les 
> autres?

C'est plutôt des résultats proches de 1.0 ou de -1.0 quand les polygones sont 
identiques, et des résultats un peu plus loin quand ils ne le sont pas. Ça 
prend des polygones très différents pour obtenir des nombres "proches" de 0: 
par exemple un très mince avec un très rond.

Note que les polygones doivent avoir leur centroïde = 0 pour être bien 
comparables.

  _ _ __ ___ _____ ________ _____________ _____________________ ...
| Mathieu Bouchard - tél:+1.514.383.3801 - http://artengine.ca/matju
| Freelance Digital Arts Engineer, Montréal QC Canada