Okrąg obejmujący n punktów

Odpowiedz Nowy wątek
2015-01-21 00:18
0

Witam.
Mam pewien problem z napisaniem projektu na uczelnie. Należy wygenerować n punktów. poźniej znaleźć dwa okręgi zawierające w sobie wszystkie punkty( przynajmniej 3 punkty mają być na okręgu). Sprawdzić który okrąg ma mniejszą powierzchnie. Problem pojawia się w znalezieniu trzech takich punktów aby okrąg na nich opisany obejmował resztę. Jeśli ktoś ma jakiś pomysł to byłbym wdzięczny.
No chybam że jest jeszcze jedna możliwość, i nie zrozumiałem polecenia, które jest po angielsku ;) Oto ono: "Generate by random a set of n points in 2D Cartesian Coordinates System. Find two different circles enveloping all of the points and connected to the set (there are at least three points on the circle). Check which circle has a smaller area."
Ja próbowałem to rozwiązać w taki sposób, że wybieram 4 punkty o ( najniższa / najwyższa watość X i najniższa / najwyższa wartość Y ) i na tej podstawie dobieranie 3 punktów do okręgów no ale niestety to nie działa (co było do przewidzenia w sumie :( ). DZiękuje za pomoc ;)

Pozostało 580 znaków

2015-01-21 00:33
0

To jest bez sensu bo można spokojnie wygenerować N punktów z których żadne 3 nie będą znajdować się na tym samym okręgu, ot wystarczyłoby żeby generować wszystkie punkty na tej samej prostej.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2015-01-21 00:42
0

Nie jestem pewien czy to zadanie jest do końca dobrze sprecyzowane.

a) dwa koła, które w sumie obejmują wszystkie punkty?
czy może
b) dwa różne koła, każde z nich obejmuje wszystkie punkty

W przypadku a):
Ja bym problem uprościł: Wybierz 4 punkty z danego setu punktów w takie sposób, żeby stworzyły czworokąt, który zawiera wszystkie punkty. Czworokąt podziel na dwa trójkąty. Znając punkty obu trójkątów:
http://www.algorytm.org/geome[...]y-przez-dane-trzy-punkty.html

Wydaje mi się, że nie zawsze da się to zrobić tak, żeby każde z kół zawierało 3 punkty z setu: np. dziewięciokąt wypukły nie foremny.

W dowolnym przypadku wydaje mi się, że rozwiązanie będzie wymagało znalezienia otoczki wypukłej, po czym brut forcem znalezieniu koła (podejrzewam, że dało by rade go troche zoptymalizować, żeby w normalnym czasie liczył). Na czuja wydaje mi się, że powinieneś brać dwa kolejne punkty z otoczki i szukać najbardziej oddalonego od tej pary (odcinka) punktu. (N log N, N - liczba punktow na otoczce)


░█░█░█░█░█░█░█░█░█░█░█░
"Wybierz 4 punkty z danego setu punktów w takie sposób, żeby stworzyły czworokąt, który zawiera wszystkie punkty" - taki czworokąt ma dużą szansę nie istnieć. (ale chodzi o interpretację b jednak) - msm 2015-01-23 10:41

Pozostało 580 znaków

2015-01-21 00:43
0
  1. Obliczasz otoczkę wypukłą https://pl.wikipedia.org/wiki/Otoczka_wypuk%C5%82a.
  2. Wybierasz 3 punkty, które są od siebie oddalone najbardziej (budują największy trójkąt).
  3. Opisujesz trójkąt na tym punkcie.

Chyba to będzie algorytm optymalny.

Wydaje mi się, że dwa punkty z otoczki obok siebie + najbardziej oddalony od nich stworzą największe koło - krwq 2015-01-21 00:50

Pozostało 580 znaków

2015-01-22 22:13
0

Dziękuję za pomoc. Niestety chwilowo muszę porzucić projekt ze względu na inne obowiązki. Odezwę się wrazie problemów (albo jeśli mi się uda wszystko ogarnąć ;) )

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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