Autor Wątek: Czy punkt leży w trapezie/trójkącie/po której stronie prostej?  (Przeczytany 1610 razy)

Offline programistagd

  • Użytkownik
    • WeHaveIdea

# Czerwiec 17, 2010, 14:59:55
Witam!
Nie jestem specjalnie zaawansowany z matematyki - jeszcze niestety nie uczyłem się równań prostych itp.
Nie do końca to rozumiem.
Przejdę do rzeczy. Potrzebuję określić czy dany punkt znajduje się w trapezie równoramiennym.
Wszystko oczywiście dzieje się w kartezjańskim układzie współrzędnych z odwróconą osią Y.
Wiem jak sprawdzić, czy punkt znajduje się w prostokącie i mogę sprawdzić po prostu, czy znajduje się w jednym z jakichś trójkątów(przy bokach trapezu).
Inny sposób to określić, czy punkt jest poniżej górnego boku trapezu, powyżej dolnego(tego nie potrzebuję) i czy jest Po tej samej stronie prostej co punkt pomocniczy np. P, który "ręcznie" ustawiłbym około środka trapezu.
Umiem oczywiście określić czy jest pod czy nad prostą poziomą lub pionową, ale potrzebuję wzoru na określenie tego w przypadku prostej pod kątem(znam jej początek i koniec odcinka którego jest wydłużeniem).
Proszę więc o pseudokod(lub kod w C++) jak sprawdzić na podst. jednego z tych sposobów czy punkt znajduje się w trapezie.
Czytałem to: http://www.math.us.edu.pl/~szyjewski/FAQ/geo_anal/wewnatrz.htm, ale nie zbyt to rozumiem.
Z góry dziękuję za odpowiedź.
@down(Badfellas): Bardzo mi pomogłeś, jak się pytam to nie oczekuję takich rzeczy tylko sensownych wypowiedzi. Czyżbyś bezsensownie nabijał posty?
« Ostatnia zmiana: Czerwiec 17, 2010, 15:33:58 wysłana przez programistagd »

Offline Mr. Spam

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

Offline Xirdus

  • Redaktor

# Czerwiec 17, 2010, 15:45:07
1. patrzysz, czy x punktu jest między najbardziej lewym i najbardziej prawym wierzchołkiem, a y między podstawą górną i dolną (wyjdzie ci taki prostokąt co zawiera w sobie dany trapez). Jeśli nie, to na pewno nie leży. Jeśli tak, to:
2. Trapez możesz podzielić na prostokąt i dwa trójkąty po bokach. Prostokąt z punktu 1. zaś można podzielić na trapez i dwa trójkąty przyległe do tego trapezu - i właśnie te ostatnie trójkąty sprawdzasz. Jeśli punkt leży na którymś z nich, to NIE leży na trapezie.

Ogólnie to ma wyglądać tak:
Kod: (cpp) [Zaznacz]
if (1)
{
    if (2) return false;
    else return true;
};
else return false;
Funkcje 1 i 2 zostawiam jako zadanie do samodzielnego rozwiązania. (Jak se nie poradzisz do 17, dam ci rysunek pomocniczy; teraz nie mam czasu, sry).

Offline pimp

  • Użytkownik

# Czerwiec 17, 2010, 16:38:05
Bez sensu jest robienie z trapezu osobnego przypadku. Wszystkie wielokąty wypukłe da się obsłużyć jednym algorytmem - testujesz "normalne" krawędzi wielokąta z wektorem od wierzchołka krawędzi do punktu poprzez iloczyn skalarny i jak w jakimś przypadku będzie on > 0 to punkt jest poza wielokątem, jak będzie == 0 to jest na krawędzi, jeżeli dla każdej krawędzi będzie < 0 to punkt jest w środku.

Offline programistagd

  • Użytkownik
    • WeHaveIdea

# Czerwiec 17, 2010, 17:49:43
Najważniejszy byłby dla mnie jakiś wzór/funkcja: podaję w nim x,y punktów A,B,C i D.
Punkty A i B tworzą odcinek, którego przedłużeniem jest prosta, która dzieli płaszczyznę na dwie półpłaszczyzny.
Punkt C to punkt "kontrolny".
Punkt D to punkt do sprawdzania.
Funkcja zwraca true/wzór ma jakiś dany wynik gdy punkty C i D leżą na tej samej półpłaszczyźnie.
Edit: Udało mi się znaleźć wzór na to czy jest w trójkącie - teraz już pójdzie gładko.
Funkcja:
/* Kod pochodzi z http://peb.pl/programowanie/463003-c-czy-punkt-lezy-wewnatrz-trojkata.html */
public boolean jestWewnatrz(float px, float py)  // wpolrzedne szukanego punktu
    { float d1, d2, d3;   // warunki
      d1 = px*(Ay-By) + py*(Bx-Ax) +
           (Ax*By-Ay*Bx);
      d2 = px*(By-Cy) + py*(Cx-Bx) +
           (Bx*Cy-By*Cx);//tu był błąd, już poprawiony
      d3 = px*(Cy-Ay) + py*(Ax-Cx) +
           (Cx*Ay-Cy*Ax);
      return ((d1<=0)&&(d2<=0)&&(d3<=0)) || ((d1>=0)&&(d2>=0)&&(d3>=0));
    }
Przerobiłem to na C++.
Jest tylko błąd, ok poprawiłem tu na górze.
Dziękuję za pomoc.
« Ostatnia zmiana: Czerwiec 17, 2010, 21:28:45 wysłana przez programistagd »