Jak mogę obliczyć prostoliniowość narysowanej linii?

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ć?

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:

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ę.

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.

(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.

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.

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.

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.

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.

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.

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ę.

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)