Le topic de la programmation: Et envoyez des sioux!

[Cwningen]

Tant qu'à écrire des équations, allons-y franchement.

J'ai deux façons pratiques pour décrire une droite qui me viennent à l'esprit :

• Avec un vecteur directeur (v) et un point de la droite (A), on définit les points de la droite en fonction du paramètre t : P(t) = A + t v
• Avec un vecteur normal (n) et un point de la droite (A), et on retrouve l'équation de droite OP.n = OA.n. (pour reprendre les lettres de mon post précédent, OP c'est le vecteur (x, y), n c'est le vecteur (a, b), OA.n c'est -c)

Dans ton cas, il me semble plus simple d'utiliser la première pour la droite grise, et la seconde pour la droite noire (pour avoir le vecteur normal, mais on peut facilement le retrouver à partir du vecteur directeur).

Le produit scalaire avec le vecteur normal unitaire permet de calculer la distance à la droite, donc pour un point B de la droite noire, on cherche t, tel que BP(t).n = 5px (ou -5px si le vecteur normal pointe de l'autre coté), tu développes ça (BP(t).n = (BA + t v).n = BA.n + t v.n), tu obtient une équation linéaire facile à résoudre (t = (5 - BA.n)/v.n, v.n est nul quand les deux droites sont parallèles).

À noter que en 3D, la première équation décrit toujours une droite, mais la seconde décrira un plan. Mais en 3D tu chercherais sûrement l'intersection d'une droite avec un plan, donc le raisonnement tient toujours.

[Anonyme20240202]

Nan nan c'est 2 représentations de la même chose oh, monsieur non mais.

a.x + b.y + c = 0 <=> y = (-a/b).x + (-c/b) <=> y = m.x + p

D'ailleurs (et je dis pas ça pour toi), mais la forme a.x + b.y + c = 0 est très mauvaise d'un point de vue pédagogique car il n'y a pas de correspondance visuelle simple entre coefficient et rendu visuel.

m.x + p = y ça veut dire que si tu bouges m la droite tourne, si tu bouges p la droite se décale, c'est simple à comprendre, tu peux voir les translations et autres opérations géométriques.

a.x + b.y + c = 0 c'est compliqué (j'exagère hein)

Si je te dis on passe de 2x + 3y + 1 = 0 à 3x + 2y + 1 = 0, est ce que tu es capable de me dire immédiatement à quelle transition géométrique ça correspond

Alors que si je dis on passe de 2x + 1 = y à 3x + 1 = y, visuellement tu vois direct

[Tramb]

a.x + b.y + c = 0 <=> y = (-a/b).x + (-c/b) <=> y = m.x + p

D'ailleurs (et je dis pas ça pour toi), mais la forme a.x + b.y + c = 0 est très mauvaise d'un point de vue pédagogique car il n'y a pas de correspondance visuelle simple entre coefficient et rendu visuel.

Mais elle évite des divisions par 0, y a pas équivalence si b == 0, donc la première forme est plus versatile.

[Anonyme20240202]

Je sais je sais, j'essaye de rester simple!

On pourra faire une thèse sur les avantages calculatoires et en terme de lisibilité de tous les moyens qu'on a de représenter une droite

[Cwningen]

D'ailleurs (et je dis pas ça pour toi), mais la forme a.x + b.y + c = 0 est très mauvaise d'un point de vue pédagogique car il n'y a pas de correspondance visuelle simple entre coefficient et rendu visuel.

Si, comme je l'ai dit dans le post que j'ai posté en même temps, (a, b) est un vecteur normal, c est une sorte de "distance signée" à l'origine (comptée en longueurs de (a, b)).

[Anonyme20240202]

Ouais dit comme un vecteur ça passe mieux, j'aime pas trop cette forme générale en équation

Je suis traumatisé par les profs qui introduisent la forme générale sans expliquer

[Awake]

Merci pour vos réponses. Je suis complètement KO mais je regarderais et ferais des tests demain.

J'aurais du préciser le format de mes données : tout est en points au format { x: float, y: float }. Un segment comme le mur est juste deux points dans ce format là, pareil pour le reste. Je galère un peu à suivre vos infos avec des droites à partir de ax+b puisque ce n'est pas du tout le paradigme que j'utilise.

[Lazyjoe]

Tu devrais générer quelques milliers de configuration différentes, mesurer chaque solution à la main avec une règle, et donner toutes ces données à un algo de deep learning.
Tu devrais facilement générer un réseau neuronal avec 90% de reconnaissance correcte.

[Cwningen]

Merci pour vos réponses. Je suis complètement KO mais je regarderais et ferais des tests demain.

J'aurais du préciser le format de mes données : tout est en points au format { x: float, y: float }. Un segment comme le mur est juste deux points dans ce format là, pareil pour le reste. Je galère un peu à suivre vos infos avec des droites à partir de ax+b puisque ce n'est pas du tout le paradigme que j'utilise.

Si tu as deux points A (x, y) et B (x', y'), le vecteur AB (x'-x, y'-y) est un vecteur directeur de la droite. Pour avoir un vecteur normal, tu prends le vecteur directeur et tu le tournes de 90°. Tourner de 90° en 2D c'est très simple, tu échanges les deux coordonnées et tu en opposes une ((x, y) devient (y, -x) ou (-y, x)). Je parlais aussi de vecteur unitaire, c'est à dire de longueur 1, il suffit de diviser chaque coordonnées du vecteur par sa longueur √(x² + y²).

[Anonyme20240202]

Merci pour vos réponses. Je suis complètement KO mais je regarderais et ferais des tests demain.

J'aurais du préciser le format de mes données : tout est en points au format { x: float, y: float }. Un segment comme le mur est juste deux points dans ce format là, pareil pour le reste. Je galère un peu à suivre vos infos avec des droites à partir de ax+b puisque ce n'est pas du tout le paradigme que j'utilise.

C'est important que tu fasses des exemples à la main tout seul, tu vas piger tout de suite et tu gagneras l'intuition visuelle, tu peux relire mon post du dessus.

Faut que tu piges qu'une droite c'est un ensemble de point, donc si tu veux dessiner une droite, disons pixel par pixel. Il va falloir dessiner chaque point. Disons que la droite est noire, comment tu sais si tu dois peindre le pixel en noir? S'il appartient à la droite.
Comment on définit une droite? C'est le chemin le plus court entre 2 points, donc comment on avance au pixel suivant? En croissant au même rythme que la droite.

Rumine ça et ça te viendra. Tu peux penser en terme de grille si tu veux (espace discret), si t'as pas le droit de faire de diagonale, comment tu relies 2 points, tu fais un coup à droite, un coup vers le haut, un coup à droite, un coup vers le haut. Mais si c'est très penché faudra faire 2 coups vers le haut, 1 coups à droite, 2 coups vers le haut, 1 coup à droite, etc.

Version en réutilisant ton propre code

Tu nous as dit que tu avais déjà une fonction de détection de collision (point rouge). En imaginant que la signature c'est:

collision(segment_1, segment_2) -> point_collision { x, y }

Il te suffit de créer le segment_3 qui est décalé de 5px du segment_1

et ensuite collision(segment_3, segment_2)

Comment on décale de 5px pour obtenir segment 3? J'explique ci dessous

Point A { x1, y1 } <- (2, 1) dans l'exemple
Point B { x2, y2 } <- (3, 2) dans l'exemple

https://www.desmos.com/calculator/ekalgpvyu8

Donc si on veut appartenir à la droite définie par ces deux points, comment on vérifie ça?

Point C { x, y } <- n'importe quel point

Il faut que l'incrément de croissance qui t'amène de A vers B ou de A vers C ou de C vers A, etc. soit le même. Quand tu traces une droite chaque point respecte la même progression, y'a pas de virage.

Donc la progression de A vers B c'est

y2 - y1 "de combien de cases je monte"
x2 - x1 "de combien de cases je vais à droite"

Et ce qu'on veut c'est "de combien de cases je monte" à chaque fois qu'on va vers la droite, donc si je vais à droite, de combien je monte pour rester sur ma droite.

On appelle ça le coefficient directeur: (y2 - y1) / (x2 - x1)

Le coefficient directeur, une division, un ratio donc, est souvent noté "m"



Donc si C appartient à la droite il faudra que (y - y1) / (x - x1) = (y2 - y1) / (y2 - y1) soit vrai, même coefficient directeur, même "croissance"/taux de progression

On applique le même raisonnement si on veut définir une droite dans un espace avec une courbature (compliqué tout ça). Tout ça pour dire que bien que ça paraisse peut être un peu bateau et exagéré, c'est le raisonnement à suivre et qui s'applique partout.

L'équation ("ensemble des points appartenant à la droite respecte:") de ma droite c'est tous les points { x, y }, tel que "la progression soit la même":

(y - y1) / (x - x1) = (y2 - y1) / (x2 - x1)

Que tu peux ré-écrire

y = ((y2 - y1).(x - x1) / (x2 - x1) + y1
y = (y2.x - y2.x1 - y1.x + y1.x1) / (x2 - x1) + y1
y = x.(y2 - y1)/(x2 - x1) + x1(y1 - y2)/(x2 - x1) + y1
y = x.m + b

Dans notre exemple

y = x.(2 - 1)/(3 - 2) + 2(1 - 2)/(3 - 2) + 1
y = x - 1

https://www.desmos.com/calculator/i5k2lzttor

Et le truc c'est que tu peux noter y = x - 1 autrement

Si on fait tout passer d'un côté on obtient la "forme générale"

x - y - 1 = 0

https://www.desmos.com/calculator/nykt5nbm9b

Que tu peux aussi voir comme le vecteur unitaire (1, 1) qui est décalé d'un cran vers le bas.

Maintenant comment j'obtiens une droite décalée de 5 px? Très simple

y = x - 1

Si je décale d'un cran vers le haut

y = x - 1 + 1
y = x

si je décale d'un cran vers le bas

y = x - 1 - 1
y = x - 2

https://www.desmos.com/calculator/406gzqkwcc

Donc tu peux faire le va et vient entre les différentes représentations d'une droite, via 2 points et via la formule avec le coefficient directeur.

https://www.desmos.com/calculator/wch4ma26dd

Version équation

De manière générale pour calcule la distance d'un point à une droite on utilise ça: https://fr.wikipedia.org/wiki/Distan...%A0_une_droite



Je passe la preuve, mais en gros c'est pythagore, tu peux avoir une intuition en comprenant que pour aller de A vers B il faut faire une diagonale (un coup vers la droite, un coup vers le haut, un coup vers la droite, etc...)



Donc maintenant, tu sais que ton point appartient à une droite (ou un segment, un segment c'est comme une droite mais avec une limite pour x et y)
y = m.x + p

Et tu sais qu'il est à une distance de 5 px d'une autre droite

5 = ((x2 - x1)(y1 - y) - (x1 - x)(y2 - y1)) / sqrt((x2 - x1)² + (y2 - y1)²)

Tu as 2 équations et 2 inconnues, tu trouveras ton (tes) points en resolvant ce système, tu cherches x et y qui satisfont ces équations, le point vert { x, y }.

Pour résoudre le système tu peux remplacer y par sa valeur (m.x + p)

- - - Mise à jour - - -

Et sinon pour terminer. Dans mon post initial, mes délires de "tu peux le faire avec une boucle for/while", j'évoque des algos de ce genre, que tu pourrais programmer par toi même à coup sûr, sans avoir à réflechir en terme de notations mathématiques

[Cwningen]

Je crois que les profs de maths de Kamikaze vont également me traumatiser.

[Shinosha]

Moi qui passe sur le topic en espérant que ça parle d'autre chose que de trucs bas niveau pour une fois

[war-p]

Je crois surtout que kamikaze s'est trompé de topic

[Tramb]

Tu devrais générer quelques milliers de configuration différentes, mesurer chaque solution à la main avec une règle, et donner toutes ces données à un algo de deep learning.
Tu devrais facilement générer un réseau neuronal avec 90% de reconnaissance correcte.

C'est moche ce que tu fais. Moche et cruel.
Et drôle et vrai.

[rOut]

Bonjour à tous,

Je viens quemander un peu d'aide sur un soucis plus mathématique que de programmation, si quelqu'un à un peu de temps pour m'aider. Je serais bien allé demandé sur le topic des maths mais ils m'auraient donné des equations que j'aurais été incapable de transformer en code. Je pense que le problème est très simple, mais je n'ai pas le bagage scolaire pour pouvoir le résoudre .

https://cdn.discordapp.com/attachmen...vector-cpc.png

Il y a un système de collision entre deux segments (les lignes grises et noires). Le segment noire représente un mur, le segment gris est la trajectoire que fait le point (=son déplacement) qui ne doit pas traverser le mur. Le point rouge celui ou les deux segment se rencontrent (point de collision). Le point bleu est celui que le point avait avant le déplacement.

J'aimerais trouver les coordonnées du point vert, qui devrait être le long du segment gris ( = le déplacement du point), mais à une distance de 5 du mur, et perpendiculaire à celui-ci.

Il faut que si la collision se fait à partir de l'autre côté du mur (si le point bleu est au nord du mur), le point vert soit bien entendu au nord aussi.

Sachant que j'ai déjà le code fonctionnel pour trouver le point rouge, c'est vraiment juste le calcul du point vert qui pose problème.

Désolé de venir avec un soucis aussi simple et concret mais je galère là dessus bien comme il faut

Bah sinon tu décales ton mur de 5px du coté qui t'intéresse et puis tu fais ton truc pour trouver le point rouge sur ce nouveau mur. Voilà.

[Nilsou]

Moi qui passe sur le topic en espérant que ça parle d'autre chose que de trucs bas niveau pour une fois

https://c.tenor.com/QpE0PLZiQEUAAAAC...-by-50cent.gif

Je ne sais pas si on peut parler de bas niveau pour la distance d'un point à une droite

[Anonyme20240202]

Bah sinon tu décales ton mur de 5px du coté qui t'intéresse et puis tu fais ton truc pour trouver le point rouge sur ce nouveau mur. Voilà.

Ouais, c'est la première réponse que j'ai donné, mais les vilains canards se moquent de mes posts plein d'amour

- - - Mise à jour - - -

J'ai développé en détail parce que si tu choppes pas le cheminement type, le raisonnement pour ce genre de problème, tu seras au même point une fois confronté au problème suivant

Genre passage en 3D, collisions de polygones, prise en compte de la vélocité et j'en passe

[Teocali]

Je ne sais pas si on peut parler de bas niveau pour la distance d'un point à une droite

Ben non, c'est des maths. C'est telllement haut niveau que y'a plus de code

[rOut]

Ouais, c'est la première réponse que j'ai donné, mais les vilains canards se moquent de mes posts plein d'amour

- - - Mise à jour - - -

J'ai développé en détail parce que si tu choppes pas le cheminement type, le raisonnement pour ce genre de problème, tu seras au même point une fois confronté au problème suivant

Genre passage en 3D, collisions de polygones, prise en compte de la vélocité et j'en passe

Bah certes mais le gars vient ici parce que les équations lui font peur et il se tape une tartine de maths en réponse.

[Awake]

Bon j'ai trop forcé ces derniers temps et je suis beaucoup trop éclaté pour pouvoir donner suite à ce problème. Heureusement je pars en vacances deux semaines et à mon retour je compte bien résoudre tout ça.

La solution de faire un segment parallèle à 5px et de recalculer la collision semble la plus simple pour l'instant.

En tout cas merci beaucoup pour toutes vos reponses (je m'attendais vraiment pas à ça), et plus spécialement à Kamikaze qui s'est vraiment cassé la tête pour donner des infos complètes.

[Anonyme20240202]

Nan nan y'a 0 math dans le premier post.
Dans le deuxième post y'a la réponse "classique" que la plupart des canards évoquent en utilisant uniquement les points sous forme { x, y }, tu peux copier coller l'équation à la fin directement dans le code sans la simplifier et ton code te donnera le fameux point vert.
Y'aura 2 points parce que y'a de la racine carré (on rappelle que racine(4) c'est 2 ou -2 grosso merdo), il faudra choisir le point du bon côté du mur. Obligé il va y arriver.

HEIN Awake, j'te mets pas la pression

Le truc que je suggère dans le premier post c'est qu'il fasse une implémentation brute, recherche dichotomique ou autre, sans équation. Voire même une boucle qui parcourt toute la droite. N'importe quoi, mais une solution qui fonctionne. Ca aide à se débloquer, bonne habitude à prendre.

Puis z'avez pas cliqué sur les liens, y'a que des dessins avec les équations correspondantes, c'est simple à comprendre

[GrandFather]

Et si on demandait à ce bon vieux Thalès ce qu'il en pense ?



Si BD et CE sont parallèles, alors (théorème de Thalès) BD/CE = AB/AC.

On connait BD, CE se calcule facilement (formule de la distance d'un point à une droite donnée par Kamikaze), on peut donc calculer le rapport K = BD/CE.

Pour obtenir les coordonnées du point B : Xb = (Xa + Xc) * K ; Yb = (Ya + Yc) * K

[Shinosha]

Salut les canards, j'ai besoin d'aide pour calculer la tangente de la fessée que Kamikaze va prendre sur SFVI

[Anonyme20240202]

Va d'abord falloir engager une brigade anti nuisible pour débarasser ton stick de la poussière et de la faune qui s'y sont développées

- - - Mise à jour - - -

Et si on demandait à ce bon vieux Thalès ce qu'il en pense ?
Si BD et CE sont parallèles, alors (théorème de Thalès) BD/CE = AB/AC.

On connait BD, CE se calcule facilement (formule de la distance d'un point à une droite donnée par Kamikaze), on peut donc calculer le rapport K = BD/CE.

Pour obtenir les coordonnées du point B : Xb = (Xa + Xc) * K ; Yb = (Ya + Yc) * K

Je comprends totalement la réponse mais blague à part, Thales c'est une solution ponctuelle s'pour ça que j'aime pas, si tu suis le raisonnement correct tu peux remplacer la droite par une courbe et ça fonctionnera encore. Tu peux te mettre en géométrie sphérique et le raisonnement tiendra encore, passer en 3D, introduire le temps/mouvement et le raisonnement tiendra encore, etc.

En 2D, dans ce cas simple, la contrainte c'est d'appartenir au segment et d'appartenir à l'ensemble des points à 5px de l'autre segment, ce qui est la définition d'une droite parallèle.

Si on passe à une courbe plutot qu'à un segment (déjà Thales ça marche plus) bah il faudra appartenir à la courbe et à l'aure ensemble, etc. Si on passe à une droite en géométrie non euclidienne il suffit de remplacer par l'équation correspondante et ça change rien.

Aussi contextuellement on voit bien qu'il est genre sur un moteur de jeu 2D ou autre, donc plus approprié d'avoir une brique réutilisable plutôt que "Thales".
D'ailleurs s'même pas Thales qu'a écrit ce théorème, c'est vraiment le pire théorème quelque part on apprend ça aux enfants sans réflechir à pourquoi.
Thales c'est plus de l'histoire des sciences qu'un théorème intéressant. Dans le contexte historique l'outil est intéressant et a du sens. Pour apprendre les maths c'est totalement obsolète.

En plus en programmation tu peux injecter des fonctions ou des ensembles etc., donc il pourrait même (avec du temps) arriver à un truc hyper généraliste du genre

collision<trajectoire, trajectoire>(t1, t2), où les trajectoires peuvent être des équations, des ensembles de points, etc., de dimension n, dans n'importe quelle géométrie, etc.

Je sais que je pars un peu loin mais le sujet de l'éducation me passione et je suis pas fan du cursus typique actuel où on enseigne des recettes de cuisine.

[Nilsou]

Après si c'est un truc qui doit tourner en boucle, le bon réflexe n'est-il pas de choisir la solution la plus efficace calculatoirement ? Et dans ce cas, amha, c'est certainement l’équation.

[Anonyme20240202]

Nope, ça va bien sûr dépendre du processeur et de tout un tas de variables. Par exemple est ce qu'on veut une valeur exacte ou approximative. Mais on rappelle que John Carmack s'est fait un nom avec sa fameuse optimisation de l'inverse de la racine carrée

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y;
i = 0x5f3759df - ( i >> 1 );
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) );
y = y * ( threehalfs - ( x2 * y * y ) );
return y;
}

Et c'est ce que je disais dans mon tout premier post en réponse à la question: le plus compliqué dans cette question c'est le contexte.

Si tu fais un simulateur de particules avec 10 millions d'entités, à coup sûr la solution avec l'équation sera pourrave en terme de performance et de toute façon tu ne voudras pas une solution exacte.
Genre si tu simules un nuage de poussière. Et il faudra prendre en compte les intéractions des particules entre elles, donc tu voudras souvent agglomérés les intéractions et simplifier car sinon c'est trop dur et sous optimal de considérer chaque particule isolée vis à vis de toutes les autres.

Si tu fais un jeu genre Mario qui saute et on veut pas qu'il traverse ou clip avec les murs, du coup distance de 5px, ça peut aller de résoudre l'équation.
Mais le calcul flottant sur les PC c'est toute une histoire.

Donc tout ça pour dire que c'est vraiment pas une question si simple et ça dépend vachement du cas d'utilisation.
Faut pas oublier qu'un écran de PC même haute résolution ça sert rarement de faire du calcul exact, t'as un pixel entier d'erreur (je simplifie) disponible, c'est discret

Si tu fais du calcul pour envoyer une fusée sur la Lune, il se peut que les équations soient exactes, mais instables, et tu préféreras peut être un truc plus lent d'un point de vue calculatoire, mais stable.

C'est quelque chose de très connu et ça a causé des catastrophe genre des missiles qui ratent leur cible etc.

On rappelle que la simple addition de 2 nombres à virgule n'est pas associatif en programmation par exemple, on est sur le topic de la prog, pas sur le topic des maths!

Donc tu ne peux pas avoir des considérations purement mathématiques ouais, il faut avoir ces considérations calculatoires, et je pense pas que la réponse soit simple.

J'peux pas le prouver en 2 minutes, mais je parierais bien qu'une simple recherche dichotomique serait potentiellement plus rapide qu'une implémentation naive de l'équation, particulièrement dans un espace discret

[Awake]

C'est une fonction qui va tourner jusqu'à 60 fois par seconde dans un browser (ordi ou mobile).

[GrandFather]

Pour apprendre les maths c'est totalement obsolète.

Thalès, c'est des maths, avec une démonstration formelle du théorème par Euclide. Je sais que la géométrie c'est has been, et que du coup on en arrive à la blague de Lazyjoe.

Maintenant, replaçons le contexte, je ne pense pas qu'il soit dans l'intention d'Awake de développer un moteur 2D/3D universel prenant en compte les espaces non-euclidiens, l'hygrométrie et l'âge du capitaine. Il a un problème simple pour lequel il demande une réponse simple, reposant sur les données dont il dispose (les coordonnées des points A et C, et celles des deux points extrémités d'un segment du mur). S'il y a plus direct que la solution à base de 3 calculs simples que j'ai donnée, je serai content de la connaître.

[Anonyme20240202]

Nan nan tu me méprends GrandFather, ta réponse y'a aucun problème, j'explique simplement pourquoi je développe et généralise, le prend pas mal haha
J'ai mis les pincettes en début de post en plus

Avec Thales t'arrives à la bonne réponse dans ce cas particulier y'a pas de problème, j'dis juste que si on modifie le problème légèrement tu te retrouves avec une solution obsolète dure à ré adapter.

Et si t'as pas la culture nécessaire, et que t'es confronté à un problème que tu connais pas (comme Thales), j'ai pas envie de dire "bah faut connaitre Thales"

Et ce que j'ai fait c'est de la géométrie hein, analytique mais géométrie quand même.

[GrandFather]

Ok, je range mes équerre et compas de combat.

Et si t'as pas la culture nécessaire, et que t'es confronté à un problème que tu connais pas (comme Thales), j'ai pas envie de dire "bah faut connaitre Thales"

Et pourtant, dans la catégorie de problèmes tels que celui exposé par Awake, conjointement avec Pythagore, de la trigonométrie, et deux ou trois autres théorèmes, tu te sors de la majorité des difficultés rencontrées, avec un code relativement simple et des connaissances de niveau Lycée grand maximum. Après, si ça se complique davantage, ou si les performances entrent en ligne de compte, il peut alors être effectivement intéressant de recourir à des algos spécialisés et optimisés. Mais la sur-ingénierie est une tentation contre laquelle il faut lutter.