Witam
Podawane są 4 punkty (8 wspolrzednych) nie po kolei. I moim zadaniem jest okreslic kolejność tych punktów w czworokacie. Zna ktos jakis algorytm? Program musi byc w c++, moze sa tam jakies gotowe funkcje ktore moglyby pomoc w tym sprawdzaniu?
Wtf, Co to znaczy,że punkty są nie po kolei? Co to jest kolejność punktów w czworokącie?
Dużej filozofii to chyba nie ma :P
Powiedzmy szukamy najpierw lewego górnego rogu :
- patrzymy we wszystkich 4 punktach które dwa z nich są najwyżej położone względem współrzędnej y-kowej i wybieramy dwa z nich,
- porównujemy współrzędne tych dwóch wybranych po x-ie, tzn ten który będzie ją miał mniejszą jest lewym górnym punktem czworokąta.
Reszta analogicznie. ;)
no tak to rozwiązanie dla czworokątow wypukłych, a co jesli czworokąt jest wklesly? To juz wiekszy problem ;p
@matrek: A co z czworokątem takim?
..........3..
........./|..
......../+|..
......./++|..
..1===2+++|..
...\++++++|..
....\+++++|..
.....\++++|..
......\+++|..
.......\++|..
........\+|..
.........\|..
..........4..
Wyjdzie ci, że wierzchołek 1 jest lewy górny, a 3 prawy górny. Twój algo, jak myślę, pasuje tylko do czworokątów wypukłych.
Edit: za późno :/
Edit2: ale jak patrzę, to istnieją w powyższym przykładzie zarówno czworokąt 1-2-3-4, jak i 1-3-2-4. Czyli wtedy kolejność już chyba będzie dowolna...
No opisalem sytuacje troche dokladniej w zalaczniku. Zdaje mi sie ze wlasnie rysunek 3 ma poprawna kolejnosc punkto ale jak ja wyznaczyc :|
Ja bym liczył powierzchnię czworokątów i wybrał ten o największej powierzchni. Nie widzę innego obiektywnego sposobu.
Czym się kierowałeś wybierając trzeci rysunek za poprawny?
Btw, skąd wziąłeś problem, tzn jakiej tam używano definicji czworokąta? To też jest czworokąt: <img src="http://students.wmi.amu.edu.pl/~bogdan/images/Czworokat.jpeg"/img>
Kierowalem sie intuicja :P, a ten twoj rysunek to juz jest pieciokat moim zdaniem, chocby dlatego ze boki sie przecinaja tworzac kolejny wierzcholek.
Mylisz się, to jest czworokąt bo powstał z czterech odcinków. Przy Twojej interpretacji byłby to pięciokąt i sześciobok jednocześnie.
Jeżeli wyboru "jedynie słusznego" czworokąta dokonałeś intuicyjnie, to pozostaje Ci wyposażenie komputera w intuicję.