C floats: comment les contourner pour la géométrie 2D (lignes)

Question

Je fais actuellement de la géométrie 2D en C, la plupart du temps des lignes se croisant. Ces lignes ont toutes sortes de pentes: de 0,001 à 1000 (exemples, je ne sais même pas). J'utilisais des flottants jusqu'à maintenant et je n'avais pas à m'inquiéter de savoir si la valeur était très petite (et alors le point flottant stockerait 0,0011 comme 1e-3 sans arrondi) ou très haut (et alors 1001 serait stocké comme 1e3), avec dans les deux cas peu de perte de précision, le cas échéant.

Mais maintenant je veux essayer sans flottants, avec des entiers. Comment maintenir la précision dans mes calculs? Je pourrais avoir un drapeau me disant si la pente sera grande ou petite et ensuite considérer un dixième de grandes pentes et dix fois de petites pentes pour que l'arrondi ne soit pas un problème pour les petites pentes et il n'y a pas de débordement dans le cas de grandes pentes . Mais cela ressemble à un mal de tête. Fondamentalement, je dois encore être capable de différencier entre une pente de 0,2 et 0,4 et aussi sur le côté de débordement des choses une pente de 1000 et 2000 (en supposant que ints débordent à 1000 - moins d'un problème ici).

D'autres idées?

Answer 1

magasin la pente comme une paire d'entiers

struct slope { 
    int delta_y; 
    int delta_x; 
}; 

Cela permet un large éventail de pistes comme 0 et +/- 1/INT_MAX ... +/- INT_MAX, même verticale. Avec un codage soigneux, des calculs précis peuvent être effectués.

Crédit de Tardy: Cela ressemble beaucoup à @Ignacio Vazquez-Abrams comment.

Answer 2

Rechercher fixed point arithmetic si vous souhaitez utiliser int de manière générale.

Vous pouvez également concevoir vos algorithmes de sorte que vous fassiez tous les calculs de manière à ce que vous n'ayez pas besoin de précision infra-integer (par exemple, recherchez les algorithmes de dessin Bresenham's line et circle).

Pour votre problème particulier, vous pouvez essayer de garder le quotient et la fraction séparément, en d'autres termes utiliser des nombres rationnels. Ou autrement dit, avoir delta X et delta Y comme deux nombres.

Answer 3

De manière générale, avec des lignes d'orientation arbitraire, il n'est pas recommandé de travailler avec la représentation pente/interception y = mx + p, mais avec l'équation implicite a x + b y + c = 0. Ce dernier est plus isotrope, supporte les lignes verticales et vous donne une flexibilité supplémentaire pour mettre à l'échelle les coefficients. de

Meeting @ chux réponse, les coefficients peuvent être les deltas, (en supposant que les lignes sont définies par deux points, Dx et Dy sont susceptibles de ne pas trop-plein). Le débordement est toujours possible sur c et vous pouvez utiliser la variante Dy (x - x0) - Dx (y - y0) = 0. Quoi qu'il en soit, les calculs intermédiaires tels que les intersections peuvent nécessiter des plages plus grandes, c'est-à-dire des entiers de longueur double. L'idée de marquer la valeur grande/faible est un peu contre-productive: c'est en fait une manière primitive de faire un point flottant, c'est-à-dire de séparer l'échelle de la mantisse. En travaillant de cette façon, vous allez en quelque sorte re-concevoir un système de point de pouls, moins puissant que le type intégré et vous coûter de la sueur et des larmes.

---

Malheureusement, l'arithmétique à haute portée ne peut pas être évitée. En effet, l'intersection de deux lignes droites est donnée par la Cramer formules

x = (c b' - c' b)/(a b' - a' b), 
y = (a c' - a' c)/(a b' - a' b) 

où les produits à évaluer sont un ordre de grandeur plus grand que les coefficients initiaux. Ceci s'explique par le fait que les lignes quasi parallèles ont des intersections lointaines.