Autor Wątek: Jak sprawdzic czy odcinek przecina okrag  (Przeczytany 5054 razy)

RageX

  • Gość
# Sierpień 14, 2007, 03:29:15
Sprawdzenie czy prosta przecina okrag nie jest trudne - wystarczy policzyc odleglosc srodka okregu od danej prostej i jesli ta odleglosc jest mniejsza od promienia okregu to prosta przeciela okrag.
Ale jak w takim razie sprawdzic czy konkretny odcinek przecial okrag? Nie potrzebuje obliczac punktu tego przececia, starczy ze dowiem sie jak w ogole sprawdzic czy nastapilo przeciecie :)

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline snakeo

  • Użytkownik

# Sierpień 14, 2007, 03:40:13
Jezeli jeden punkt odcinka lezy wewnatrz okregu a drugi na zewnatrz? (tj chodzi mi o wspolrzedne koncow, a to sprowadza sie do 2ch sprawdzen, czy punkt lezy wewnatrz okregu)
Chociaz nie jest to do konca dobre, bo co jezeli odcinek przecial okrag w wiecej niz 1 punkcie?
Jezeli wiec obydwa punkty leza wewnatrz to wtedy odcinek nie przecial, ale jezeli obydwa leza nazewnatrz to wtedy albo przecial albo nie przecial.
Moze by tak poprowadzic prosta przez ten odcinek i pokombinowac z warunkami?
« Ostatnia zmiana: Sierpień 14, 2007, 03:59:53 wysłana przez snakeo »

RageX

  • Gość
# Sierpień 14, 2007, 03:53:45
To za malo. Co jesli poczatek i koniec odcinka sa poza okregiem a sam odcinek przecina okrag?

Offline snakeo

  • Użytkownik

# Sierpień 14, 2007, 04:16:13
Jezeli:
1)wysokosc (od srodka okregu na odcinek AB) trojkata utworzonego z koncow odcinka i srodka okregu jest mniejsza lub rowna promieniowi i
2)oba konce odcinka nie leza wewnatrz okregu
3)oraz odcinek nie jest wspoliniowy ze srodkiem,
To wtedy przecina w 2ch lub 1 punkcie.
4)Jezeli odcinek jest wspoliniowy ze srodkiem (nie wiem czy to dobre okreslenie), to wtedy nalezy sprawdzic wraunek z poprzedniego posta.

Nie wiem czy to zadziala na 100%, nie mam cyrkla zeby potestowac ;/
« Ostatnia zmiana: Sierpień 14, 2007, 04:32:03 wysłana przez snakeo »

RageX

  • Gość
# Sierpień 14, 2007, 04:17:50
Chyba juz wiem.
Najpierw sprawdzic czy oba punkty sa na zewnatrz okregu, potem czy oba wewnatrz, a jesli zaden z tych warunkow nie zostal spelniony to poprowadzic prosta prostopadla do prostej przechodzacej przez odcinek i jesli punkt przeciecia tych dwoch prostych znajduje sie wewnatrz okregu, to odcinek przecial okrag.

Offline snakeo

  • Użytkownik

# Sierpień 14, 2007, 04:20:56
Prosta prostopadla w ktorym punkcie chcesz prowadzic? W punkcie, ktory znajduje sie wewnatrz okregu?
A co w przypadku, gdy obydwa punkty leza poza okregiem?
« Ostatnia zmiana: Sierpień 14, 2007, 04:30:13 wysłana przez snakeo »

RageX

  • Gość
# Sierpień 14, 2007, 04:36:07
Właściwie to punkty przecięcia kuli z odcinkiem liczysz w ten oto prosty sposób...
Liczysz najbliższy punkt na prostej. I masz prostopadłą - sam odcinek oraz najkrótszy dystans od sfery, koła do prostej. Sprawdzamy czy nasza sfera wogóle przecina prostą, bądź czy przypadkiem nie leży na prostej(czy nie ma tylko jednego punktu przecięcia), czyli czy dystans od środka sfery do odcinka nie jest równy (prawie równy, tak między bogiem a prawdą) promieniowi.
Jesli nie, to lecimy dalej.

Przyprostokątna 1 to odległość od środka sfery do punktu leżącego na prostej, najbliższego sferze.
Przeciwprostokątna to długość promienia.

Pamietaj, że powinniśmy miec dwa wyniki. :)
Sprawdzamy czy któreś  z tych rzutowań leży na odcinku. jeśli tak, to mamy punkt/punkty przecięcia.

Edit:
A tera pogłówkuje chwile... jak mozna tylko sprawdzić czy przecina, nie przecina...

Sprawdzamy to co w poście numer 1, czyli dystans od prostej. Jesli true.
Czy któryś z punktów leży w sferze, kole. jeśli false.
Rzutujemy środek kuli na odcinek. Jeśli rzutowanie mieści się w odcinku. gotcha... jak coś to to wcześniejsze sprawdzone, to tutaj, nie.
Edit2: właściwie przy kroku pierwszym, możemy z łatwością sprawdzić czy najbliższy punkt sferze na prostej, leży na odcinku... taka zamiana kolejności, celem optymalizacji. :) Czyli najpierw sfera - środek odcinka, a potem sfera - punkty.
 
« Ostatnia zmiana: Sierpień 14, 2007, 04:52:09 wysłana przez RageX »

RageX

  • Gość
# Sierpień 14, 2007, 04:51:11
Cytuj
Prosta prostopadla w ktorym punkcie chcesz prowadzic? W punkcie, ktory znajduje sie wewnatrz okregu?
Prosta prostopadla do prostej utworzonej przez poczatek i koniec odcinka i PRZECHODZACA PRZEZ WSPOLRZEDNE SRODKA OKREGU

Cytuj
A co w przypadku, gdy obydwa punkty leza poza okregiem?
Przypadek szczegolny - patrz pierwsze zdanie poprzedniego posta :)

Offline Piotr Wach

  • Użytkownik
    • Blog o programowaniu na urządzenia mobilne

# Sierpień 14, 2007, 09:53:07
Moze czegos nie widze ale chyba ostro przekombinowaliscie... masz poczatek i koniec odcinka, mozesz policzcyc prosta przechodzaca przez te punkty policzyc odleglosc od srodka okregu + sprawdzic czy poczatek lub koniec lezy wewnatrz okregu i masz sprawdzanie kolizji... ( tzn. masz wszystkie info jakie ci trzeba, musisz tylko pomyslce jak je ladnie ubrac w ify - bo oczywisice nie wszystkie warunki musza byc spelnione zeby byla kolizja ;p )

Offline Spider100

  • Moderator
    • Strona domowa

# Sierpień 14, 2007, 10:55:53
Witam!

Brakuje tu jeszcze kodu i można zamykać temat.

{------------------------------------------------------------------------------}
{ Odległosc pomiedzy punktem a odcinkiem }

function Distance_Point_Segment3D(const vP, vA, vB: TVector3D): Single;
var
  vAB, vAP, vU, vPoint: Tv3D;
  sABLen: Single;
  t: Single;
begin
  vAP := v3D_Sub(vP, vA); // Wektor Od A do punktu
  vAB := v3D_Sub(vB, vA); // Wektor OD A do  B
  sABLen := v3d_Length(vAB); // Dlugosc wektora AB
  vU := v3D_Scale(vAB, 1 / sABLen); //Normalizacja wektora AB
  t := v3D_Dot(vU, vAP); // rzutowanie na wektor vU
  if (t < 0) then // jesi rzut jest po za zasiegiem odcinka < 0
    vPoint := vA // przyjmujemy graniczny punkt A
  else if (t > sABLen) then // jesi rzut jest po za zasiegiem odcinka > 1
    vPoint := vB // przyjmujemy graniczny punkt B
  else // rzut znajduje sie na odcinku

// skalujemy znormalizowany wektor przez 'czas rzutu' i dodajemy do punktu A
    vPoint := v3D_ADD(vA, v3D_Scale(vU, t));

  result := v3D_Distance(vPoint, vP);
end;

Zasada jest taka:
Rzutujemy punkt na prosta przechodzącą przez odcinek.
Jeśli rzut jest w przedziale od 0 do 1 to znaczy że najbliższy punkt znajduje się na odcinku, a jeśli nie to na jego krańcach.
Wystarczy porównać podległość najbliższego punktu z promieniem okręgu.
KONIEC

Pozdrawiam!
Spider ^*^

Offline ziomber

  • Użytkownik

  • Zbanowany
# Sierpień 14, 2007, 11:54:41
no bo wlasnie chodzi o to zeby sprawdzic czy najblizszy punkt odcinka do srodka sgfery jest mniejszy lub równy promieniowi okregu, nie wiem czy ktos to juz napisal ale kod jest taki:
function ClosestPointOnLine (vA, vB, vPoint : t3dpoint) : t3dpoint;
//Returns the closest point on a line to a given point

var
  vVector1, vVector2, vVector3 : t3dpoint;
  vClosestPoint : t3dpoint;
  D, T : Single;

begin
  //First, we create a vector from our end point vA to our point vPoint
  vVector1.X := vPoint.X - vA.X;
  vVector1.Y := vPoint.Y - vA.Y;
  vVector1.Z := vPoint.Z - vA.Z;

  //Now we create a normalized direction vector from end point vA to end point vB
  vVector2.X := vB.X - vA.X;
  vVector2.Y := vB.Y - vA.Y;
  vVector2.Z := vB.Z - vA.Z;
  vVector2 := Normalize (vVector2);

  //Now we use the distance formula to find the distance of the line segment
  D := n3ddistance(vA, vB);

  //Using the dot product, we project the vVector1 onto the vector vVector2. This essentially
  //gives us the distance of our projected vector from vA
  T := Dot(vVector2, vVector1);

  //If our projected distance from vA, "t",  is greater than or equal to 0, it must be closest to the end point
  //vA.  So we return this end point.
  if (T<=0) then
  begin
    Result := vA;
    exit;
  end;

  //If our projected distance from vA, "t", is greater than or equal to the magnitude or distance of the line
  //segment, it must be closest to the end point vB, so we return vB.
  if (T >=D) then
  begin
    Result := vB;
    exit;
  end;

  //Here we create a vector that is of length T and in the direction of vVector2
  vVector3.X := vVector2.X * T;
  vVector3.Y := vVector2.Y * T;
  vVector3.Z := vVector2.Z * T;

  //To find the closest point on the line, we just add vVector3 to the original end point vA
  vClosestPoint.X := vA.X + vVector3.X;
  vClosestPoint.Y := vA.Y + vVector3.Y;
  vClosestPoint.Z := vA.Z + vVector3.Z;

  Result := vClosestPoint;
end;

Offline biki

  • Użytkownik

# Sierpień 14, 2007, 12:35:48
a moze by tak?
int Hit(vector &p1,vector &p2,vector &s,float r) {
float delta,t1,t2;
float a,b,c;
vector q;
 
  q=p1-s; v=p2-p1;
  a=v*v;   b=2*q*v;  c=q*q-r*r;
  delta=b*b-4*a*c;
  if (delta<0) return 0;
    t1=(-b-sqrt(delta)/(2*a);
    t2=(-b+sqrt(delta)/(2*a);
    if (t1<0 && t2<0) return 0;
    if (t1>1 && t2>1) return 0;
    return 1;
}
« Ostatnia zmiana: Sierpień 14, 2007, 15:46:43 wysłana przez biki »

Offline Goliatus

  • Użytkownik
    • Warsztat - tworzenie gier

# Sierpień 14, 2007, 13:51:17
Może tak jak tutaj: http://wiki.warsztat.gd/Kolizja_w_czasie ?

Masz okrąg o środku w punkcie O i promieniu R oraz punkt, który przemieszcza się w czasie t=1 o długość odcinka zgodnie z jakimś wektorem v, który jest równoległy do odcinka i ma jego długość.
[tex]\begin{cases}
v = p1 - p0 \\
p(t) = p0 + v * t \\
d(O, p(t)) = R
\end{cases}[/tex]

Musisz teraz tego równania wyliczyć t. Wyjdzie trójmian kwadratowy. Jeśli odcinek jest styczny to delta jest równa zero, jeśli większa od zero to prosta przecina w dwóch punktach, a odcinek, gdy t jest mniejsze od 1 i większe od 0. Delta mniejsza od zero to wtedy nie przecina.

Jak sobie rozwiążesz to równanie to masz już gotowy kod.

P.S dałem na wiki: http://wiki.warsztat.gd/Kolizja_w_czasie#Punkt_-_okr.C4.85g.28nieruchomy.29
« Ostatnia zmiana: Sierpień 14, 2007, 14:24:14 wysłana przez Goliatus »

RageX

  • Gość
# Sierpień 14, 2007, 14:02:56
wachu... no właśnie nie... bo możesz mieć koło które przecina odcinek, a nie zawiera w sobie żadnego z punktów. Stąd musisz sprawdzić... albo po naszemu... czyli jak ja napisałem i spider100.. albo tak jak maxest (w gruncie rzeczy to sprawdzenie tego samego, ale "chyba" wolniejsze).
PS. Po prostu musiałem zweryfikować nie prawdę. :)

Co do kodów... nie jestem w stanie zweryfikować... za dużo różnego kodu. mhihi.

A co do kolizji w czasie... :D

Offline kryzys

  • Użytkownik

# Sierpień 14, 2007, 15:54:05
Cytuj
A co do kolizji w czasie...  :D
W tym przypadku nie chodzi konkretnie o kolizje w czasie, ale o przedstawienie odcinka za pomocą równania z parametrem t.
« Ostatnia zmiana: Sierpień 14, 2007, 15:56:40 wysłana przez kryzys »