Zmiana rozmiaru zaznaczenia

Witam, mój problem polega na braku pomysłu przy zrealizowaniu zmiany rozmiaru zaznaczenia. Coś na wzór zwężenia, czy poszerzenia zaznaczenia w Photoshop'ie o zadaną ilość pikseli.
Nie mam pojęcia jak miałoby to wyglądać z matematycznego czy algorytmicznego punktu widzenia.
Od razu zaznaczam, iż nie chodzi tutaj o skalowanie, bo to całkiem co innego i nie rozwiązuje to problemu.
Przykładowo mając figurę klepsydry opisaną sześcioma punktami o wymiarach powiedzmy 100px x 200px i zawężając takie zaznaczenie o np. 50px; powstaną dwa małe trójkąty (jeden na górze drugi na dole). Potrzebuję współrzędne punktów tych nowych figur.
Potrzebuję funkcję najlepiej w Delphi, której argumentami będą tablica punktów (określa dowolną figurę, wielokąt) oraz ilość pikseli do zawężenia, a zwracającą tablicę tablic punktów nowo powstałych figur.
Deklaracja:

type
   TPoints = array of array of TPoint;

function ChengeSelect(Figure : array of TPoint; Distance : Byte) : TPoints;

figurę klepsydry opisaną sześcioma punktami o wymiarach powiedzmy 100px x 200px i zawężając takie zaznaczenie o np. 50px;
zawężając od której strony?

i o co ci właściwie chodzi? przycięcie figury o jakiś margines (zabranie n pikseli z każdej lub którejś strony)?

x_nowy = x_stary - (x_stary / (x_max - x_min)) * x_delta
gdzie
x_stary to aktualne położenie punktu
x_max to szerokość figury
x_min to 0
x_delta to o ile ma nastąpić zmiana szerokości

dla y analogicznie

Dokładnie, można powiedzieć, że przycięcie o margines.
Tylko może to być dowolna figura - wielokąt.

Azarien:
Ściśnięcie to w pewien sposób zmiana rozmiaru, a więc skalowanie, a to byłoby poprawne dla podstawowych figur jak kwadrat czy trójkąt, ale do złożonych wielokątów to nie zda egzaminu.
Misiekd:
Niestety, ale sposób skalowania nie rozwiązuje problemu.

Najlepiej to widać w Photoshopie.

no to nie mam pojęcia o co Ci chodzi - wiadomo, że piksel jest piksel i nie da się przesunąć punktu o np. 0,5 piksela bo się po prostu nie da. A mój sposób działa bardzo dobrze o ile oczywiście masz świadomość pewnych graniczeń samego sprzętu. Inna sprawa, że to o co pytałeś to jest grafika WEKTOROWA a PhotoShop nigdy obok takowej nawet nie stał!

Ta czarna ("zewnętrzna") figura to kształt wejściowy. Te trzy niebieskie ma zwrócić funkcja przekazując do niej współrzędne tej największej figury (czarnej) i odległość 20px powinna zwrócić trzy-elementową tablicę zawierającą tablice punktów tych trzech figur.
Po Twoim algorytmie Misiekd czarna figura wyglądała by identycznie jak teraz tylko byłaby mniejsza.
Oczywiście cały czas mam na myśli grafikę wektorową (zresztą współrzędne punktów o tym świadczą), jest ona generowana automatycznie, ale to nie ważne.
Jasna sprawa, że nie ma 0,5px dlatego zadowolę się przybliżeniem do 1px :) (piszę px bo łatwiej na tych jednostkach operować - domyślnie brak jednostek to są jedynie wartości). Figury są dość duże, rzędu tysięcy pikseli. Źle zapisałem typ punktów powinno być:

TPoints = array of array of record 
   X, Y : Extended;
end;

jeśli przekazujesz JEDNĄ tablicę (czyli JEDNĄ figurę) to na wyjściu dostajesz JEDNĄ tablicę (czyli JEDNĄ) figurę ale mniejszą/większą! Jak chcesz mieć TRZY na wyjściu to przekazujesz TRZY na wejściu. To takie trudne?? A jak ci się coś zmieni i zamiast trzech będziesz chciał mieć dwie albo pięć to algorytm ma się domyślać???? Zrozum FIGURA JEST FIGURA i program może ci ją zmniejszyć/zwiększyć ale NIE ROZBIĆ NA INNE!

Uwierz, że się da - twórcy Photoshopa i innych programów jakoś to rozwiązali, z resztą kolega mi pisał podobny algorytm, ale było w tym tyle matematyki, że się to strasznie pogmatwało i nie działało dla wszystkich figur. Nie wiem jak mam to jeszcze tłumaczyć przekazuję jedną figurę (najmniej złożoną, jednak mniej złożona niż podana wyżej jest nie możliwa). Algorytm byłby w stanie się domyślić, jeżeli zawężenia na siebie zachodzą tzn. figury się całkiem od siebie odcinają i powstają nowe.
Na początku przytoczony przeze mnie przykład klepsydry - jest ona zwężona po środku. Powiedzmy że podstawa i góra mają 100px, a jej zwężenie 50px (tu gdzie przesypuje się piasek).
Jeżeli zwężę tą klepsydrę o 25px (odległość od każdej ze ścian) to nie ma siły powstaną dwa trójkąty.
To tak jakby wyciął z kartki papieru taką klepsydrę i na około od każdej z jej krawędzi poodcinał po powiedzmy 1cm (te 25px) to kartka podzieli się na dwa trójkąty,a te ścinki do kosza ;)

Sam to też próbowałem robić wyznaczając funkcję liniowe tych wszystkich boków, przesuwając te funkcję o zadaną odległość i badając punkty ich przecięcia oraz ewentualne "zamknięcia" się funkcji wyznaczały kolejną figurę, ale to też nie działało dla każdego przypadku, głównie mam na myśli kąty rozwarte figury.

napiszę to jeszcze raz JEŚLI NA WEJŚCIU JEST JEDNA FIGURA TO NA WYJŚCIU TEŻ JEST JEDNA!
Napisz, gdzie photoshop ma taką opcję, bo ja nie widziałem. Dalej Photoshop nie jest programem do grafiki wektorowej więc on robi to całkiem inaczej! Tam nie ma figur - nawet jak narysujesz linię to ona nie jest figurą tylko zbiorem pikseli!

Dla mnie jeśli oryginalną figurą jest pierwsza to po zmniejszeniu o 25% z każdej strony poprawnym wynikiem jest dwa a nie trzy ponieważ dostaję na wejściu tą figurę jako całość i tak ją też traktuje!

Taką figurę jak ta trzecia corel Ci zrobi jeśli ta pierwsza to będą DWIE figury i jak zaznaczysz je obie. Ale to muszą być dwa trójkąty narysowane oddzielnie.

I jeszcze jedno - jeśli mam taką figurę opisaną CZERWONYMI punktami

to mam znaleźć punkt NIEBIESKI, rozbić ją na dwie figury i każdą potraktować osobno co da w efekcie takie coś

czy też potraktować ją jako całość i zwrócić takie coś

oczywiście nie ma tam zachowanych żadnych proporcji - ot mazanina w paincie

Widzę, że kompletnie się nie rozumiemy.
Mam polską wersję Photoshop'a, ale u mnie po zaznaczeniu obszaru lassem wielokątnym jest ta opcja w menu Zaznacz->Zmień->Zwężanie.
Ten program i tą jego funkcję podałem dla przykładu bo doskonale odzwierciedla to o co mi chodzi, nie ważne czy to grafika rastrowa czy wektorowa. Mi chodzi o algorytm, funkcje, bądź cokolwiek innego co rozwiązałoby ten problem. Na kartce próbuję rysować różne figury w układzie współrzędnych i kombinować jakimi przekształceniami matematycznymi dałoby się to zrealizować.

Bierzesz po uwagę jedynie proste figury, ale uwierz, że nie każdą się da rozłożyć na trójkąty czy kwadraty. Pisałem o klepsydrze ale trochę w innym wydaniu (specjalnie pisałem zwężenie gdzie przesypuje się piasek bo chodziło mi o... - zdjęcie).
Teraz tak nie upieraj się że jeżeli na wejściu jest jedna figura to na wyjściu będzie też jedna, bo to kompletna bzdura. Zresztą to przecież oczywiste po moich poprzednich rysunkach i w ogóle logicznie rzecz biorąc.

Po kolei - myślę, że nie trzeba tłumaczyć i pierwszy rysunek klepsydry (od lewej) jest to wielokąt, którego nie jestem w stanie rozłożyć na mniejsze figury!!! Tak jest i koniec kropka na początku pisałem, że chodzi mi o wielokąty (mogą być więc 100 boczne i to też wielokąt), a nie trójkąty tworzące wielokąt w jakikolwiek sposób.
Drugi obrazek pokazuje powstałe dwa wielokąty (w tym wypadku są to akurat trójkąty) i nie ma innej możliwości. Jeżeli zwężyłbym tą figurę o 1 to nie wiele się zmieni, ale tutaj zwężając w tym wypadku o 25 (nie piszę już px żeby ewentualnie nie mylić), to w miejscu gdzie są czerwone strzałki jest wymiar 40, a jak będę chciał zwężyć o 25 z każdej ze stron to 25 * 2 = 50 czyli więcej niż 40 więc powstają dwie figury. Moim zdaniem to banalne i nie mam pojęcia jak to tłumaczyć inaczej. Tak jak pisałem najlepiej to zrozumieć wycinając taką klepsydrę, którą narysowałem jako pierwszą i spróbować ją dookoła poobcinać od każdego z brzegów na odległość większą połowie tego przewężenia klepsydry (ujścia piasku), GWARANTUJĘ, ŻE KARTKI NIE WYSTARCZY I BĘDĄ DWA TRÓJKĄTY.
Tak więc mimo iż daną wejściową jest jedna figura w efekcie takiej przeróbki powstają dwie!!!
Oczywiście jest to najprostszy przypadek figury wejściowe mogą być dowolnie złożone i bardziej połamane od tej klepsydry (bo to jest jedynie przykład).
Trzeci obrazek to to dwa poprzednie nałożone na siebie. Powiedzmy, że mając taką klepsydrę na kartce papieru z każdej ze stron obcina się tą czarną obwódkę to pozostaną właśnie te niebieskie trójkąty.
Ostatni przedstawia Twój sposób na rozwiązanie problemu czyli skalowanie co jest zupełnie inną transformacją i nie ma sensu tego przypadku wcale rozpatrywać, bo dla bardziej złożonych figur jest jeszcze gorzej ze skalowaniem.

Jeszcze jedno wejściowa figura nigdy nie wygląda tak jak Twoja. Ona nigdy nie przecina sama siebie. Jest dowolnie złożona ale krawędzie nigdy się nie przecinają - innymi słowy można ją wyciąć z kartki papieru w jednym kawałku.

ale Ty zrobiłeś na tym obrazku całkiem co innego - po prostu 'odkroiłeś' to co na trzecim obrazku jest czarne i zostało Ci tylko to co jest niebieskie. Aby to zrobić to pierwotna figura musiała by się składać z dwóch - zaznaczony na czerwono i zielono obrys

i wtedy nie ma problemu - każdą zmniejszasz wg uznania

Jedno z rozwiązań jakie widzę to przeliczyć nowe współrzędne punktów (po odjęciu/dodaniu ileś tam), potem pogrupować je w odcinki (jakaś kolejność przy kreśleniu figury musi być zachowana przecież) a następnie sprawdzić dla każdej pary czy się nie przecinają i jak tak to oba odcinki odpowiednio skrócić (trzeba też obliczyć z którego końca ma być skracany). Inne rozwiązanie to najpierw obliczyć równania prostej dla każdego odcinka (boku) (kolor czerwony), potem odpowiednio je poprzesuwać (kolor żółty) i zaczynając od pierwszej prostej szukać takiej, która się z nią przecina i tak dalej aż do zamknięcia figury. Tutaj dla odmiany musisz sprawdzać czy dany punkt przecięcia możesz brać pod uwagę (znaczy czy punkt przecięcia należy do przetransformowanego odcinka na obu prostych) - zielone OK, fioletowe - be

Dzięki wielkie za zaangażowanie.
Nie wiem dlaczego tak się upierasz, że trzeba te figury dzielić na trójkąty, przecież ewentualnie coś takiego może robić funkcja zwężająca (od każdej z krawędzi ta sama odległość.
Twój sposób nie zadziała na złożonych wielokątach np.:

W końcu udało mi się to za pomocą funkcji i przynależności punktu do wielokąta nieforemnego wypukłego wyznaczyć. Jak na razie dużo liczenia i programowania, ale widzę, że to jest właśnie sekret twórców Photoshop'a na zmianę rozmiaru zaznaczenia (skubańce;) ).
Jeszcze raz serdeczne dzięki za pomoc.

to głupie pytanie - co Ci wyjdzie jak pomniejszysz np. samego konia o powiedzmy 25%? :) bo jestem bardzo ciekawy

To dość proste pytanie wyjdzie... źrebak tzn. mniejszy koń :)

Po lewej skalowanie, po prawej zwężanie. Twórcy programów graficznych się tym zajmowali wiec wiedzą, że to jest różnica.
Mnie chodzi o zawężenie, jakby odchudzenie konia ;) , czyli o to co już wałkujemy kilka dobrych godzin.

i chcesz znaleźć algorytm który Ci (a właściwie temu koniowi) tak okroi np. ogon :p. A nie prościej zrobić to (za przeproszeniem) od d**y strony - zapisać obrazek w jednym kolorze, znaleźć krawędzie (jest od metra algorytmów), wygumować gumką o odpowiedniej średnicy krawędź a potem tak powstałą maskę nałożyć na oryginalny rysunek i po problemie. Potem tylko ponownie znaleźć krawędzie i zapisać jako zbiór punktów.

Algorytm wektoryzacji bitmapy napisałem sam, bo żaden inny mi nie pasował.
Mi nie chodzi o zawężanie konia, smoka, klepsydry czy jeszcze czegoś innego to ma być generowane dynamicznie, a nie że ja to sobie w paincie będę robił.
Tym bardziej, że koń ma wymiary powiedzmy 1000px szerokości i ja chcę go zawężać co 1px, to jakbym miał gumką w paincie robić to bym zwątpił w możliwości programistyczne ;). Z resztą ja chcę tysiące takich grafik obrabiać, a właściwie, żeby to program sam robił.
Chcę tak zawężać te grafiki, aż do braku jakichkolwiek figur - niemożności zwężenia co jedną wartość (powiedzmy px).

ale ja nie mówię nic o paincie tylko o takim algorytmie w programie - jak napisałem algorytm znajdowania krawędzi jest na necie - jak będziesz miał krawędź to co za problem wygumować (czy inaczej narysować np. białym kolorem) coś po krawędzi a potem nałożyć obrobioną maskę na oryginał i go przyciąć. To wszystko w programie a nie w paincie - no bądźmy poważni :p

BTW tego ostatniego zdania nie rozumiem - to zostaw z każdego obrazka po trzy kropki 1px i już

No fakt jest to jakiś sposób, ale to jest znaczna utrata jakości, więc jak na razie pozostanę na matematycznym rozwiązaniu problemu.
Jak się znowu pogubię to rozważę Twój pomysł. W sumie sprytne, ale to taka "rzeźnia" trochę ;)
Ostatnie zdanie było stwierdzeniem o nic w nim nie wnioskowałem :)

Może czegoś nie doczytałem, ale nie chodzi Ci po prostu o operację erozji lub coś na kształt tego?
Obrazki z tymi trójkątami bardzo przypominają mi właśnie ten operator...

http://en.wikipedia.org/wiki/Erosion_(morphology)
http://homepages.inf.ed.ac.uk/rbf/HIPR2/erode.htm

Dokładnie, nie sądziłem, że taka operacja ma jakąś nazwę. Przestudiuję te materiały.
Dzięki.