Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

[C++] Tworzenie grafu na podstawie mapy o rozszerzeniu .map

Ostatnio zmodyfikowano 2016-04-20 13:36
Autor Wiadomość
Barol
Temat założony przez niniejszego użytkownika
[C++] Tworzenie grafu na podstawie mapy o rozszerzeniu .map
» 2016-04-18 13:33:20
Witam wszystkich

Mam zadanie napisania programu, który na podstawie mapy 2D otoczenia(np. pomieszczenia biurowego) stworzonej w programie Mapper3 Basic, utworzy graf zbudowany z wierzochołków i krawędzi obiektów zawartych na tej mapie.Zamieszczam zdjęcie obrazujące zadanie.
Mapa otoczenia
Mapa otoczenia

Dane tej mapy zapisują się w pliku o rozszrzeniu .map i wyglądaja następująco:



[...]


LINES
-32230 -41719 18041 -41719
-32230 7930 -32230 -41719
-32230 7930 18041 7930
-31994 6306 -31994 6306
-27979 -14445 -17633 -14445
-22806 -9271 -27979 -14445
-22806 -9271 -17633 -14445
-20776 -29036 -20776 -20725
-20776 -29036 -12280 -29036
-20776 -20725 -12280 -20725
-14133 -3826 -7571 2731
-14133 -3826 -1013 -3826
-12280 -20725 -12280 -29036
-10829 -38833 -10829 -38833
-7571 2731 -1013 -3826
-7479 -38270 6835 -38270
-2584 -22110 9235 -22110
-2584 -14353 -2584 -22110
-2584 -14353 9235 -14353
-322 -31113 -7479 -38270
-322 -31113 6835 -38270
9235 -14353 9235 -22110
18041 7930 18041 -41719
DATA

Czyli każda linia na mapie zapisywana jest jako para współrzędnych(początek i koniec linii).


Zaczynam naukę C++ i potrzebuję porad organizacyjnych/metodycznych bardziej doświadczonych programistów, tzn. jak wgl podejść do tego zadania.

Moja wersja na chwilę obecną:
1. Zmieniam rozszerzenie pliku mapa.map na mapa.txt. Odczytuje współrzędne każdej linii(dane pomiędzy LINES a DATA), zapisauje je w tablicy intów. Ten fragment mam napisany.
2. Tworzę klasę graf(lista wierzchołków, krawędzi i sąsiedztwa). I tutaj pojawia się pierwszy problem. Jak automatycznie utowrzyć macierz/listę sąsiedztwa pomiędzy wierzchołkami, które nie są połączne krawędziami ? Np. pkt. START z najbliższym wierzchołkiem ? Chcę żeby program był uniwersalny dla każdej mapy jaką mu wprowadzę(z pewnymi założeniami pocz. co do tworzenia samej mapy).

Na razie proszę tylko o pomoc logiczną. Jak powinienem podejść do tematu i z jakich narzędzi powinienem korzystać- klasy, struktury, tablice dynamiczne(wektory pewnie) (uczę się z kursu C++ zawartego na tym forum).

Pozdrawiam i przepraszam za długa treść


   

 

P-147384
darko202
» 2016-04-19 14:49:27
Wydaje mi się, że nie rozumiem Twojego problemu :)

1.
>> Mam zadanie napisania programu. utworzy graf zbudowany z wierzchołków i krawędzi obiektów zawartych na tej mapie.
...
>> Tworzę klasę graf(lista wierzchołków, krawędzi i sąsiedztwa).

tak od razu ?
jedna klasa realizuje całe zadanie :(( 

Oczywiście można próbować :)
ale dużo prościej jest rozłożyć tak złożone zadanie na kilka podzadań

to już niestety Twoja rola

http://forum.pcformat.pl​/Grafy-w-C-t
http://www.algorytm.org​/klasyczne​/grafy-i-ich-reprezentacje.html

2.
w pliku mapy masz w każdej linii informację na temat powiązań miedzy punktami  

stąd masz :
* listę punktów
* listę krawędzi
czyli wszystko co jest potrzebne

3.
jak chcesz rysować ten gra ?
może np.
http://cpp0x.pl/artykuly/?id=52 
http://forum.komputerswiat.pl​/topic​/156347-c-jak-narysowa%C4%87-w​ykres-funkcji​/
 a może zupełnie inaczej

P-147428
Barol
Temat założony przez niniejszego użytkownika
» 2016-04-19 16:14:28
Dziękuję za odpowiedź.

Zdjęcie pomocnicze do zobrazowania moich wątpliwości:
Dodałem oznaczenia wierzchołków A,B,C,D

Graf widocznosci
Graf widocznosci
 
Mój program powienien automatycznie po analizie takiej mapy utworzyć graf widoczności-pojęcie z robotyki mobilnej(to na początek, później jak to się uda pomyślę o diagramie Voronoia).

Tzn. wypełnia te tablice/vektory(dynamicznie w zal odliczby elementów na mapie) o wierzchołki, krawędzie, sąsiedztwa i o wagi(wagi będą wyliczane na podstawie różnicy we współrzednych pomiędzy sąsiednimi wierzchołkami grafu).

Tak jak mówisz, w pliku .map mam linie np. B i C powiążę bo są na tej samej linii tylko jak powiącać w grafie pkt. A i B, A i C itd. ?

Druga kwestia to ścieżki grafu nie mogą przechodzić przez grawędzie obiektów np. B i D. Też muszę  to wykryć i wykluczyć.

Generalnie graf nie musi być narysowany. Sens jego istnienia polega na przeszukaniu go algorytmami np. wszerz albo w głąb i wygenerowaniu mi tej ścieżki(na podstawię tej ścieżki wygeneruję sterowanie dla robota mobilnego Pioneer3DX, który przejedzie ta ścieżka w środowisku laboratoryjnym). Jeżeli wystarczy mi checi i opanuję techniki rysowania to może i zrobie jakis interfejs graficzny ale moje zadanie tego nie wymaga.

Mam nadzieję, że rozjaśniłem trochę.

Pozdrawiam



P-147435
darko202
» 2016-04-20 13:36:09
4.
strasznie dużo niewiadomych :
* start z jakiej mapy - analiza obrazu, czy pliku *.map
* graf widoczności  - podaj definicję tego cudu
np.  http://workshop.tcs.uj.edu.pl​/mszana2015/gutkraw/main.pdf
według tego prawdopodobnie mówimy o żółtych liniach widocznych na rysunku (nie napisałeś tego)


5.
zastanów się nad poniższym zadaniem
C/C++
zadanie: "napisz program zjedzenia jajka na miękko"

Twoj algorytm: "zjadam jajko"


A.
przeczytaj je ze zrozumieniem 

B.
powiedz mi jak mam sprawdzić przy pomocy tego algorytmu "czy to czy na pewno jest to jajko na miękko"

C.
Może ktoś "mądrzejszy" (kadzenie) ma jakiś pomysł jak przy pomocy mojego algorytmu rozwiązać problem "miękkiego jajka"  zapytam na forum !

D.
odpowiedz Sobie :
- "czy przeczytałeś ze zrozumieniem ?"
- zauważyłem pewne podobieństwa ?

E.
nie obrażaj się - to miał być elektrowstrząs :)



6.
Ciągle masz ten sam problem nie definiujesz poprawnie realizowanego algorytmu
najpierw bez używania słów Tablica, program, itp. opisz słownie co masz zrobić.

np.
- biorę mapę np. grafika
- biorę punkt (lewy dolny róg) i patrzę które punkty są widoczne
- co oznacza "patrzę"  (prowadzę żółte linie), nie przecinają figur na rysunku 
- co oznacza "prowadzę linię",
- co oznacza "nie przecinają"
.... 
 
jestem przekonany, że ten opis bardzo Ci to ułatwi znalezienie algorytmu, a jak go opublikujesz, zamiast tego co do tej pory - to wiele osób wesprze Cię w problemie, który przedstawiłeś

Powodzenia !
 


 7.
matematycznie : 4 punkty - 2 proste - punkt przecięcia

http://www.math.edu.pl​/punkt-przeciecia-dwoch-prostych
http://matematyka.pisz.pl​/strona/1223.html

punkt przecięcia leży na odcinku ? -> "patrzę" na jego współrzędne w stosunku do ...

P-147461
« 1 »
  Strona 1 z 1