calculer l'intersection entre deux segments de manière symétrique

Lorsque vous utilisez les formules habituelles pour calculer l'intersection entre deux segments 2D, soit here, si vous arrondissez le résultat à un entier, vous obtenez des résultats non symétriques. C'est-à-dire, parfois, en raison d'erreurs d'arrondi, je reçois intersection(A,B)!=intersection(B,A).calculer l'intersection entre deux segments de manière symétrique

La meilleure solution est de continuer à travailler avec des flotteurs, et de comparer les résultats jusqu'à une certaine précision. Cependant, je dois arrondir les résultats aux entiers après avoir calculé l'intersection, je ne peux pas continuer à travailler avec des flotteurs.

Ma meilleure solution jusqu'ici était d'utiliser un peu d'ordre sur les segments dans le plan, et j'ai intersection pour toujours comparer le plus petit segment au plus grand segment.

Existe-t-il une meilleure méthode? Est-ce que je manque quelque chose?

Source

2010-04-11 Elazar Leibovich

Quel est le motif que vous pouvez » t utiliser, disons, symmetricIntersection (A, B) = (intersection (A, B) + intersection (B, A))/2? L'addition à virgule flottante est commutative. – brainjam

@brainjam, c'est vraiment sympa et mathématiquement solide, mais cela nécessite de calculer l'intersection deux fois, et de me fier à l'arrondi à virgule flottante, donc je ne suis pas sûr que ce soit mieux que de commander sur des segments. Quoi qu'il en soit, bravo! Aimé. –

@brainjam, une fois qu'une erreur se glisse, toute opération peut amplifier l'erreur. Donc, si déjà en comparant 'X' ==' Y' est sorti faux, 'X' ==' (X + Y)/2' sera probablement aussi faux. De plus, dans les cas où 'X' ==' Y' pourrait être vrai, 'X' ==' (X + Y)/2' peut être faux (par exemple quand 'X' et' Y' peuvent être représentés sans erreur, mais «X + Y» ne peut plus être représenté sans erreur.) – vladr

Vous ne souhaitez pas comparer les longueurs de segments.

Aussi, je suppose que lorsque l'on compare intersection(A',B')-intersection(B",A") il est entendu que A' « s sont coordonnées representationally identique àA" » s (idem pour B' et B"), ou bien il n'y a pas de solution.

Cela dit, tenez compte des segments [PQ] et [RS], où P, Q, R et S sont des points dans le plan. Vous voulez que les intersections des segments:

[PQ][RS]
[QP][RS]
[PQ][SR]
[QP][SR]
[RS][PQ]
[SR][PQ]
[RS][QP]
[SR][QP]

... pour revenir toujours la même paire de coordonnées.

commande, le premier des points d'extrémité sur chaque segment, puis des segments eux-mêmes (sur la base de chaque segment de point de terminaison de moins), est la seule solution qui garantit des résultats reproductibles. L'ordre lui-même peut être informatiquement trivial, par ex. P<Q ssi P.x < Q.x || P.x == Q.x && P.y < Q.y, bien que la ramification pourrait coûter cher si le traitement avec des millions de segments (voir comment vous pouvez utiliser SIMD pour segmenter échanger des coordonnées en place, si possible, pour générer la commande.)

Source

2010-04-11 05:50:06 vladr

Merci, c'est ce que j'ai pensé. Cependant, s'il y avait une méthode qui choisissait toujours le chemin de calcul qui donnait le moins d'erreur de précision, cela serait symétrique et réduirait l'erreur de précision. Peut-être que ce n'est pas possible de le faire. –

@Vlad, vous commencez par "Vous ne voulez pas comparer les longueurs de segments". Pourquoi dites vous cela? Est-ce le coût de calcul, ou autre chose? – brainjam

@brainjam, alors que je ne peux pas parler pour Vlad, je pense qu'il ne veut pas la précision perdue et le coût de calcul de la fonction racine carrée. –

calculer l'intersection entre deux segments de manière symétrique

Répondre

Questions connexes