Odległość punktu od odcinka

Podstawowy problem grafiki komputerowej

Część aplikacji wymaga rozpoznawania obiektów graficznych i trudno z tym polemizować. Wyobraźmy sobie prosty program do definiowania kształtów foremek - być może chcielibyśmy definiować krawędzie i dać możliwość wskazania ich myszką. Jak rozpoznać, że kliknięcie w punkcie (X,Y) jest kliknięciem w odcinek? Inny przykład - graf. Grafy mogą reprezentować połączenia pomiędzy miastami, pomiędzy komputerami, przepływy informacji. Tutaj też chcielibyśmy mieć możliwość zaznaczenia takiej krawędzi i wyświetlenia atrybutów danego połączenia. Powszechności odcinków w schematach technicznych też chyba nie trzeba udowadniać. Prosta kreska jest bardziej czytelna dla technika niż nawet najbardziej wykwintne malowidło znanego impresjonisty czy kapisty. Przykłady można mnożyć, ale nie o to chodzi. Faktem jest, że wielokąty (ze szczególnym uwzględnieniem trójkątów) również zbudowane są z odcinków. Trzeba poznać fundamenty, potem można mierzyć dalej.

Przykład wykrywania odcinków na płótnie JavaScript

Zanim przejdę do szczegółowych wyjaśnień, matematycznych i programistycznych, pozwolę sobie pokazać małą aplikację demonstracyjną:

Rysunek można nazwać interaktywnym. Po pierwsze, gdy użytkownik najedzie kursorem myszy nad obrazek, wskaźnik zmieni swój kształt. Gdy użytkownik kliknie w pobliżu linii (w zasadzie to należałoby powiedzieć odcinka), segment zostanie podświetlony na czerwono. Gdy użytkownik kliknie w pobliżu punktu łączącego dwa segmenty, oba z nich zostaną oznaczone. Gdy użytkownik kliknie poza linie, zaznaczenie zostanie anulowane. Tyle zabawy, czas na teorię.

Skąd się bierze wzór na odległość punktu od odcinka?

Załóżmy, że dane są dwa punkty wyznaczające odcinek, P1 oraz P2. Załóżmy też, że punkty umieszczone są w przestrzeni dwuwymiarowej (będą posiadały współrzędne x i y). Gdzieś na tej płaszczyźnie znajduje się trzeci punkt, nazwijmy go sobie P. Gdyby odcinek [P1,P2] był nieskończenie długi, linia wyznaczająca najkrótszą odległość byłaby prostopadła do takiego odcinka. Załóżmy na początek, że tak jest i popatrzmy na rysunek, który obrazuje wspomniany przypadek:

Na rysunku oznaczyłem dodatkowo punkt P3, w którym prosta wyznaczająca najkrótszą odległość przecina odcinek. Jak matematycznie zapisać ten warunek? Otóż będzie to wektor, równoległy do wektora [P1,P2], ale nieco krótszy. Możemy to zapisać w następujący sposób:

P3 = P1+u(P2-P1)

Skorzystamy przy okazji z innej zależności. Wiemy, że proste wyznaczone przez punkty [P1,P2] oraz [P3,P] są prostopadłe. Oznacza to, że iloczyn skalarny tych wektorów będzie równy 0. Możemy to zapisać następująco:

[P2-P1]·[P-P3] = 0

Jeżeli teraz wykonamy podstawienie i zamienimy P3 otrzymamy:

[P2-P1]·[P-P1-u(P2-P1)] = 0

Wszystkie wartości oprócz u są znane. Wystarczy wobec tego przekształcić wzór. Pamiętajmy, że mamy do czynienia z dwuwymiarowym układem współrzędnychPokazane wyliczenia można z łatwością przenieść w trójwymiarowy układ. Sposób postępowania będzie podobny.:

([x2,y2]-[x1,y1])·([x,y]-[x1,y1]-u([x2,y2]-[x1,y1]) = 0

([x2 - x1,y2 - y1])·([x-x1-u(x2-x1),y-y1-u(y2-y1]) = 0

(x2 - x1)(x - x1 - u(x2 - x1)) + (y2 - y1)(y - y1 - u(y2 - y1)) = 0

(x2 - x1)(x - x1) - u(x2 - x1)2 + (y2 - y1)(y - y1) - u(y2 - y1)2 = 0

(x2 - x1)(x - x1) + (y2 - y1)(y - y1) = u(x2 - x1)2 + u(y2 - y1)2

(x2 - x1)(x - x1) + (y2 - y1)(y - y1) = u((x2 - x1)2 + (y2 - y1)2)


    (x2 - x1)(x - x1) + (y2 - y1)(y - y1)
u = ————————————————————————————————————
          (x2 - x1)2 + (y2 - y1)2

Warto zwrócić uwagę na mianownik. Jest to po pierwsze kwadrat odległości pomiędzy punktami P1 i P2, a po drugie - jedyne miejsce, w którym nasze rozważania nie mają sensu. Nie będziemy przecież dzielić przez 0. Przypomnijmy sobie wcześniej zapisaną zależność:

P3 = P1+u(P2-P1)

Wyliczyliśmy u, więc możemy teraz z łatwością wyliczyć współrzędne punktu przecięcia, P3:

x3 = x1 + u(x2 - x1)
y3 = y1 + u(y2 - y1)

Założyliśmy na początku, że odcinek [P1,P2] jest nieskończenie długi. W takim przypadku prosta prostopadła do odcinka [P1,P2] i przechodząca przez punkt P przecina badany odcinek pomiędzy punktami końcowymi. Nie zawsze tak jest.

Prosta wyznaczająca odległość nie przecina odcinka

W niektórych przypadkach punkt przecięcia P3 leży poza odcinkiem i trzeba sobie jakoś z tym poradzić. Popatrzmy na ilustrację pokazującą problem:

Wiadomo, że w takim przypadku nie należy liczyć odległości punktu do prostej. Poprawnie mierzona odległość to zwykła odległość pomiędzy punktami, liczona z twierdzenia Pitagorasa. Z kronikarskiego obowiązku oznaczyłem tę odległość na rysunku. Pozostaje tylko pytanie: jak stwierdzić, czy punkt przecięcia wypada poza odcinkiem? Bardzo łatwo - przy pomocy współczynnika u. Przecięcie wypada przed punktem P1 jeżeli zmienimy zwrot wektora, czyli pomnożymy go przez wartość ujemną (u < 0). Jeżeli wektor przedłużymy, czyli wymnożymy go przez współczynnik większy niż 1, otrzymamy punkt wykraczający poza P2 (u > 1). Reasumując:

u <= 0 - odległość liczona jest jako odległość pomiędzy punktami P1 i P,
u > 0 i u < 1 - odległość liczona jest od punktu P do punktu przecięcia P3,
u >= 1 - odległość liczona jest jako odległość pomiędzy punktami P2 i P.

W przypadku punktów, dla których przecięcie wypada w P1 i P2 nie ma znaczenia jak postąpimy - odległość |P,P1| dla u = 0 będzie równa odległości |P,P3|. Analogicznie - odległość |P,P2| dla u = 1 będzie również równa odległości |P,P3|.

Implementacja w JavaScript

Wyposażeni w taką wiedzę możemy z łatwością zaimplementować pokazaną na początku prostą aplikację. Popatrzmy na poniższy listing:

<html>
<head>
    <title>Odległość punktu od odcinka</title>
</head>
<body>
<figure>
<canvas id="canvas" width="400", height="320"></canvas>
<figcaption>Płótno z wykrywaniem kliknięć w odcinki.</figcaption>
</figure>
<script>
(function pointToLine() {
    var canvas = document.getElementById("canvas"),
        ctx = canvas.getContext("2d"),
        getMousePos = function(evt, elem) {
            var rect = elem.getBoundingClientRect();
            return {
                X: evt.clientX - rect.left,
                Y: evt.clientY - rect.top
            };
        },
        drawLines = function(p) {
            ctx.beginPath();
            ctx.strokeStyle = "#000";
            ctx.lineWidth=2;
            ctx.moveTo(p[0].X, p[0].Y);
            for (var i=1; i<p.length; i++) {
                ctx.lineTo(p[i].X, p[i].Y);
            }
            ctx.stroke();
        },
        drawLine = function(p1,p2) {
            ctx.beginPath();
            ctx.strokeStyle = "#F00";
            ctx.lineWidth=2;
            ctx.moveTo(p1.X, p1.Y);
            ctx.lineTo(p2.X, p2.Y);
            ctx.stroke();
        },
        distanceToLine = function(p1, p2, p) {
            var A = p2.X-p1.X,
                B = p2.Y-p1.Y,
                p3;
            var u = (A*(p.X-p1.X)+B*(p.Y-p1.Y))/(Math.pow(A,2)+Math.pow(B,2));
            if (u<=0) {
                p3 = p1;
            }
            else if (u>=1) {
                p3 = p2;
            }
            else {
                p3 = {
                    X: p1.X + u * A,
                    Y: p1.Y + u * B
                };
            }
            return Math.sqrt(Math.pow(p.X-p3.X,2)+Math.pow(p.Y-p3.Y,2));
        },
        points = [{X: 100, Y: 10},
                  {X: 10, Y: 60},
                  {X: 100, Y: 300},
                  {X: 150, Y: 70},
                  {X: 250, Y: 280},
                  {X: 350, Y: 250}];
    
    canvas.addEventListener("mousemove", function(e){
        var found = false;
        var position = getMousePos(e, canvas);
        for (var i=0; i<points.length-1; i++) {
            if (distanceToLine(points[i], points[i+1], position)<2)
                found = true;
        }
        
        canvas.style.cursor = found?"pointer":"default";    
    });
    
    canvas.addEventListener("click", function(e){
        drawLines(points);
        var position = getMousePos(e, canvas);    
        for (var i=0; i<points.length-1; i++) {
            if (distanceToLine(points[i], points[i+1], position)<2)
                drawLine(points[i], points[i+1]);
        }
    });
    drawLines(points);
})();
</script>
</body>
</html>

W przypadku kodu o rozsądnej długości staram się go umieszczać w całości. Kod można śmiało skopiować na lokalny pulpit i poeksperymentować z różnymi ustawieniami. Ja uznałem, że kliknięcia w linię będą akceptowane wtedy, gdy odległość nie będzie przekraczała dwóch pikseli. W wielu zastosowaniach jest to ograniczenie zbyt restrykcyjne. W wielu przypadkach nie jest pożądane zaznaczanie dwóch sąsiednich krawędzi jednocześnie. Można wtedy zaznaczać tylko tę, która jest bliżej lub... pierwszą lepszą.

Kategoria:HTMLJavaScriptCanvas