Jak mogę obliczyć prostoliniowość narysowanej linii?


37

Pracuję nad grą, która wymaga od graczy narysowania linii od punktu A (x1, y1) do drugiego punktu B (x2, y2) na ekranie urządzenia z Androidem.

Chcę dowiedzieć się, jak dobrze ten rysunek pasuje do linii prostej. Na przykład wynik 90% oznaczałby, że rysunek prawie idealnie pasuje do linii. Jeśli gracze narysują zakrzywioną linię od A do B, powinna uzyskać niski wynik.

Punkty końcowe nie są znane z góry. W jaki sposób mogę to zrobić?


1
Czy wiesz z góry, jakie są twoje dwa punkty końcowe? Czy jest ustalany w momencie, gdy użytkownik przestaje dotykać ekranu?
Vaillancourt

Przepraszam, jeśli mój opis nie jest dla ciebie jasny. Cóż, punkt początkowy A (x, y) to pierwszy dotyk, a punkt końcowy B (x, y) to moment, kiedy uwolniliśmy się z ekranu dotykowego, jak powiedziałeś.
user3637362

Mamy powiązane pytanie dotyczące dopasowywania liter narysowanych przez gracza .
Anko

3
Proszę nie publikować zdjęć dla kodu źródłowego w przyszłości.
Josh

1
@ user3637362 Rozumiem, że zaczynasz j=1, dzięki czemu można porównać touchList[j]z touchList[j-1], ale kiedy touch.phase == TouchPhase.Beganlub touch.phase == TouchPhase.Endedpozycje nie są dodawane do touchList, a następnie nieuwzględnione w sumLength. Ten błąd byłby obecny we wszystkich przypadkach, ale byłby bardziej widoczny, gdy linia ma kilka segmentów.
Kelly Thomas,

Odpowiedzi:


52

Idealnie prosta linia byłaby również najkrótszą możliwą linią o całkowitej długości sqrt((x1-x2)² + (y1-y2)²). Bardziej bazująca na linii linia będzie mniej idealnym połączeniem, a zatem będzie nieuchronnie dłuższa.

Kiedy weźmiesz wszystkie poszczególne punkty ścieżki, którą narysował użytkownik i zsumujesz odległości między nimi, możesz porównać całkowitą długość z idealną długością. Im mniejsza całkowita długość podzielona przez idealną długość, tym lepsza linia.

Oto wizualizacja. Gdy czarne kropki są punktami końcowymi gestu, a niebieskie punkty są punktami mierzonymi podczas gestu, obliczymy i zsumujemy długości zielonych linii i podzielimy je przez długość czerwonej linii:

wprowadź opis zdjęcia tutaj

Wynik lub wskaźnik kręgu 1 byłby idealny, wszystko wyższe byłoby mniej idealne, wszystko poniżej 1 byłoby błędem. Jeśli wolisz mieć wynik procentowy, podziel 100% przez tę liczbę.


34
Z tym podejściem wiąże się niewielki problem polegający na tym, że polilinie o równej długości nie są równie „proste”. Linia, która kołysze się z małym odchyleniem (ale wiele razy) wokół linii prostej, jest „prostsza” niż linia o równej długości, która odchyla się do jednego punktu, a następnie z powrotem.
Dancrumb,

Nie mogę dać +1 komentarzowi @Dancrumbs - jest to dość kluczowe ograniczenie w przypadku tej metody, ponieważ jeśli użytkownik rysuje linię prostą, trzęsie się nieco, więc wydaje się, że jest to częsty przypadek użycia.
T. Kiley,

@Dancrumb wystarczy wziąć pod uwagę średnią odległość od linii lub uwzględnić „maksymalną odległość” dowolnego punktu od linii. Następnie możesz wyważyć algorytm w kierunku bardziej chwiejnych linii o mniejszych amplitudach odchylenia i z dala od linii, które zbaczają daleko od oczekiwanej ścieżki.
Superdoggy

2
@Dancrumb, wydaje mi się, że może to być korzystne dla przypadku użycia OP. Ręcznie rysowane linie będą oczywiście miały niewielkie odchylenia. Takie podejście może faktycznie zadziałać w celu osłabienia efektu tych oczekiwanych różnic.

2
@ user3637362 masz błąd w kodzie. Możliwym wyjaśnieniem jest to, że zapomniałeś uwzględnić odległość między punktem początkowym a pierwszym punktem lub punktem końcowym a ostatnim punktem, ale bez spojrzenia na kod nie można powiedzieć, jaki mógł być Twój błąd.
Philipp

31

To może nie być najlepszy sposób na wdrożenie tego, ale sugeruję, że RMSD (odchylenie średniego kwadratu pierwiastkowego) mogłoby być lepsze niż tylko metoda odległości, w przypadkach wspomnianych przez Dancrumb (patrz pierwsze dwie linie poniżej).

RMSD = sqrt(mean(deviation^2))

Uwaga:

  • Suma odchyleń bezwzględnych (całkowych) może być lepsza, ponieważ nie uśrednia błędów dodatnich za pomocą błędów ujemnych. ( =sum(abs(deviation)))
  • Prawdopodobnie musiałbyś szukać najkrótszej odległości do linii liniowej, jeśli istnieje sposób, który tworzy krótsze odległości niż upuszczenie prostopadłej.

rysunek

(Proszę wybaczyć niską jakość mojego rysunku)

Jak widzisz, musisz

  1. znajdź wektor ortogonalny do swojej linii ( iloczyn iloczynu wynosi 0 ).
    Jeśli twoja linia wskazuje w stronę (1, 3) , którą chcesz (3, -1)(przez początek każdego)
  2. Zmierz odległości h od linii idealnej do linii użytkownika, równolegle do tego wektora.
  3. Oblicz RMSD lub sumę różnic bezwzględnych.

Odpowiedź Joela Bosvelda wskazuje na interesujący przypadek: prawie idealnie prostą linię z narożnikami na początku i na końcu. Jeśli użytkownik powinien swobodnie rysować linię, jest to rzeczywiście problem. Niemniej jednak uważam, że ta metoda mogłaby obejmować ten scenariusz. Można faktycznie wykonać dopasowanie z RMSD lub absolutną całką jako najwyższą możliwą do zminimalizowania wartość. Wartości początkowe mogą być punktami początkowymi i końcowymi. Ponieważ długość nie ma znaczenia, nie ma również znaczenia, czy optymalizacja przesuwa punkty, aby idealna linia sięgała dalej lub była krótsza (wysokość musi być obliczona do tego niveau).
gr4nt3d

1
Kolejny przypadek, który nie wydaje się obejmować: Powiedz, że każdy zmierzony punkt znajduje się na osi x, ale linia kilkakrotnie zmienia kierunek. Zwróci błąd 0
dave mankoff

23

Istniejące odpowiedzi nie biorą pod uwagę, że punkty końcowe są arbitralne (a nie podane). Dlatego podczas pomiaru prostoliniowości krzywej nie ma sensu używać punktów końcowych (na przykład do obliczenia oczekiwanej długości, kąta, położenia). Prostym przykładem może być linia prosta z dwoma końcami kinck. Jeśli mierzymy za pomocą odległości od krzywej i linii prostej między punktami końcowymi, będzie to dość duża, ponieważ narysowana linia prosta jest odsunięta od linii prostej między punktami końcowymi.

Jak powiedzieć, jak prosta jest krzywa? Zakładając, że krzywa jest wystarczająco gładka, chcemy wiedzieć, o ile średnio zmienia się styczna do krzywej. Dla linii byłoby to zero (ponieważ styczna jest stała).

Jeśli pozwolimy pozycji w czasie t być (x (t), y (t)), to styczną jest (Dx (t), Dy (t)), gdzie Dx (t) jest pochodną x w chwili t (wydaje się, że w tej witrynie brakuje obsługi TeXa). Jeśli krzywa nie jest sparametryzowana przez długość łuku, normalizujemy dzieląc przez || (Dx (t), Dy (t)) ||. Mamy więc wektor jednostkowy (lub kąt) stycznej do krzywej w czasie t. Tak więc kąt to a (t) = (Dx (t), Dy (t)) / || (Dx (t), Dy (t)) ||

Jesteśmy następnie zainteresowani zintegrowaniem krzywej || Da (t) || ^ 2.

Biorąc pod uwagę, że najprawdopodobniej mamy dyskretne punkty danych, a nie krzywą, musimy użyć różnic skończonych do przybliżenia pochodnych. Tak więc Da (t) staje się (a(t+h)-a(t))/h. I staje się (t) ((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)/||((x(t+h)-x(t))/h,(y(t+h)-y(t))/h)||. Następnie otrzymujemy S, sumując h||Da(t)||^2dla wszystkich punktów danych i ewentualnie normalizując przez długość krzywej. Najprawdopodobniej używamy h=1, ale tak naprawdę jest to tylko arbitralny czynnik skali.

Aby powtórzyć, S będzie wynosić zero dla linii i tym większe, im bardziej odbiega od linii. Aby przekonwertować na wymagany format, użyj 1/(1+S). Biorąc pod uwagę, że skala jest nieco dowolna, możliwe jest pomnożenie S przez pewną liczbę dodatnią (lub przekształcenie jej w inny sposób, np. Użyj bS ^ c zamiast S), aby wyregulować, jak proste są niektóre krzywe.


2
To najbardziej sensowna definicja prostoty.
Marcks Thomas,

1
To zdecydowanie najbardziej sensowna odpowiedź i jestem pewien, że inni mogliby stać się bardzo frustrujący. Niestety, forma prezentacji rozwiązania jest nieco bardziej niejasna niż inne, ale polecam, że OP nadal występuje.
Dan Sheppard

Ogólnie uważam również, że ta odpowiedź jest rzeczywiście najlepsza. Chociaż przeszkadza mi problem: co się stanie, jeśli linia nie będzie „wystarczająco gładka”? Np. Jeśli masz dwa idealnie proste segmenty linii o kącie, powiedzmy 90 °. Czy się mylę, czy może to dać całkiem niski wynik w porównaniu z naprawdę gładką linią? (Myślę, że przypadek użytkownika Dancrumb z chwiejną linią był podobny problem) ... Lokalnie jest to z pewnością najlepszy sposób.
gr4nt3d

3

To jest system oparty na siatce, prawda? Znajdź własne punkty dla linii i oblicz nachylenie linii. Teraz, korzystając z tego obliczenia, określ poprawne punkty, przez które przechodzi linia, biorąc pod uwagę pewien margines błędu w stosunku do dokładnej wartości.

Za pomocą krótkiej liczby prób i błędów określ, jaka byłaby dobra i zła ilość pasujących punktów, i skonfiguruj grę, używając skali dla tych samych wyników z testów.

tzn. krótka linia o prawie poziomym nachyleniu może mieć 7 punktów, przez które można by narysować. Jeśli możesz konsekwentnie dopasować 6 lub więcej z 7, które zostały określone jako część linii prostej, byłby to najwyższy wynik. Klasyfikacja pod względem długości i dokładności powinna być częścią oceny.


3

Bardzo łatwą i intuicyjną miarą jest obszar między najlepiej dopasowaną linią prostą a rzeczywistą krzywą. Ustalenie tego jest dość proste:

  1. Użyj dopasowania najmniejszych kwadratów we wszystkich punktach (zapobiega to problemowi zagięcia końca wspomnianego przez Joela Bosvelda).
  2. Dla wszystkich punktów na krzywej określ odległość do linii. Jest to również standardowy problem. (algebra liniowa, transformata podstawowa).
  3. Zsumuj wszystkie odległości.

Czy miałbyś coś przeciwko, jeśli poproszę Cię o kodowanie tekstu (JS, C #) lub pseudo-kod, ponieważ większość odpowiedzi powyżej jest opisanych w teorii, nie wiem jak zacząć?
user3637362

1
@ user3637362: StackOverflow ma praktyczne odpowiedzi: stackoverflow.com/questions/6195335/… stackoverflow.com/questions/849211/...
MSalters

2

Chodzi o to, aby zachować wszystkie punkty, których dotknął użytkownik, a następnie ocenić i zsumować odległość między każdym z tych punktów do linii utworzonej, gdy użytkownik zwolni ekran.

Oto coś na początek w pseudokodzie:

bool mIsRecording = false;
point[] mTouchedPoints = new point[];

function onTouch
  mIsRecording = true

functon update
  if mIsRecording
    mTouchedPoints.append(currentlyTouchedLocation)

function onRelease
  mIsRecording = false

  cumulativeDistance = 0

  line = makeLine( mTouchedPoints.first, mTouchedPoints.last )

  for each point in mTouchedPoints:
    cumulativeDistance = distanceOfPointToLine(point, line)

  mTouchedPoints = new point[]

Co cumulativeDistancemoże dać ci pomysł na dopasowanie. Odległość 0 oznaczałaby, że użytkownik był cały czas na linii prostej. Teraz musisz wykonać kilka testów, aby zobaczyć, jak zachowuje się w twoim kontekście. I możesz chcieć zwiększyć wartość zwracaną przez distanceOfPointToLinepodniesienie jej do kwadratu, aby ukarać bardziej duże odległości od linii.

Nie jestem zaznajomiony z jednością, ale kod updatetutaj może przejść w onDragfunkcji.

I możesz chcieć dodać gdzieś tam jakiś kod, aby zapobiec rejestracji punktu, jeśli jest taki sam jak ostatni zarejestrowany. Nie chcesz rejestrować rzeczy, gdy użytkownik się nie rusza.


5
Po dodaniu odległości między linią idealną a punktem dla każdego zmierzonego punktu należy uwzględnić liczbę podjętych działań, w przeciwnym razie, gdy użytkownik będzie rysował wolniej lub użyje urządzenia o większej szybkości skanowania, zarejestruje więcej punkty, co oznacza, że ​​uzyskają gorszy wynik.
Philipp

@Philipp Tak, robisz! Muszę przyznać, że twój sposób na zrobienie tego wydaje się lepszy niż mój: P
Vaillancourt

Myślę, że to podejście zostało ulepszone poprzez przyjęcie średniego dystansu zamiast skumulowanego dystansu.
Dancrumb,

@Dancrumb Naprawdę, to zależy od potrzeb, ale tak, to byłby sposób, aby to zrobić.
Vaillancourt

2

Jedną z metod, której można użyć, jest podzielenie linii na segmenty i wykonanie iloczynu wektorowego między każdym wektorem reprezentującym segment, a wektorem reprezentującym linię prostą między pierwszym i ostatnim punktem. Ma to tę zaletę, że pozwala łatwo znaleźć wyjątkowo „kolczaste” segmenty.

Edytować:

Rozważałbym również użycie długości segmentu oprócz iloczynu kropkowego. Bardzo krótki, ale ortogonalny wektor powinien liczyć się mniej niż długi, który ma mniejsze odchylenie.


1

Najłatwiejszym i najszybszym może być po prostu ustalenie, jak gruba musiałaby być linia, aby pokryć wszystkie punkty narysowanej przez użytkownika linii.

Im grubsza musi być linia, tym gorzej użytkownik rysował swoją linię.


0

W jakiś sposób odnosząc się do MSalters Answer, oto kilka bardziej szczegółowych informacji.

Użyj metody najmniejszych kwadratów, aby dopasować linię do swoich punktów. Zasadniczo szukasz funkcji y = f (x), która najlepiej pasuje. Gdy już go masz, możesz użyć rzeczywistych wartości y do zsumowania kwadratu różnic:

s = suma ponad ((yf (x)) ^ 2)

Im mniejsza suma, tym linia jest prostsza.

Jak uzyskać najlepsze przybliżenie, wyjaśniono tutaj: http://math.mit.edu/~gs/linearalgebra/ila0403.pdf

Wystarczy przeczytać z „Dopasowywanie linii prostej”. Zauważ, że zamiast xib stosuje się t zamiast y. C i D należy określić jako przybliżenie, wtedy masz f (x) = C + Dx

Uwaga dodatkowa: Oczywiście należy również wziąć pod uwagę długość linii. Każda linia składająca się z 2 punktów będzie idealna. Nie znam dokładnego kontekstu, ale sądzę, że jako ocenę użyłbym sumy kwadratów podzielonej przez liczbę punktów. Dodałbym również wymóg minimalnej długości, minimalnej liczby punktów. (Może około 75% maksymalnej długości)

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.