C'est en effet la meilleure méthode. Surtout que pour optimiser on peut prendre une demi-droite horizontale ou verticale, au choix, ce qui allège énormément les calculs (pas de division, très peu de multiplications).
Choisis une des quatre demi-droites possibles (vers le haut, le bas, la droite, la gauche). Mettons que tu prennes celle partant vers la droite. Pour chaque côté [AB], regarder s'il y a intersection revient alors à :
- si A et B sont tous deux au-dessus de la droite, ou tous deux en-dessous, alors il n'y a pas intersection. Il suffit ici de calculer ((yB - yDroite)> 0) XOR (yA - yDroite)> 0). Le CPU est heureux.
- sinon, il faut calculer l'intersection avec la droite. En posant et transformant l'inégalité (xIntersection> 0) tu te débarrasses du dénominateur, donc de la division. Tu te retrouves donc avec le calcul de quelques multiplications et additions.
Tu refais la même chose pour tous les côtés (ici quatre, mais ça vaut pour n'importe quel polygone), ce qui permet de compter le nombre d'intersections et donc de répondre à ta question.
[^] # Re: question de math,
Posté par Moby-Dik . En réponse au journal question de math,. Évalué à 4.
Choisis une des quatre demi-droites possibles (vers le haut, le bas, la droite, la gauche). Mettons que tu prennes celle partant vers la droite. Pour chaque côté [AB], regarder s'il y a intersection revient alors à :
- si A et B sont tous deux au-dessus de la droite, ou tous deux en-dessous, alors il n'y a pas intersection. Il suffit ici de calculer ((yB - yDroite)> 0) XOR (yA - yDroite)> 0). Le CPU est heureux.
- sinon, il faut calculer l'intersection avec la droite. En posant et transformant l'inégalité (xIntersection> 0) tu te débarrasses du dénominateur, donc de la division. Tu te retrouves donc avec le calcul de quelques multiplications et additions.
Tu refais la même chose pour tous les côtés (ici quatre, mais ça vaut pour n'importe quel polygone), ce qui permet de compter le nombre d'intersections et donc de répondre à ta question.