1

Tout est dans le titre...
On connait bien sur les coordonnées des points du polygone et du point à tester.
C pour un moteur de collision d'objets vectoriels
Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

2

Soit z0 l'affixe du point à tester. Tu intègres 1/(2 pi i (z-z0)) le long de la courbe parcourant le polygône. Si le point est à l'intérieur, l'intégrale vaut 1 ou -1 (selon l'orientation choisie), sinon elle vaut 0.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

3

C'est à dire ???
Je me rappelle plus comment on intègre en complexe.
Si il y avait plus simple (algorithmiquement) ce serait cool.
Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

4

Tu intègres 1/(z-z0) le long d'un segment qui ne passe pas par z0 (Si z0 est exactement sur un de tes segments, tu auras un problème. sad Il faudra vérifier ça séparément.) à peu près de la même manière que tu le ferais sur |R: ln(z-z0), où ln est le logarithme complexe, mais attention, il faut choisir une branche continue sur le segment.

On peut simplifier le tout: on sait que le résultat est réel (-1, 0 ou 1). On multiplie tous les logarithmes par 1/(2 pi i), donc on n'a besoin que de leur partie imaginaire. Donc il suffit d'étudier les arguments.

Bref, ton intégrale vaut la somme des arg(z2-z0)-arg(z1-z0) pour tous les segments [z1,z2] du polygône. Reste à savoir quels arguments choisir. Le choix correct est de faire en sorte que -pi<arg(z2-z0)-arg(z1-z0)<pi. Si ta différence d'arguments est plus grande que pi en valeur absolue, tu as choisi la mauvaise branche du logarithme. Si elle est égale à pi, alors z0 est sur [z1,z2], et ton point est donc sur le polygône.

Si la somme vaut 0, ton point est à l'extérieur, si elle vaut ± 2 pi, il est à l'intérieur.

Bon, là, je pense que tu as un algorithme bien concret pour résoudre ton problème. Mais je ne sais pas s'il est optimal.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

5

en 2D ou en 3D?
polygone complexe? polygone concave? polygone convexe? triangle?
In many respects the Yoshi is like a beautiful woman. A man can come so enamoured that he bestows on her all his time, his energy and his fortune.
- Fred whipple, 1960

*** Ne sous-estimez pas la puissance de la Marmotte ***
© Marmotte Team : LaMarmotte, sBibi, Vark & Sabrina

6

sbibi > en 2D. polygone quelconque.

kevin > ta méthode est géniale mais elle a un défaut : elle fait intervenir les flottants (problème de rapidité et de précision des calculs). Sinon je pense que je vais la garder.
Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

7

polygone quelconque ca veut rien dire, c'est c'est un polygone complexe ca complique enormement... et je pense pas que la methode de kevin marche pour les polygones complexes (elle marche pour les polys concaves? g pas trop compris triso)
mais l'histoire d'angles me fait vite fait penser a une methode ou tu somme les angles formes par chacun des points du polygone avec ton point, si elle est egale a 2PI c'est a l'interieur, sinon c'est a l'exterieur (et la somme des angles vaut 0) (d'ailleurs c'est peut etre la meme methode, sauf que je trouve ton explication mathematique incomprehensible...)

et on peut y arriver en raisonnant logiquement et en se faisant un schema sur papier sans avoir besoin de la moindre integrale ou autres... (si c'est bien la mm methode dont on parle hein..)
In many respects the Yoshi is like a beautiful woman. A man can come so enamoured that he bestows on her all his time, his energy and his fortune.
- Fred whipple, 1960

*** Ne sous-estimez pas la puissance de la Marmotte ***
© Marmotte Team : LaMarmotte, sBibi, Vark & Sabrina

8

Ma méthode devrait marcher pour n'importe quel polygône non-croisé (c'est-à-dire où les segments délimitants ne se coupent pas). Même concave. (Pour des polygônes croisés, il y a des cas où ça marche et d'autres où il y peut y avoir un problème.)
sBibi
: mais l'histoire d'angles me fait vite fait penser a une methode ou tu somme les angles formes par chacun des points du polygone avec ton point, si elle est egale a 2PI c'est a l'interieur, sinon c'est a l'exterieur (et la somme des angles vaut 0) (d'ailleurs c'est peut etre la meme methode, sauf que je trouve ton explication mathematique incomprehensible...)

C'est la même. arg(z2-z0)-arg(z1-z0) n'est l'autre que "l'angle formé par les points du polygône avec ton point", et le choix de la valeur que j'ai décrit (-pi<...<pi) revient à choisir l'angle géométrique orienté (attention... sans ça ta méthode est fausse). Et comme il faut sommer des angles orientés, on peut aussi se retrouver avec -2pi selon l'orientation choisie.
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

9

"Ma méthode devrait marcher pour n'importe quel polygône non-croisé (c'est-à-dire où les segments délimitants ne se coupent pas)."

oui, donc pas les polygones complexes...

"revient à choisir l'angle géométrique orienté" -> oui dsl, j'ai pas precise ca vu que g l'habitude que tous les points des polygones soient orientes (pour le backface culling, bref...)

bon ben ok alors c la meme triso
In many respects the Yoshi is like a beautiful woman. A man can come so enamoured that he bestows on her all his time, his energy and his fortune.
- Fred whipple, 1960

*** Ne sous-estimez pas la puissance de la Marmotte ***
© Marmotte Team : LaMarmotte, sBibi, Vark & Sabrina

10

en javascript, (mais si tu prefères le VB, ça vient de là) :
IsPtInPoly = function(Ax,Ay, index,nb)
{
var lCrossings = 0

for(var lLoopCtrl = 0; lLoopCtrl < nb; )
{
var Xl = Pt2D_x[index+lLoopCtrl] //on prend le point courant comme 1er point
var Yl = Pt2D_y[index+lLoopCtrl]

if(!(lLoopCtrl + 1 > nb - 1))//si le point n'est pas le dernier
{
var Xr = Pt2D_x[index+lLoopCtrl + 1]//on prend le point suivant comme 2eme point
var Yr = Pt2D_y[index+lLoopCtrl + 1]
}
else //sinon on prend le 1er point comme 2eme point
{
Xr = Pt2D_x[index]
Yr = Pt2D_y[index]
}

if((Xl < Ax) && (Xr < Ax)) { lLoopCtrl++; continue }
if((Xl > Ax) && (Xr > Ax)) { lLoopCtrl++; continue }
if((Yl < Ay) && (Yr < Ay)) { lLoopCtrl++; continue }

if(((Yl > Ay) && (Yr > Ay)) && ((Xl > Ax) || (Xr > Ax)))
{
lCrossings++//croise le polygone 1X
lLoopCtrl++
continue
}
//If it makes it to here then it is in the MBR of the segment
//We need to test and see which pt is further left in case this was drawn ctr clockwise.
if(Xl > Xr)
{
var temp = Xl
Xl = Xr
Xr = temp
temp = Yl
Yl = Yr
Yr = temp
}

var Yc = Yl + (((Yr - Yl) / (Xr - Xl)) * (Ax - Xl))
if(Yc > Ay) lCrossings++//croise le polygone 1X
lLoopCtrl++
}

if((lCrossings % 2) != 0) return true//si le demi-segment croise le polygone un nombre paire de fois
else return false }