Niezupełnie off-topic, tak dla rozrywki.

Jest skończony ciąg punktów (na płaszczyźnie, ale jak kto chce może być 3D,
może być przestrzeń n-wymiarowa itd.). To znaczy, w uproszczonym wariancie,
jest n par (x[k], y[k]).

Trzeba algorytmicznie skonstruować krzywą, przechodząca kolejno przez te
punkty, o długości nie większej niż L, przy czym L jest rozsądne, tj.
większe niż długość łamanej je łączącej. Można założyć, że np. 2 razy
większe. Krzywa ta jednak ma mieć minimalną krzywiznę w sensie normy
maksimum, tj. dla najlepszej krzywej krzywizna nawet w najgorszym miejscu
(na ostrym zakręcie) jest możliwie mała. Tak mała, że po prostu mniejsza być
nie może, bo nie.

Dodatkowe założenia: współrzędne punktów są liczbami zmiennoprzecinkowymi od
0. do 100., punktów jest nie więcej niż 100, krzywą wystarczy wyznaczyć z
dokładnością nie gorszą niż 0.01 (tzn. obszar 100x100 metrów, pozycjonowanie
nie gorsze niż 1 cm). Albo jakoś tak.

'Background' to np. znalezienie trajektorii, po której robot jadący ze stała
wartością prędkości będzie ulegał najmniejszym przyspieszeniom itd.
(przypominam, siła od/do-środkowa zależy od krzywizny, przy stałej prędkości
im mniejsza krzywizna tym lepiej).

A, jeszcze drobiazg - gdzieś tam napotkałem na błędne oszacowanie. Tymczasem
dla dowolnie dużego L, czyli bez ograniczeń, minimalna krzywizna wynosi
dokładnie zero - robocik-komiwojażer jedzie przez punkt i dalej po prostej,
a zakręca gdzieś w nieskończoności.

slawek

do góry

W dniu środa, 24 kwietnia 2013 20:41:50 UTC+2 użytkownik slawek napisał:
> Niezupełnie off-topic, tak dla rozrywki.
>
>
>
> Jest skończony ciąg punktów (na płaszczyźnie, ale jak kto chce może być 3D,
>
> może być przestrzeń n-wymiarowa itd.). To znaczy, w uproszczonym wariancie,
>
> jest n par (x[k], y[k]).
>
>
>
> Trzeba algorytmicznie skonstruować krzywą, przechodząca kolejno przez te
>
> punkty, o długości nie większej niż L, przy czym L jest rozsądne, tj.
>
> większe niż długość łamanej je łączącej. Można założyć, że np. 2 razy
>
> większe. Krzywa ta jednak ma mieć minimalną krzywiznę w sensie normy
>
> maksimum, tj. dla najlepszej krzywej krzywizna nawet w najgorszym miejscu
>
> (na ostrym zakręcie) jest możliwie mała. Tak mała, że po prostu mniejsza być
>
> nie może, bo nie.
>
>
>
> Dodatkowe założenia: współrzędne punktów są liczbami zmiennoprzecinkowymi od
>
> 0. do 100., punktów jest nie więcej niż 100, krzywą wystarczy wyznaczyć z
>
> dokładnością nie gorszą niż 0.01 (tzn. obszar 100x100 metrów, pozycjonowanie
>
> nie gorsze niż 1 cm). Albo jakoś tak.
>
>
>
> 'Background' to np. znalezienie trajektorii, po której robot jadący ze stała
>
> wartością prędkości będzie ulegał najmniejszym przyspieszeniom itd.
>
> (przypominam, siła od/do-środkowa zależy od krzywizny, przy stałej prędkości
>
> im mniejsza krzywizna tym lepiej).
>
>
>
> A, jeszcze drobiazg - gdzieś tam napotkałem na błędne oszacowanie. Tymczasem
>
> dla dowolnie dużego L, czyli bez ograniczeń, minimalna krzywizna wynosi
>
> dokładnie zero - robocik-komiwojażer jedzie przez punkt i dalej po prostej,
>
> a zakręca gdzieś w nieskończoności.
>

ja niby interesuje sie tematem gier 2d
i ruchami/trajektoriami na plaszczyznie
(beziery itp) ale z tymi krzywiznami to
jednak wydaje mi sie na tyle odlegle
od jakiejs praktycznej potrzeby ze nie
bardzo chce mi sie to rozwarzac (a
z kolei matematyczna algorytmika tez
mi osobiscie nie bardzo podchodzi - mam
tyle praktycznego drobnego cholerstwa
do zakodowania ze i tak nie wyrabiam )

do góry

> [..] nie
> bardzo chce mi sie to rozwarzac [..]

a) tnij cytaty
b) "rozważać"
c) jeśli nie masz nic do powiedzenia w temacie, to po co spamujesz
wszędzie tymi swoimi "grami 2d"?

--
Pozdrawiam,
Stregor

do góry

Użytkownik "firr kenobi" napisał w wiadomości grup
dyskusyjnych:8a94a5b3-4dbc-42e3-b62f-416c5cc30123@go
oglegroups.com...

>(beziery itp) ale z tymi krzywiznami to
>jednak wydaje mi sie na tyle odlegle
>od jakiejs praktycznej potrzeby ze nie

Wydaje ci się. Taka trajektoria - o minimalnej krzywiźnie (minimalnej
maksymalnej krzywiźnie) - to po prostu sposób na możliwie najspokojniejsze
przejście od punktu A do B, potem C, D, E, F itd. Zakładając stałą wartość
prędkości. (Hint, łamana ma zerową krzywiznę... ale w punktach A, B, C, ...
po prostu "szarpie" - nie ma ciągłej pochodnej.)

do góry

On Sat, 27 Apr 2013 17:48:25 +0200, "slawek" <h...@s...pl> wrote:

>Użytkownik "firr kenobi" napisał w wiadomości grup
>dyskusyjnych:8a94a5b3-4dbc-42e3-b62f-416c5cc30123@g
ooglegroups.com...
>
>>(beziery itp) ale z tymi krzywiznami to
>>jednak wydaje mi sie na tyle odlegle
>>od jakiejs praktycznej potrzeby ze nie
>
>Wydaje ci się. Taka trajektoria - o minimalnej krzywiźnie (minimalnej
>maksymalnej krzywiźnie) - to po prostu sposób na możliwie najspokojniejsze
>przejście od punktu A do B, potem C, D, E, F itd. Zakładając stałą wartość
>prędkości. (Hint, łamana ma zerową krzywiznę... ale w punktach A, B, C, ...
>po prostu "szarpie" - nie ma ciągłej pochodnej.)

A o splajnach Panowie slyszeli?...

A.L.

do góry

Użytkownik "A.L." napisał w wiadomości grup
dyskusyjnych:mctnn8lh8v8sq9sum27n96ua6b5huap4m8@4ax.
com...

>A o splajnach Panowie slyszeli?...

A i co sobie z funkcjami sklejanymi zrobisz?

Nota bene, funkcje sklejane bywają różne - naprawdę jest tego znacznie
więcej, niż Jankowscy kiedykolwiek opisali. Niemniej jednak, funkcja
sklejana nie ma, zazwyczaj, STAŁEJ krzywizny - stałą to mają tylko prosta i
okrąg. A skoro nie ma stałej, to można polimeryzować czy jest optymalna w
sensie zagadnienia. Ogólniej - problem haczy o rachunek wariacyjny i
geometrię różniczkową - co samo w sobie jest przyjemne. Bo zwróć uwagę -
masz punkty, ale nie masz czasów. Najlepiej byłoby tę krzywą sparametryzować
przez s, tj. mieć równania na krzywiznę i skręcenie wyrażone długością łuku.
Choć oczywiście na początku nie masz długości łuku. Na płaszczyźnie nie
będzie potrzebne skręcenie.

do góry

W dniu 2013-04-27 17:58, A.L. pisze:
> On Sat, 27 Apr 2013 17:48:25 +0200, "slawek" <h...@s...pl> wrote:
>
>> Użytkownik "firr kenobi" napisał w wiadomości grup
>> dyskusyjnych:8a94a5b3-4dbc-42e3-b62f-416c5cc30123@go
oglegroups.com...
>>
>>> (beziery itp) ale z tymi krzywiznami to
>>> jednak wydaje mi sie na tyle odlegle
>>> od jakiejs praktycznej potrzeby ze nie
>>
>> Wydaje ci się. Taka trajektoria - o minimalnej krzywiźnie (minimalnej
>> maksymalnej krzywiźnie) - to po prostu sposób na możliwie najspokojniejsze
>> przejście od punktu A do B, potem C, D, E, F itd. Zakładając stałą wartość
>> prędkości. (Hint, łamana ma zerową krzywiznę... ale w punktach A, B, C, ...
>> po prostu "szarpie" - nie ma ciągłej pochodnej.)
>
> A o splajnach Panowie slyszeli?...
>

Jeśli chodzi o sklejanie, to ok, ale splajny to jednak wielomiany,
Maksymalna krzywizna będzie tam punktowa, a w tym problemie
rozwiązanie siedzi najprawdopodobniej w okolicach okręgów.

pzdr
bartekltg

do góry

W dniu środa, 24 kwietnia 2013 20:41:50 UTC+2 użytkownik slawek napisał:
> Niezupełnie off-topic, tak dla rozrywki.
> Jest skończony ciąg punktów (na płaszczyźnie, ale jak kto chce może być 3D,
> [...]
> a zakręca gdzieś w nieskończoności.

Ciekawe zadanko. Można podejść na wiele sposobów. Rozumiem że krzywa
łamana jest już dana. Co myślisz o takim podejściu: Dla każdej pary
połączonych punktów wyznaczamy odcinek prostopadły do środka łączącego
ich odcinka o długości proporcjonalnej do długości odcinka. Współczynnik
proporcjonalności im większy, tym krzywizna będzie większa. Potem dodajemy
sztuczne punkty leżące na końcu odcinków. Operację powtarzamy kilka razy,
może 3 razy, może 5. Przy współczynniku proporcjonalności równym zero,
wszystkie nowe punkty będą leżały na odcinku. Im większy (dodatni) współczynnik
tym nowe punkty będą leżały dalej. Na koniec jakieś splajny z uwzględnieniem
nowych punktów.

Pozdrawiam

do góry

On Sat, 27 Apr 2013 18:31:39 +0200, "slawek" <h...@s...pl> wrote:

>Użytkownik "A.L." napisał w wiadomości grup
>dyskusyjnych:mctnn8lh8v8sq9sum27n96ua6b5huap4m8@4ax
.com...
>
>>A o splajnach Panowie slyszeli?...
>
>A i co sobie z funkcjami sklejanymi zrobisz?
>

Rozne rzeczy

>Nota bene, funkcje sklejane bywają różne - naprawdę jest tego znacznie
>więcej, niż Jankowscy kiedykolwiek opisali.

Naprawde?...

>Niemniej jednak, funkcja
>sklejana nie ma, zazwyczaj, STAŁEJ krzywizny - stałą to mają tylko prosta i
>okrąg. A skoro nie ma stałej, to można polimeryzować czy jest optymalna w
>sensie zagadnienia.

Ze co?..

>Ogólniej - problem haczy o rachunek wariacyjny i
>geometrię różniczkową - co samo w sobie jest przyjemne. Bo zwróć uwagę -
>masz punkty, ale nie masz czasów.

Jakich czasow?...

>Najlepiej byłoby tę krzywą sparametryzować
>przez s, tj. mieć równania na krzywiznę i skręcenie wyrażone długością łuku.
>Choć oczywiście na początku nie masz długości łuku. Na płaszczyźnie nie
>będzie potrzebne skręcenie.

Pzreparszam, ale to belkot totalny

A.L.

do góry

On Sat, 27 Apr 2013 18:47:22 +0200, bartekltg <b...@g...com>
wrote:

>W dniu 2013-04-27 17:58, A.L. pisze:
>> On Sat, 27 Apr 2013 17:48:25 +0200, "slawek" <h...@s...pl> wrote:
>>
>>> U?ytkownik "firr kenobi" napisa? w wiadomo?ci grup
>>> dyskusyjnych:8a94a5b3-4dbc-42e3-b62f-416c5cc30123@go
oglegroups.com...
>>>
>>>> (beziery itp) ale z tymi krzywiznami to
>>>> jednak wydaje mi sie na tyle odlegle
>>>> od jakiejs praktycznej potrzeby ze nie
>>>
>>> Wydaje ci si?. Taka trajektoria - o minimalnej krzywi?nie (minimalnej
>>> maksymalnej krzywi?nie) - to po prostu sposób na mo?liwie najspokojniejsze
>>> przej?cie od punktu A do B, potem C, D, E, F itd. Zak?adaj?c sta?? warto??
>>> pr?dko?ci. (Hint, ?amana ma zerow? krzywizn?... ale w punktach A, B, C, ...
>>> po prostu "szarpie" - nie ma ci?g?ej pochodnej.)
>>
>> A o splajnach Panowie slyszeli?...
>>
>
>Je?li chodzi o sklejanie, to ok, ale splajny to jednak wielomiany,

Owszem, ale sa tez "exponential splines". Ale to zupelnie inne zwierze
:)

>Maksymalna krzywizna b?dzie tam punktowa,

No to co? Przeciez tam chodzi o minimalizacje maksymalnej lrzywizny.
Na caalej krywej

Poza tym, splajny maja pewne wlasnosci "wariacyjne", w szczegolnosci
parametr zwany "tension" (napiecie). Znane sa procedury konstruujace
splajny z ograniczeniem na owo "napiecie". Nie jest to dokladnie
krzywizna, ale byc moze blisko. Trudno powiedziec jak sie nie wie po
co to wszystko Procedura jest opisana na przykald tu

Renka, R.J., (1987), “Interpolatory tension splines with automatic
selection of tension factors”, SIAM Journal of Scientific and
Statistical Computing,
Volume 8, p. 393-415.

Dostepny na przykald tutaj

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.
1.1.76.3808

Oczywiscie zawsze mozna problem sformulowac jako zadanie wariacyjne z
ograniczeniami

A.L.

do góry