Załóżmy, że mamy obiekty umieszczone na płaszczyźnie. Każdy obiekt charakteryzuje się współrzędnymi (X, Y), identyfikatorem (ID) oraz dwoma polami łączącymi (L1 i L2 będącymi ID innych obiektów).
Teraz zadanie:
Jak wyrysować linie łączące dane obiekty, ale tak, by linie te nie przechodziły przez inne obiekty oraz żeby możliwie najmniej z nich się krzyżowało? Możemy dodatkowo założyć, że linie prowadzone są jedynie w kierunku pionowym i poziomym (tzn. mogą być to łamane).
Jakieś pomysły na algorytm?
Zakładamy, że rysowanie prostej z jednego punktu do drugiego jest instrukcją elementarną.
0
0
<font color="darkblue">Coś podobnego było na dróżynowych zawodach w programowaniu w www.pwr.wroc.pl >> ale nasz team tego zadania niestety nie rozwiązał [glowa] </span>
0
w takim razie same polaczenia musza(powinny) byc takze obiektami aby mozna bylo sprawdzic jak sa wyrysowane :-)
0
Z powyższego opisu wynika, że obiekty wraz z połączeniami stanowią graf. Graf ten nazywamy planarnym jeśli to co opisałeś jest możliwe (połączenie wierzchołków tak aby łączące je linie się nie krzyżowały) trochę informacji na ten temat można znaleźć pod: mathworld.wolfram.com/PlanarGraph.html
0
Z powyższego opisu wynika, że obiekty wraz z połączeniami stanowią graf. Graf ten nazywamy planarnym jeśli to co opisałeś jest możliwe (połączenie wierzchołków tak aby łączące je linie się nie krzyżowały)
Tyle to ja wiem. Z tym, że ja dopuszczam możliwość krzyżowania się (jeżeli już innego wyjścia nie ma). I chodzi o to wyrysowanie lini (najlepiej jedynie prostopadłe i równoległe).
Chodzi po prostu o algorytm rysowania schematów blokowych na podstawie danych jedynie obiektów. Dzięki temu możnaby do serwisu wprowadzić grafikę SVG i prezentowanie algorytmów zyskałoby na bardzo przejrzystych metodach przedstawiania algorytmów.
0
Ja bym proponowal skonstruowanie czegos na ksztalt autoroutera. Zalozyc ze mamy kilka iteracji tworzenia polaczen. Kazde polaczenie powinno miec attrybut okreslajacy ile razy krzyzuje sie ono z innymi polaczeniami. Teraz wykorzystujac miare drogi typu taksowkarzy Nowego Yourku obliczamy dlugosc zaproponowanej drogi. W ten sposob kazde polaczenie jest charakteryzowane poprzez dwie wartosci czyli swoja dlugosc oraz liczbe okreslajaca ilosc skrzyzowan z innymi polaczeniami. Dalej rworzymy funcje celu opisujaca sumaryczna dlugosc wszystkich polaczen oraz zawierajaca tzw. funkcje kary, ktora powoduje ze polaczenie o duzej liczbie skrzyzowan wnosi wiekszy wklad w vartosc calej funcji. Dalej to juz tylko minimalizacja funcji celu... :) (tyle ze to jest osobne i mocno powazne zagadnienie choc mozna znalezc kilka algorytmow do tego w literaturze) Mozliwe jest tu wykorzystanie metody Najwiekszego spadku, lub metody kwadratowej itd itp. Po obliczeniu wartosci funkcji celu mozliwe jest okreslenie o ile i jakie parametry polaczen nalezy zmodyfikowac stad mamy iteracyjen podejscie. Pozostaje jedynie znalezienie kryterium konca iteracji co czasami nie jest wcale takie banalne. Przez parametry polaczenia rozumiem np. ilosc segmentow, ich kolejnosc itp. (wszystkie ktore maja wplyw na dlugosc i ksztalt polaczenia)