Witam! Mam projekt, w którym potrzebuję pobrać wszystkie wierzchołki należące do danego wielokąta wraz z tymi leżącymi na krawędzi. Przykładowo mam podanych "i" wierzchołków i dla każdego wierzchołka jego współrzędne $x[i] i $y[i].

Nie wiem kompletnie jak się za to zabrać może macie jakiś pomysł, choćby wskazówkę na zaczęcie tego skryptu?

Pozdro i z góry dzięki ; )

PS: Dodam, że wielokąt może być wklęsły.

Masz to na obrazku czy w jakiejś tablicy?

W tablicy. Mam podane współrzędne wierzchołków, wierzchołki występują kolejno po sobie.

No to nie kumam o co chodzi, skoro masz już te wierzchołki w tablicy...

Przepraszam, pisałem na szybko, chodziło o wszystkie punkty należące do danego wielokąta, nie wierzchołki .

To może pomóc: http://blog.vokiel.com/klasa-php-rozwiazuj...tu-do-wielokata
btw: pierwszy wynik z google

Ale to sprawdza jeden punkt, który podam, a ja chcę pobrać do tablicy wszystkie punkty. A sprawdzanie każdego możliwego punktu z danego zakresu byłoby nie optymalne : /

Ale nie jesteśmy w dziale gotowe rozwiązania.
Dałem Ci przykład, który możesz sobie rozwinąć do własnych potrzeb. Zapewne nie widziałeś tej strony: http://en.wikipedia.org/wiki/Point_in_polygon ani tej: http://alienryderflex.com/polygon/ , bo inaczej byś wiedział, że jest to najlepszy algorytm w stosunku pewność wyniku/ łatwość implementacji. Jeżeli Ci ta metoda nie odpowiada, to zainteresuj się Metodą elementów skończonych. Sprawdziłoby się do podzielenia figury na trójkąty, a wtedy sprawdzenie dla punktu możesz przeprowadzić już na bardzo wiele sposobów: http://stackoverflow.com/questions/2049582...t-in-a-triangle || http://www.blackpawn.com/texts/pointinpoly/default.html || http://math.stackexchange.com/questions/51...by-three-points

Dzięki, już wiem jak to przekształcić : )