algorytm przekształcający linie w wielokąt

Cześć,

Mam pytanie, czy istnieją (jeżeli tak to jakie) algorytmy, które potrafią przekształcić linie w wielokąt, ale w ten sposób, że tworzy on tak jak by tunel, otoczkę wzdłuż tej linii?;>

Pozdrawiam

Jakie linie (proste, krzywe?), jakie wielokąty? Narysuj jakiś przykład.

W załączniku zamieściłem obrazek ukazujący cel jaki chce osiągnąć. Pierwszy rysunek pokazuje linie jaką mam na wejściu, drugi rysunek pokazuje ta linie oraz na czerwono zakolorowany "tunel" jaki chciałbym mieć.

Czyli masz jedną krzywą łamaną i musisz dodać dwa równoległe odcinki, których środek wypada w końcach krzywej. Dodatkowo jeszcze chcesz narysować dwie takie same krzywe przesunięte tak, żeby kończyły się na końcach odcinków?

Możesz także przesunąć każdy z elementów krzywej w obie strony, robiąc proste, a po tym wielokąt ograniczyć do przecięć kolejnych prostych oraz prostych prostopadłych do końców krzywej.

Do rysowania to bym zrobił po prostu szereg prostokątów. Nie wiem jak inne biblioteki, ale opengl wymaga wielokątów wypukłych.

http://cgcad.thss.tsinghua.edu.cn/~yongjh/papers/CiI2007V58N03P0240.pdf
Masz gotowy algorytm od Chińczyków ;).

http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/BezierFlattening.pdf
A tutaj dla krzywych Beizera.

Podstawowym będzie wyznaczenie pewnego charakterystycznego punktu dla danej pary sąsiednich odcinków - miejsca gdzie obwiednia załamuje się. Może są jakieś inne metody ale ja bym zrobił to to według następującego schematu. Rysunek pomoże :)

Wspomniana para odcinków to AB i BC, a raczej para wektorów gdyż musimy przyjąć kierunek dla łamanej . Wyznaczany punkt załamania obwiedni to P. Za "grubość" obwiedni przyjmijmy 2r (na rysunku wektory u i v mają długość r). Niech
A=(x1,y2)
B=(x2,y2)
C=(x3,y3)
Prosta k może być opisana przy pomocy "równania prostej przechodzącej przez dwa punkty", te punkty to A i B czyli:
k: (x2-x1)(y-y1)=(y2-y1)(x-x1)
Wektor u można skonstruować obracając wektor AB o 90° w prawo i dostosowując długość:
u=(ux,uy)=AB^-90°·|v|/|AB|=(y1-y2,x2-x1)·r/|AB|
Czyli
ux=(y1-y2)·r/|AB|
uy=(x2-x1)·r/|AB|
Długość |AB| wyliczamy z Pitagorasa.
Aby przesunąć jakąś prostą o wektor u wystarczy w jej równaniu od każdego x odjąć ux a od każdego y odjąć uy. Stąd prosta k' (czyli k przesunięte o u) będzie mieć równanie:
k': (x2-x1)(y-y1-uy*)=(y2-y1)(x-x1**-ux**)
Analogicznie prosta b' będzie mieć równanie:
b': (x3-x2)(y-y2-vy)=(y2-y1)(x-x1-vx)
Rozwiązujesz układ równań (punkt przecięcia prostych k' i b') i masz punk P.

Jak wspomniałem wcześniej, analogicznie wyliczasz punkt z lewej strony łamanej. Trzeba obracać wektor w lewo a nie w prawo tym razem czyli zamiast u jest -u a zamiast v jest -v.

W ten sposób możesz wyznaczyć kolejne punkty obwiedni iterując po łamanej. Na końcach łamanej trzeba osobno dodać po 2 punty. Można je prosto wyliczyć. Dla przykładu, jeśli tym końcem jest punkt A to punktami będą A+v oraz A-v.

Ale to jeszcze nie koniec. W pewnych przypadkach odcinki obwiedni będą przecinać się na wzajem dlatego trzeba ją zredukować. Wyszukujesz punkty przecięcia i usuwasz zbędne "pętelki". Tylko uwaga! Tu trzeba trochę pomyśleć. Musisz wybrać odpowiedni kierunek i stronę.

*Słowo "linia" znaczy zupełnie coś innego jeśli poruszamy się w pobliżu geometrii. Wszyscy znamy takie terminy jak "odcinek", "krzywa" itd., warto ich używać, prędzej się dogadasz ;) .