Potrzebuję podstawowej funkcji, aby znaleźć najkrótszą odległość między punktem a segmentem linii. Napisz rozwiązanie w dowolnym języku; Potrafię przetłumaczyć to na to, czego używam (JavaScript).
EDYCJA: Mój segment linii jest zdefiniowany przez dwa punkty końcowe. Więc mój segment linii AB
jest zdefiniowany przez dwa punkty A (x1,y1)
i B (x2,y2)
. Próbuję znaleźć odległość między tym odcinkiem linii a punktem C (x3,y3)
. Moje umiejętności geometrii są zardzewiałe, więc przykłady, które widziałem, są mylące, przykro mi to przyznać.
language-agnostic
geometry
distance
line-segment
Eli Courtwright
źródło
źródło
Odpowiedzi:
Eli, ustalony kod jest niepoprawny. Punkt w pobliżu linii, na której leży segment, ale daleko od jednego końca segmentu, zostałby nieprawidłowo oceniony w pobliżu segmentu.Aktualizacja: Wspomniana nieprawidłowa odpowiedź nie jest już zaakceptowana.Oto poprawny kod w C ++. Zakłada klasę wektora 2D
class vec2 {float x,y;}
, w zasadzie, z operatorami do dodawania, odejmowania, skalowania itp. Oraz funkcją iloczynu odległości i kropki (tjx1 x2 + y1 y2
.).EDYCJA: Potrzebowałem implementacji Javascript, więc tutaj jest bez zależności (ani komentarzy, ale jest to bezpośredni port powyższego). Punkty są reprezentowane jako obiekty
x
iy
atrybuty.EDYCJA 2: Potrzebowałem wersji Java, ale co ważniejsze, potrzebowałem jej w 3d zamiast 2d.
źródło
p
na linię to punkt na linii najbliższejp
. (I prostopadłe do linii na występ przechodzi przezp
). Liczbat
, jak daleko wzdłuż odcinka linii od punktuv
naw
tym, że występ spada. Więc jeślit
wynosi 0, rzutowanie zaczyna się od razuv
; jeśli to 1, to jest włączonew
; jeśli wynosi na przykład 0,5, to jest w połowie drogi między. Jeślit
jest mniejsze niż 0 lub większe niż 1, spada na linię za jednym końcem lub drugim segmentem. W takim przypadku odległość do segmentu będzie odległością do bliższego końca.Oto najprostszy kompletny kod w JavaScript.
x, y to punkt docelowy, a x1, y1 do x2, y2 to segment linii.
ZAKTUALIZOWANO: naprawiono problem z linią długości 0 z komentarzy.
źródło
Jest to implementacja stworzona dla SEGMENTÓW LINII SZYBKICH, a nie nieskończonych linii, jak się wydaje w większości innych funkcji (dlatego to zrobiłem).
Implementacja teorii przez Paula Bourke .
Pyton:
AS3:
Jawa
źródło
distAnother(0, 0, 4, 0, 2, 2)
daje 2.8284271247461903 (niepoprawnie).distAnother(0., 0., 4., 0., 2., 2.)
daje 2.0 (poprawnie). Pamiętaj o tym. Myślę, że kod można ulepszyć, aby mieć gdzieś konwersję float.W moim wątku pytania, jak obliczyć najkrótszą odległość 2D między punktem a segmentem linii we wszystkich przypadkach w C, C # / .NET 2.0 lub Java? Poproszono mnie o umieszczenie tutaj odpowiedzi w języku C #, więc tutaj jest zmodyfikowana z http://www.topcoder.com/tc?d1=tutorials&d2=geometry1&module=Static :
Nie jestem w stanie odpowiedzieć, ale zadawać pytania, więc mam nadzieję, że z pewnych powodów nie otrzymam miliona głosów, ale skonstruuję krytykę. Chciałem tylko (i zachęciłem) do dzielenia się czyimiś pomysłami, ponieważ rozwiązania w tym wątku są albo z jakimś egzotycznym językiem (Fortran, Mathematica) lub oznaczone przez kogoś jako wadliwe. Jedyny użyteczny (dla mnie Grumdrig) jest napisany w C ++ i nikt nie oznaczył go jako wadliwy. Brakuje jednak wywoływanych metod (kropka itp.).
źródło
W F # odległość od punktu
c
do odcinka linii pomiędzya
ib
jest określona przez:Wektor
d
wskazuje oda
dob
wzdłuż odcinka linii. Iloczyn iloczynud/s
zc-a
daje parametr punktu najbliższego zbliżenia między linią nieskończoną a punktemc
. Funkcjemin
imax
służą do zaciskania tego parametru do zakresu,0..s
tak aby punkt znajdował się międzya
ab
. Wreszcie długośća+p-c
to odległość odc
najbliższego punktu na odcinku linii.Przykładowe zastosowanie:
źródło
(a + p - c).Length
lambda
ip
jaklet lambda = (c - a) * d / (s * s)
ilet p = a + (lambda |> max 0.0 |> min 1.0) * d
, odpowiednio. Następnie funkcja zwraca prawidłową odległość, np. Dla przypadkua = (0,1)
, gdyb = (1,0)
ic = (1,1)
.Dla wszystkich zainteresowanych, oto trywialna konwersja kodu JavaScript Joshua do Objective-C:
Potrzebowałem tego rozwiązania do pracy,
MKMapPoint
więc podzielę się nim na wypadek, gdyby ktoś go potrzebował. Tylko niewielka zmiana, która zwróci odległość w metrach:źródło
W Mathematica
Wykorzystuje parametryczny opis segmentu i rzutuje punkt na linię zdefiniowaną przez segment. Ponieważ parametr zmienia się od 0 do 1 w segmencie, jeśli rzut znajduje się poza tymi granicami, obliczamy odległość do odpowiedniego punktu, zamiast linii prostej prostopadłej do segmentu.
Wynik wydruku:
Wykreśl te punkty bliżej niż odległość odcięcia :
Wykres konturowy:
źródło
Hej, właśnie to napisałem wczoraj. Jest w ActionScript 3.0, który jest w zasadzie Javascript, chociaż możesz nie mieć tej samej klasy Point.
Jest też dość kompletna i czytelna dyskusja na temat problemu: notejot.com
źródło
Dla leniwych, oto mój port Objective-C rozwiązania @ Grumdrig powyżej:
źródło
return dist2(p, CGPointMake(v.x + t * (w.x - v.x), v.y + t * (w.y - v.y)))
sqrtf(x) = x*x
.Nie mogłem się oprzeć zakodowaniu go w pythonie :)
Ditto for fortran :)
źródło
Oto pełniejsza pisownia rozwiązania Grumdrig. Ta wersja zwraca również najbliższy punkt.
źródło
Jedno liniowe rozwiązanie wykorzystujące arcus tangens:
Chodzi o to, aby przesunąć A do (0, 0) i obrócić trójkąt zgodnie z ruchem wskazówek zegara, aby C leżał na osi X, kiedy to się stanie, By będzie odległością.
DO#
Jedna linia C # (do konwersji na SQL)
źródło
Zastanów się nad modyfikacją powyższej odpowiedzi Grumdriga. Wiele razy przekonasz się, że niedokładność zmiennoprzecinkowa może powodować problemy. Używam podwójnych w poniższej wersji, ale możesz łatwo zmienić na zmiennoprzecinkowe. Ważną częścią jest to, że używa epsilon do obsługi „wpadki”. Ponadto wiele razy będziesz chciał wiedzieć, GDZIE nastąpiło skrzyżowanie, lub jeśli w ogóle. Jeśli zwrócone t wynosi <0,0 lub> 1,0, nie doszło do kolizji. Jednak nawet jeśli nie doszło do kolizji, wiele razy będziesz chciał wiedzieć, gdzie jest najbliższy punkt w segmencie do P, dlatego używam qx i qy, aby zwrócić tę lokalizację.
źródło
Zakładam, że chcesz znaleźć najkrótszyodległość między punktem a odcinkiem linii; aby to zrobić, musisz znaleźć linię (linię A), która jest prostopadła do segmentu linii (linia B), która przechodzi przez twój punkt, określić przecięcie między tą linią (linia A) a linią, która przechodzi przez twój segment linii (linia B) ; jeśli ten punkt znajduje się między dwoma punktami segmentu linii, to odległość jest odległością między twoim punktem a właśnie znalezionym punktem, który jest przecięciem linii A i linii B; jeśli punkt nie znajduje się między dwoma punktami segmentu linii, musisz uzyskać odległość między swoim punktem a bliższą dwoma końcami segmentu linii; można to łatwo zrobić, biorąc odległość kwadratową (aby uniknąć pierwiastka kwadratowego) między punktem a dwoma punktami segmentu linii; cokolwiek jest bliżej, weź pierwiastek kwadratowy z tego.
źródło
Implementacja C ++ / JavaScript Grumdriga była dla mnie bardzo przydatna, więc podałem bezpośredni port Python, którego używam. Pełny kod jest tutaj .
źródło
Kod Matlab z wbudowanym „autotestem”, jeśli wywołują funkcję bez argumentów:
źródło
A teraz moje rozwiązanie również ...... (JavaScript)
Jest bardzo szybki, ponieważ staram się unikać jakichkolwiek funkcji Math.pow.
Jak widać na końcu funkcji mam odległość linii.
kod pochodzi z lib http://www.draw2d.org/graphiti/jsdoc/#!/example
źródło
zakodowane w t-sql
punkt to (@px, @py), a odcinek linii biegnie od (@ax, @ay) do (@bx, @by)
źródło
Wygląda na to, że prawie wszyscy inni na StackOverflow udzielił odpowiedzi (do tej pory 23 odpowiedzi), więc oto mój wkład w C #. Jest to głównie oparte na odpowiedzi M. Katza, która z kolei oparta jest na odpowiedzi Grumdriga.
A oto mały program testowy.
Jak widać, próbowałem zmierzyć różnicę między użyciem wersji, która omija metodę Sqrt (), a wersją normalną. Moje testy wskazują, że możesz zaoszczędzić około 2,5%, ale nawet nie jestem tego pewien - różnice w różnych przebiegach testowych były tego samego rzędu wielkości. Próbowałem także zmierzyć wersję opublikowaną przez Matti (plus oczywistą optymalizację), i ta wersja wydaje się być o około 4% wolniejsza niż wersja oparta na kodzie Katz / Grumdrig.
Edycja: Nawiasem mówiąc, próbowałem również zmierzyć metodę, która znajduje odległość do nieskończonej linii (nie segmentu linii) przy użyciu iloczynu krzyżowego (i Sqrt ()), i jest o około 32% szybsza.
źródło
Oto wersja C ++ devnullicus przekonwertowana na C #. Do mojej realizacji musiałem znać punkt przecięcia i znaleźć jego rozwiązanie, które działa dobrze.
źródło
Tutaj używa Swift
źródło
DO#
Na podstawie @Grumdrig
źródło
Rozwiązanie 2D i 3D
Rozważ zmianę podstawy, tak aby segment linii stał
(0, 0, 0)-(d, 0, 0)
się punktem(u, v, 0)
. Najkrótsza odległość występuje w tej płaszczyźnie i jest podana przez(odległość do jednego z punktów końcowych lub do linii pomocniczej, w zależności od rzutu na linię. Lokus izo-odległości składa się z dwóch półokręgów i dwóch odcinków linii).
W powyższym wyrażeniu, d jest długością odcinka AB, zaś u, v oznaczają odpowiednio iloczyn skalarny i (moduł) iloczynu AB / d (wektor jednostkowy w kierunku AB) i AC. Stąd wektorowo
źródło
zobacz zestaw narzędzi Matlab GEOMETRY w następującej witrynie: http://people.sc.fsu.edu/~jburkardt/m_src/geometry/geometry.html
ctrl + f i wpisz „segment”, aby znaleźć funkcje związane z segmentem linii. funkcje „segment_point_dist_2d.m” i „segment_point_dist_3d.m” są tym, czego potrzebujesz.
Kody GEOMETRII są dostępne w wersji C i wersji C ++ oraz wersji FORTRAN77 oraz wersji FORTRAN90 i wersji MATLAB.
źródło
Wersja AutoHotkeys oparta na JavaScript Joshua's:
źródło
Nie widziałem tutaj implementacji Java, więc przetłumaczyłem funkcję JavaScript z zaakceptowanej odpowiedzi na kod Java:
źródło
Wersja WPF:
źródło
Oto kod, który skończyłem pisać. Ten kod zakłada, że punkt jest zdefiniowany w postaci
{x:5, y:7}
. Zauważ, że nie jest to absolutnie najbardziej wydajny sposób, ale jest to najprostszy i najłatwiejszy do zrozumienia kod, jaki mogłem wymyślić.źródło
Powyższa funkcja nie działa na liniach pionowych. Oto funkcja, która działa dobrze! Linia z punktami p1, p2. a CheckPoint to p;
źródło
Oto to samo, co odpowiedź C ++, ale została przeniesiona do pascal. Kolejność parametru punktu zmieniła się, aby pasować do mojego kodu, ale jest taka sama.
źródło