Savoir si un point appartient plus ou moins à un segment

Edit important : la solution est donnée en fin de message

Bonjour à tous,

Je travaille sur un projet qui fait usage de formes géométriques et je suis amené à devoir être capable de dire si oui ou non un point donné appartient à un segment.

Appartenance d’un point à un segment

Je considère qu’un point appartient à un segment :

1. Si ses coordonnées appartiennent effectivement à ce dernier ;
2. Si ses coordonnées sont légèrement¹ distantes de ce segment (il y a donc une notion d’imprécision).

¹ : si un point est à une distance inférieure à 10 pixels du segment, je considère qu’il appartient au segment - sinon, non. Le "10 pixels" désigne une valeur pratique, mais évidemment il faut faire abstraction et considérer une constante maximal_allowed_distance = 10.

En résumé : vous aurez compris qu’il ne s’agit pas de dire si précisément un point appartient au segment, mais bien s’il appartient "plus ou moins" à celui-ci !

Quelques exemples

(NB : J’affirme, et nous en ferons l’hypothèse donc, qu’aucun point ne peut se superposer.) Si un point est situé sur le segment (ordonnée ET abscisse également à l’un des points de ce segment), il y appartient.

Si un point a la même ordonnée qu’un point du segment, mais une absisse très différente, il n’y appartient pas (+ ou - une distance > maximal_allowed_distance)

Si un point prolonge ce segment par l’une des extrémités de celui-ci, et qu’il n’est pas trop éloigné de l’extrémité adéquate (toujours en fonciton de maximal_allowed_distance), il y appartient.

etc.

Solution (qui ne marche pas)

NB important : le segment n’est pas forcément à l’horizontale, à la verticale. Effectivement, il peut très bien être penché.

L’idée est de détecter si un point est !!! LOIN !!! du segment.

Il s’agit de projeter le point-vecteur test que l’on veut tester (ie. : dont on veut savoir s’il appartient plus ou moins ou non au segment) sur le segment. Puis, partant du constat que tout point du segment est de la forme a + k(b-a) avec a : vecteur-point-extrémité et b : l’autre vecteur-point-extrémité, je travaille sur le coefficient linéaire k.

Donc si k < 0, je comparerais à maximal_allowed_distance la distance : test - a.

Si k > 1, ce sera test - b.

Et si k est compris entre [0;1], ce sera test - p.

Avec p : le point projeté sur le segment. p, comme toute projection de point, est défini par : p = ((x - a).(b - a))/((b - a).(b - a)) (b - a) + a.

J’ai cependant un gros souci avec cela : c’est que la plupart des points ne semblent pas être considérés comme étant éloignés du segment…

Screenshot illustrant une exécution

Comme vous pouvez le voir, mon code actuel considère qu’un point appartenant à un segment est éloigné de celui-ci… c’est évidemment un très gros problème… :

Pour le segment (1 ; 2 ; 0 ) - (1 ; 0 ; 0 ), le point (1 ; 1 ; 0) est considéré comme éloigné, alors qu’il y appartient…

Sources (ne marchent pas)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

    public static List<Point> getOnlyOnSegmentPoints(Point segment_first_point, Point segment_last_point, List<Point> points_to_test, double maximal_allowed_distance) {
        System.out.println("=== Segment : " + segment_first_point + " - " + segment_last_point);
        double segment_first_point_x = segment_first_point.getNumber(0);
        double segment_first_point_y = segment_first_point.getNumber(1);
        double segment_last_point_x = segment_last_point.getNumber(0);
        double segment_last_point_y = segment_last_point.getNumber(1);
        double test_x, test_y;
        double k_numerator, k_denominator;

        Point p;
        List<String> coords_p = new ArrayList<>();

        List<Point> returned = new ArrayList<>(points_to_test);

        for(Point point_to_test : points_to_test) {

            if(point_to_test == segment_first_point || point_to_test == segment_last_point) {
                continue;
            }

            test_x = point_to_test.getNumber(0);
            test_y = point_to_test.getNumber(1);

            // k = ((x - a).(b - a))/((b - a).(b - a))
            k_numerator = (test_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)
                    + (test_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y);

            k_denominator = (segment_last_point_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)
                    + (segment_last_point_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y);

            // p = ((x - a).(b - a))/((b - a).(b - a)) (b - a) + a
            coords_p.add(
                    ""
                            + (

                            ((test_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)) // "((x - a).(b - a))"
                                    /
                                    (// "((b - a).(b - a))"
                                            (segment_last_point_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)

                                    )

                                    *
                                    (segment_last_point_x - segment_first_point_x) // "* (b - a)"

                            +

                            segment_first_point_x) // " + a"
            );
            coords_p.add(
                    ""
                            + (

                            ((test_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y)) // "((x - a).(b - a))"
                                    /
                                    (// "((b - a).(b - a))"
                                            (segment_last_point_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y)

                                    )

                                    *

                                    (segment_last_point_y - segment_first_point_y) // "* (b - a)"

                            +

                            segment_first_point_y) // " + a"

            );
            p = new Point(coords_p);

            if(k_numerator/k_denominator < 0 && EuclidianFilters.distanceBetweenTwoPoints(point_to_test, segment_first_point) > maximal_allowed_distance) {
                returned.remove(point_to_test);
                System.out.println("------> Point removed : " + point_to_test);

            } else if(k_numerator/k_denominator >= 0 && k_numerator/k_denominator <= 1 && EuclidianFilters.distanceBetweenTwoPoints(point_to_test, p) > maximal_allowed_distance) {
                returned.remove(point_to_test);
                System.out.println("------> Point removed : " + point_to_test);

            } else if(k_numerator/k_denominator > 1 &&  EuclidianFilters.distanceBetweenTwoPoints(point_to_test, segment_last_point) > maximal_allowed_distance) {
                returned.remove(point_to_test);
                System.out.println("------> Point removed : " + point_to_test);
            }

        }

        return returned;
    }

Question

Je ne comprends pas ce qui ne va pas dans mon code, la logique semble pourtant assez correcte… Si vous pouviez m’aider un peu ce serait sympa du coup !

Solution (code qui compile et fait bien ce qu’on lui demande de faire)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

    public static List<Point> getOnlyOnSegmentPoints(Point segment_first_extremity, Point segment_last_extremity, List<Point> points_to_test, double maximal_allowed_distance) {
        double segment_first_point_x = segment_first_extremity.getNumber(0);
        double segment_first_point_y = segment_first_extremity.getNumber(1);
        double segment_first_point_z = segment_first_extremity.getNumber(2);

        double segment_last_point_x = segment_last_extremity.getNumber(0);
        double segment_last_point_y = segment_last_extremity.getNumber(1);
        double segment_last_point_z = segment_last_extremity.getNumber(2);

        double test_x, test_y, test_z;
        double k_numerator, k_denominator, k;

        Point p;
        List<String> coords_p = new ArrayList<>();

        List<Point> returned = new ArrayList<>(points_to_test);

        for(Point point_to_test : points_to_test) {

            coords_p.clear();

            test_x = point_to_test.getNumber(0);
            test_y = point_to_test.getNumber(1);
            test_z = point_to_test.getNumber(2);

            // k = ((x - a).(b - a))/((b - a).(b - a))
            k_numerator = (test_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)
                    + (test_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y)
                    + (test_z - segment_first_point_z) * (segment_last_point_z - segment_first_point_z);

            k_denominator = (segment_last_point_x - segment_first_point_x) * (segment_last_point_x - segment_first_point_x)
                    + (segment_last_point_y - segment_first_point_y) * (segment_last_point_y - segment_first_point_y)
                    + (segment_last_point_z - segment_first_point_z) * (segment_last_point_z - segment_first_point_z);
            k = k_numerator/k_denominator;

            // p = ((x - a).(b - a))/((b - a).(b - a)) (b - a) + a
            coords_p.add("" + (k * (segment_last_point_x - segment_first_point_x) + (segment_first_point_x)));
            coords_p.add("" + (k * (segment_last_point_y - segment_first_point_y) + (segment_first_point_y)));
            coords_p.add("" + (k * (segment_last_point_z - segment_first_point_z) + (segment_first_point_z)));
            p = new Point(coords_p);

            if(k < 0.0 && EuclidianFilters.distance3DBetweenTwoPoints(point_to_test, segment_first_extremity) > maximal_allowed_distance) {
                returned.remove(point_to_test);
            }

            if(k >= 0.0 && k <= 1.0 && EuclidianFilters.distance3DBetweenTwoPoints(point_to_test, p) > maximal_allowed_distance) {
                returned.remove(point_to_test);
            }

            if(k > 1.0 && EuclidianFilters.distance3DBetweenTwoPoints(point_to_test, segment_last_extremity) > maximal_allowed_distance) {
                returned.remove(point_to_test);
            }

        }

        return returned;
    }

Je te laisse jeter un coup d’oeil à ceci.

Comme tu peux le voir, je suis l’auteur du topic, mais j’ai abandonné le projet sans jamais vraiment avoir trouvé de solution. Mais de mémoire j’avais créer un rectangle autour de la ligne et je vérifiais si j’étais dans le carré. Je vais voir si je retrouve des sources.

Salut,

Après un peu de réflexion, je me dis que le plus simple est de changer de repère pour se placer dans un repère où $A$ et $B$ sont sur l’axe des $x$, avec $A=(0,0)$ et $B=(x_B, 0)$. De cette façon, pour savoir si le point $M=(x,y)$ appartient à $[AB]$ en se donnant une marge $\delta$, il suffit de regarder si $0\leqslant x\leqslant x_B$ et $|y|\leqslant\delta$ ou $x<0$ et $x^2+y^2\leqslant\delta^2$ ou enfin $x>x_B$ et $(x-x_B)^2+y^2\leqslant\delta^2$.

Pour passer du repère initial (pour lequel je marque les coordonnées avec un exposant $i$) au nouveau repère, il suffit de mettre $A$ à l’origine et tourner de l’angle $-\left(Ox^i, \vec{AB}\right)$ :

Avec $AB=x_B=\sqrt{(x^i_A-x^i_B)^2+(y^i_A-y^i_B)^2}$.

On peut noter que la méthode de la détermination de $k$ est strictement équivalente à un changement de repère en ajoutant une normalisation par $AB$ (donc en divisant par $\dfrac1{AB^2}$ au lieu de $\dfrac1{AB}$ dans le calcul de $(x,y)$), ce qui donne $x_B=1$ et les comparaisons doivent être faites par rapport à $\dfrac{\delta}{AB}$ au lieu de $\delta$. Le voir comme ça permet de le retrouver facilement sans passer par la minimisation du polynôme en $k$. Après changement de repère, on a $x=k$, et $y=M\Delta$.

Je me demande si ça serait pas plus élégant de prendre un modèle elliptique. Ça change un peu la qualité de la détection (mais qui est peut-être plus naturelle?). En tout cas c’est plus simple à vérifier puisqu’il s’agit de tester simplement :

La quantité à droite est constante. Celle à gauche est pas bien compliquée à évaluer

Quasiment idem Holosmos, mais plutôt : ( D(M,A) + D(M,B) ) / D(A,B) < k

Ainsi, on préserve les formes : Si telle position est acceptée, alors la position similaire, obtenue en multipliant toutes les valeurs par 10 sera aussi acceptée. Mais ce n’est peut-être pas le comportement voulu !

On peut aussi utiliser le formalisme des nombres complexes si c’est facile en Java. Le changement de repère s’écrit $z \mapsto (z - z_A)(\overline{z_B - z_A})$, puis on regarde si la distance est inférieure à $\delta \times AB$. Enfin, je voulais juste dire que c’était peut-être bien de rester uniquement avec des calculs sur des entires en manipulant les distances au carré au lieu des distances et en effectuant juste des multiplications, non ? Et puis il faudrait refactoriser le code. C’est pour quoi que tu veux filtrer des points suivant leur distance à un segment ?

Sinon j’ai appris l’existence d’algorithmes pour calculer une somme pythagoricienne évitant les dépassements de capacité présents lors du calcul direct avec les carrés.

Dans le cas présent je pense pas que ce soit le comportement voulu.

Si on a un intervalle immense, on a pas envie qu’il soit épais comme une comète. On cherche plutôt à laisser une petite marge d’erreur (constante).

Bonjour à tous,

Merci d’avoir répondu, je vois que vous êtes tous très forts en maths ! Au final je suis resté avec ma solution, et le problème que je rencontrais ne venait pas de l’algorithme en lui-même : il était en effet dû à un effet de bord de mon programme… (oubli d’un clear car je stocke les coordonnées de p dans une ArrayList => ses coordonnées n’étaient pas mises à jour… !).

J’ai édité l’OP avec le code final, qui compile et fait bien ce qu’on lui demande de faire.