Autor Wątek: Punkt przecięcia 2 odcinków  (Przeczytany 3014 razy)

Offline gmpro

  • Użytkownik

# Sierpień 28, 2010, 20:32:23
Poszukuję algorytmu który by odnalazł punkt przecięcia 2 odcinków. Od razu uprzedzam że nie chodzi mi o sprawdzanie przecięcia 2 prostych pokrywających się z tymi odcinkami (tyle to sam wygooglowałem) Jest wiele fajnych wzorów bazujących na iloczynach skalarnych, wektorowych itp. wiec może jest też jakiś sposób na szybkie obliczenie punktu przecięcia bez konieczności używania prostych.

Często gdy zadaję pytanie dot. fizyki matematyki to potem dostaję komenty że nie wiadomo o czym piszę, więc użyłem moich nadzwyczajnych umiejętności tworzenia grafiki 3D i wymodelowałem ;d w MS Paincie schemiacik (patrz załącznik)

Offline Mr. Spam

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

Offline Oti

  • Użytkownik

# Sierpień 28, 2010, 20:40:14
Mogę dać ci kod:

Kod: (cpp) [Zaznacz]

#define MAXFLOAT 9999999

class Vector2
{
public:
float x,y;
bool operator == (Vector2 W)
{
return x==W.x&&y==W.y;
}
bool operator != (Vector2 W)
{
return x!=W.x&&y!=W.y;
}
void operator += (Vector2 W)
{
x+=W.x; y+=W.y;
}
void operator -= (Vector2 W)
{
x-=W.x; y-=W.y;
}
Vector2 operator + (Vector2 W) const
{
return Vector2(x+W.x,y+W.y);
}
Vector2 operator - (Vector2 const &W) const
{
return Vector2(x-W.x,y-W.y);
}
float operator * (Vector2 const &W) const
{
return x*W.y-y*W.x;
}
Vector2 operator * (float L) const
{
return Vector2(x*L,y*L);
}
float GetLenght()
{
return abs(sqrt(x*x+y*y));
}
float Normalize()
{
float len=GetLenght();
x/=len; y/=len;
return len;
}
Vector2() {x=0; y=0;}
Vector2(float _x, float _y) {x=_x; y=_y;}
};

class Odcinek
{
public:
Vector2 ps,pe;
float CzyPrzeciecie(Odcinek Odc, Vector2 *pp) const;
Odcinek() {}
Odcinek(Vector2 poczatek, Vector2 koniec) {ps=poczatek; pe=koniec;}
};

float Odcinek::CzyPrzeciecie(Odcinek Odc, Vector2 *pp) const
{
Vector2 A1=pe-ps, A2=Odc.pe-Odc.ps;
Vector2 B=Odc.ps-ps;
float Wz=A2*A1;
if(Wz==0) return MAXFLOAT;
float t=(A1*B)/Wz;
if(t < 0 || 1 < t) return MAXFLOAT;
t=(A2*B)/Wz;
if(t < 0 || 1 < t) return MAXFLOAT;
*pp=A1*t+ps;
return t;
}
Funkcja CzyPrzeciecie zwraca MAXFLOAT jeśli nie ma przecięcia, lub (o ile dobrze pamiętam) wartość 0-1(lub 0-długosc_odcinka) oznaczającą w którym miejscu odcinek został przecięty i zapisuje do *pp pozycję punktu przecięcia. Kod nie jest mój, więc nie pytaj o szczegóły. ;d

Offline gmpro

  • Użytkownik

# Sierpień 28, 2010, 20:44:45
Naprawdę wielkie dzięki za to ;]

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Sierpień 30, 2010, 09:53:52
Nie ma się co buntować przeciwko sprawdzaniu najpierw kolizji prostych. Odcinek to podzbiór prostej. Gdybyś chciał testować kolizje z wycinkiem okręgu, to chyba jasne, że należałoby najpierw policzyć kolizję okręgów, a potem sprawdzić, czy punkt kolizji należy do takiego wycinka. Tak samo w kodzie, który podał Oti, dla punktu przecięcia prostych wyliczony zostaje parametr t i następuje sprawdzanie, czy należy on do przedziału 0..1 - co znaczy, że punkt należy do odcinka.

Offline yorp

  • Użytkownik
    • ProfessionGG Project

# Sierpień 30, 2010, 10:27:14
i dobrze jest jeszcze wczesniej zrobic test ktory sprawdza czy wogole sie tna te odcinki, a nie odrazu sprawdzac gdzie.
Pozdrawiam.

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Wrzesień 01, 2010, 10:27:39
W podanym wyżej kodzie to jest. Odcinki są równoległe, czyli nie mają jednego punktu przecięcia, kiedy Wz jest równe 0. Wtedy też nie można liczyć punktu przecięcia, bo nastąpiłoby dzielenie przez zero. Oti w swoim kodzie to sprawdza.

Offline Oti

  • Użytkownik

# Wrzesień 01, 2010, 11:59:00
Oti w swoim kodzie to sprawdza.
Nie swoim-sam tego nie napisałem, znalazłem gdzieś kiedyś w necie.