Wyszukiwanie początku i końca odcinków.

Odpowiedz Nowy wątek
2012-07-23 10:45

Rejestracja: 7 lat temu

Ostatnio: 2 miesiące temu

0

Hej!

Sprawa wygląda tak, że w bazie mam tabelę:

#ID - #START_X - #START_Y - #END_X - #END_Y

  1. 0.0 - 0.0 - 3.0 - 3.0
  2. 3.0 - 3.0 - 8.0 - 4.0
  3. 11.0 - 12.0 - 8.0 - 4.0

StartX/Y i EndX/Y to punktu układu współrzędnych, które wprowadza użytkownik.
Są to punkty (wierzchołki) krzywej. Użytkownik po prostu wprowadza współrzędne punktów. Dodatkowo założyłem tutaj pewną okoliczność, że użytkownik myli Start z Endem (punkt 3).

Co chcę osiągnąć?
Chciałbym z takiej tablicy wybrać punkty, które leżą na jednej krzywej. Tzn - koniec pierwszego punktu jest początkiem drugiego i tak kolejno. Na koniec drukuję, że punkt początkowy to #1 o współrzędnych takich i takich, a końcowy to #3 o wsp. takich i takich.

I jeszcze chciałbym dać jedną opcję dla użytkownika, mianowicie rozchodzenie się prostej w punkcie. Tzn. - dwa (lub więcej) punkty(ów) mają ten sam punkt startowy/bądź końcowy.

Odnośnie samego języka C#, czy też LINQ (które chciałbym tutaj użyć) nie mam problemu.

Problemem jest to, że nie bardzo mam pomysł jak podejść do tego problemu, z której strony go ugryźć, aby to było sprytne i poprawne :) Może ktoś z szanownych użytkowników mógłby tchnąć we mnie jakieś natchnienie/pomysł do rozwiązania tego problemu.

Z góry dziękuję serdecznie :)

Jeśli nie język jest problemem, lecz algorytm, to może lepiej byłoby to pytanie zadać w dziale "Algorytmy"? Tam jest większe prawdopodobieństwo uzyskania dobrej podpowiedzi. W razie czego mogę przenieść. - somekind 2012-07-23 11:22

Pozostało 580 znaków

PS
2012-07-23 10:49
PS
1
GrzesiekP napisał(a):

Tzn - koniec pierwszego punktu jest początkiem drugiego i tak kolejno. Na koniec drukuję, że punkt początkowy to #1 o współrzędnych takich i takich, a końcowy to #3 o wsp. takich i takich.

I jeszcze chciałbym dać jedną opcję dla użytkownika, mianowicie rozchodzenie się prostej w punkcie. Tzn. - dwa (lub więcej) punkty(ów) mają ten sam punkt startowy/bądź końcowy.

http://pl.wikipedia.org/wiki/Punkt_(geometria)

Pozostało 580 znaków

2012-07-23 10:52

Rejestracja: 12 lat temu

Ostatnio: 4 minuty temu

1

Przerób to na graf i szukaj cykli. Wierzchołki to będą końce odcinków, a krawędziami będą same odcinki (krawędzie mogą być dwukierunkowe, wtedy użytkownik może pomylić początek z końcem).

Pozostało 580 znaków

2012-07-23 10:56

Rejestracja: 7 lat temu

Ostatnio: 2 miesiące temu

0

@PS
No oczywiście pomyłka moja - chodzi mi, że punkt #1 jest początkiem pierwszego odcinka krzywej, #2 końcem. #3 to kontynuacja krzywej.

Spróbuję sobie to rozrysować. Kiedyś w końcu wypada się trochę podszkolić z algorytmów i grafów :)

Pozostało 580 znaków

2012-07-23 14:19

Rejestracja: 7 lat temu

Ostatnio: 2 miesiące temu

0

Zastanawiam się teraz, czy aby graf będzie dobrym rozwiązaniem.

W sumie mam coś takiego:
http://pl.wikipedia.org/w/ind[...];filetimestamp=20070519100203

Takich zbiorów będę mieć mnóstwo - tzn. mnóstwo punktów, które tworzą odcinki/krzywe (połączone ze sobą lub nie) i będę mieć kilka zdefiniowanych punktów startowych.
Inaczej mówiąc - pojedynczy zbiór to będzie zbiór punktów o danych współrzędnych i o zdefiniowanym punkcie początkowym.
Teraz dla takiego zbioru potrzebuję wyznaczyć ścieżki: 1-2-3, 1-2-4-5, 1-2-4-6-7, a więc od początkowego punktu do każdego ostatniego/skrajnego.

Bardziej mi to podchodzi pod drzewo, ale nie jestem pewien teraz, w którą stronę iść.

Pozostało 580 znaków

2012-07-23 14:48

Rejestracja: 12 lat temu

Ostatnio: 4 minuty temu

0

Link nie działa (prowadzi mnie do strony, która została usunięta, jeżeli to jest to, to proszę o wytłumaczenie, czego mam tam szukać).
Drzewo jest grafem.

Odpowiedz

1 użytkowników online, w tym zalogowanych: 0, gości: 0, botów: 1

Robot: Bingbot