[S]Kreis der n% aller Punkte enthält
-
Hallo!
Gegeben: Eine Liste aus diesen Elementen: ele { Position(x,y), Datum }; die Liste stellt dar, an welchem Tag wo ein Tier gefunden worden ist. Man nehme an, dass das Tier zwischen diesen Funddaten gleichförmig und geradlinig zum nächsten Punkt wandert.
Ich suche jetzt einen algorithmus, der mir einen Kreis bestimmt (also mittelpunkt und Radius) der das Gebiet enthält, wodrin sich das Tier n% der Zeit aufgehalten hat.
Als Anfang wäre schon ein Algo gut, der mir einen Kreis bestimmt, in dem sich n% Prozent der Fund-Position befinden.es ist wohl klar, dass ich nicht einen Kreis suche, sondern den kleinstmöglichen :), oder wenn das nciht geht, einen möglichst kleien Kreis der dem Kleinstmöglichen möglichst nahe kommt.
es muss auch nicht unbedingt ein Kreis sein, könnte auch ein Rechteck, eine Ellipse oder sowas sein, aber ich glaube ein Kreis ist dabei am einfachsten, weil er ja rotationsinvariant ist.Habt ihr tipps wie so ein algo heißt oder wie man das machen könnte? Ich steh da nämlich total aufm Schlauch, sowas hatten wir in der schule nich
Mir fiele nur die bruteforce lösung ein, aber die is nicht das geowllte Gruß, Maxi
-
Du könntest dir beispielsweise ein paar Techniken aus der Regressionsberechnung "ausleihen". ich denke dabei beispielsweise an den Algorithmus der kleinsten Quadrate und ähnliche Techniken. Diese lassen sich ja auf vielfältige Funktionen anwenden. Auch stellen derartige Aufgaben oft Problemstellungen für einfache genetische Algorithmen bzw. neuronale Netzwerke dar.
Eine erste Anlaufstelle wäre aber sicherlich mathworld.wolfram.com.
-
hm... also bei mathworld.wolfram.com seh ich nich so durch wonach ich da suchen soll
Ich hba auch keine Stichworte irgendwie.
das mit den kleinsten Quadaraten o.ä. Also, is vielleicht ne Idee. aber was müsste man da minimieren? Oder was erstmal überhaupt ausrechnen?
Ist das Zentrum der Punkte auch das Zentrum des Kreises? ich glaube nich. Außer es geht darum 100% der Punkte unterzubringen, aber das is ja nich, sind ja zB nur 95%
Isn kompliziertes Problem, was ich mit meinen bescheidenen mathekenntnissen ncih so leicht lösen kann. Besonders problematisch sehe ich eben diese n% an, wie ich die in form von gleichungen ausdrücken kann
-
Suchstichpunkte wären beispielsweise:
- Least Squares Fitting ( hieraus kann man recht einfach eine Formel ableiten, weil du ja nur den Abstand zum Kreis minimieren musst )
- Conformal Mapping
- Karimäki Methode
Siehe auch http://www.math.uab.edu/cl/cl2/cl2/node4.html.