Schnittfläche mehrerer Kreise berechnen |
| 17.12.2011, 01:18 | redy. | Auf diesen Beitrag antworten » | ||||
| Schnittfläche mehrerer Kreise berechnen Hallo zusammen, ich habe ein Problem bei dem ich nicht weiter komme und hoffe ihr könnt mir auf die Sprünge helfen. (Muss gestehen meine Geometriekenntnisse sind schon etwas angestaubt) Ich habe verschiedene Punkte auf einer Landkarte. (Longitude und Latitude) Diese Punkte haben Signalstärken. Ich versuche nun die Signalstärke in einen Kreis umzurechnen. Wenn ich jeden Kreis berechnet habe, würde ich gerne die Schnittstelle der Kreise ermitteln und daraus den Mittelpunkt errechnen. Meine Ideen: 1.) Um den Radius bei hoher Signalstärke kleiner werden zu lassen (maximale Signalstärke ist 100): Radius = 150 - Signalstärke 2.) Den Umfang des Kreises berechnen: Umfang = 2 x (PI) x Radius jetzt hat man mehrere Kreise die sich unter Berücksichtigung ihrer Koordinaten überschneiden. Koordinaten sind (Latitude) und (Longitude) Wie kann ich jetzt die Schnittfläche der Kreise errechnen? Und wie kann ich den Mittelpunkt dieser Schnittfläche ermitteln? Vielen Dank gruß redy. |
||||||
| 19.12.2011, 03:56 | chris_78 | Auf diesen Beitrag antworten » | ||||
Hallo, eine interessante Problemstellung. Ich weiß nicht, ob ich Dir da helfen kann, aber mal meine Ideen dazu. Zuerst einmal: Warum soll der Kreisradius bei hoher Signalstärke kleiner werden? Steht der Kreis nicht für die Reichweite des Signals und müßte bei einem starken Signal größer werden? Wenn man das ganze nicht mit Zirkel auf der Landkarte lösen will, müßte man die Punkte wohl in ein Koordinatensystem übertragen. Liegen die Punkte nicht übermäßig weit auseinander, kann man, denke ich, die Erdkrümmung ignorieren. Die Kreisgleichung ist mit dem Mittelpunkt Hat man nun 2 Kreise so kann man die Schnittpunkte der beiden Kreise bestimmen (sofern die existieren). Die beiden Kreise schließen eine Fläche ein, deren Größe man berechnen könnte (ist das überhaupt nötig?). Mit Mittelpunkt der Fläche ist vermutlich der Schwerpunkt gemeint. Den zu berechnen ist nicht ganz so leicht glaube ich. Da weiß ich auf Anhieb auch nicht weiter. Was ist den der Zweck des Ganzen? Vielleicht gibt es ja noch andere Lsungsmöglichkeiten für das Problem. |
||||||
| 19.12.2011, 20:33 | redy. | Auf diesen Beitrag antworten » | ||||
Hi chris, vorab danke für die Antwort. Ich versuch das Problem noch mal genauer zu beschreiben. Wir haben einen Sender auf einer Karte. Diesen wollen wir möglichst genau orten. Wir messen den Sender von verschiedenen Punkten und möchten die location des Senders möglichst genau bestimmen. Wir haben die GPS-Punkte von den verschiedenen Messpunkten und jeweils eine Signalstärke. (Daher die Umkehrung mit der Signalstärke. Desto näher man dran ist, desto genauer ist der radius.) Wir wollten eine Formel entwickeln, bei der man mit hilfe der signalstärken überschneidungen der Messpunkte errechnen kann. In der Fläche der Überschneidungen soll dann der Mittelpunkt errechnet werden. Im endeffekt soll eine Gpskoordinate rauskommen bei der die Wahrscheinlichkeit maximal ist, dass sich dort unser Sender befindet. gruß redy. |
||||||
| 20.12.2011, 13:20 | chris_78 | Auf diesen Beitrag antworten » | ||||
Ich denke mal ein wenig vor mich hin. Vielleicht steigt ja auch noch jemand hier ein? Angenommen man könnte aufgrund der Signalstärke genau auf die Entfernung des Messpunktes zum Sender schließen. Der Abstand zwischen Messpunkt und Sender wäre somit dann der Radius r und der Sender muß sich auf dem Kreis mit dem Radius r um den Messpunkt befinden. Habe ich nun 2 Messpunkte so schneiden sich die beiden Kreise in 2 Punkten (oder auch im Ausnahmefall nur einem Berührpunkt). Dies wären beides mögliche Standpunkte des Senders. Spätestens mit einem 3. Messpunkt könnte ich dann eindeutig bestimmen wo der Sender sich befindet, weil der Kreis um diesen Messpunkt ebenfalls durch den Standort des Senders geht. Dass sich 2 Kreise nicht schneiden kann nur vorkommen, wenn die Radien nicht stimmen. Sollte dies passieren, so wurde einer der Radien (also der Abstand vom Messpunkt zum Sender) zu klein angenommen. Soweit die Theorie. In der Praxis dürfte wohl es wohl schwerfallen die Radien so exakt zu berechnen aus der Signalstärke? Wie genau ist das denn? Wenn Du von maximaler Signalstärke 100 sprichst, bist Du dann nicht direkt am Sender? Ich hab mal eine Grafik angehängt, wie das ausschauen kann, bei 3 Messpunkten (A, B, C). Wie man sieht, gibt es eben mehrere Schnittpunkte und Schnittflächen. Irgendwo bei den Schnittpunkten H, F, D wäre da der Sender, aber E, I und ein weitere Punkt der nicht auf der Grafik zu sehen ist sind auch Schnittpunkte zweier Kreise. Diese muß man aber rausfallen lassen und sich nur auf H, F, D konzentrieren. Hier würde ich dann einfach den Mittelwert aus x und y-Koordinate bilden, um den Senderstandort zu ermitteln. Das wird sich aber kaum in eine einfache Formel packen lassen. |
||||||
| 20.12.2011, 19:03 | redy. | Auf diesen Beitrag antworten » | ||||
Hey chris, genau so ist es. Wenn man 100% hat ist man am Sender. Das ding ist dass man die empfangsstärke aka radius wahrscheinlich nicht so genau bekommt, dass der Sender auf dem Kreis liegt. Daher dachte ich an einen dritten und letzten schritt. Man macht den Radius um ein paar Prozent größer und bekommt dadurch eine etwas größere Schnittfläche der Kreise. Das bringt uns schon mal weiter da wir damit den möglichen Standort schon sehr einschränken können. Wenn man dann als letzten Schritt den Mittelpunkt dieser Schnittfläche berechnet, ist die chance recht groß, dass man den Sender auf ein paar Meter orten kann. Das ganze wird genauer desto mehr messungen man macht. könnte man daraus vielleicht verschiedene Berechnungsschritte machen? 1. Radius = 150 - Signalstärke 2. Schnittfläche = Kreis1, Kres2, Kreis3, etc 3. Mittelpunkt = Errechnung des Mittelpunkts der Schnittfläche gruß redy. |
||||||
| 21.12.2011, 01:35 | chili_12 | Auf diesen Beitrag antworten » | ||||
Hi, ist die Signalstärke nicht umgekehrt proportional zum Abstand? Falls ja könnte man mithilfe von zwei Messungen den genauen Standpunkt bestimmen. Die Kreise scheinen mir kein besonders guter Ansatz. Da die Messungen an sehr unterschiedlichen Orten stattfinden müssten um die Schnittfläche möglichst gering zu halten was doch recht unpraktikabel ist. Selbst wenn der Proportionalitätsfaktor a priori nicht bekannt ist. Könnte man mit drei Messungen den Standort bestimmen. 1. Reziproke Proportionalität: (Entfernung E Signalstärke S) 2. Ausserdem gilt ja : (P1(x1,y1) Zielkoordinaten | P2(x2,y2) Messkoordinaten) P2 und S sind bekannt also haben wir drei Unbekannte zu bestimmen. Dies sollte mit drei Messungen möglich sein. Wie gesagt wenn k bekannt ist sogar in 2 Messungen. mfg |
||||||
| Anzeige | ||||||
|
|
||||||
| 21.12.2011, 01:55 | chili_12 | Auf diesen Beitrag antworten » | ||||
Mir fällt gerade auf, dass mein Ansatz dem Kreisansatz doch sehr ähnelt. Nur dass ich davon ausgehe, das Ziel läge auf dem Kreisrand. Was das Problem doch stark vereinfacht. Wenn man nun mehrere Messungen durchführen will um die Ziekoordinaten genauer zu bestimmen. Könnte man doch 2 bzw. 3er Blöcke bilden und die jeweils ermittelten Koordinaten mitteln. Oder evtl. noch besser mit der Signalstärke gewichtet mitteln, da zu erwarten ist, dass der Fehler mit zunehmender Signalstärke abnimmt. |
||||||
| 21.12.2011, 03:55 | Iridium | Auf diesen Beitrag antworten » | ||||
| ... Entsprechen die gesuchten Schnittpunkte nicht den Ecken einer Voronoi-Zerlegung? Evtl. mit einer zusätzlichen Gewichtung, je nach Signalstärke. Kristallographen haben dazu Methoden entwickelt. Stichwort: Potenzebenenverfahren. Die daraus erhaltene Zerlegung ist raumfüllend, erfüllt aber auch die Gewichtungskriterien, die bei einfacherer Anwendung auf das Konzept der Voronoi-Zerlegung zu Lücken führen können. |
||||||
| 21.12.2011, 07:55 | redy. | Auf diesen Beitrag antworten » | ||||
Hi zusammen, vorab erst mal vielen vielen Dank für die Unterstützung in der Sache. Ich bin euch wirklich zu Dank verpflichtet. Super das es das Forum und euch Matheasse gibt!
im prinzip ja, jedoch gibt es schwankende Störfaktoren wie Gebäude oder Büme etc. Daher dachte ich an den Zwischenschritt mit dem etwas erweiterten radius und der am Ende stehenden Schnittflächenberechnung. Anbei mal ein Beispiel wie die Daten zu einem Messpunkt/Sender aussehen: 1 Messpunkt Lan: 50.15283 Lon: 8.803358 Sig: 80% 2 Messpunkt Lan: 50.152655 Lon: 8.802993 Sig: 82% 3 Messpunkt Lan: 50.152253 Lon: 8.803229 Sig: 54% So würden die Daten au0ssehen. Mit nur zwei Messpunkten halte ich es für nicht möglich, da ich die Richtung nicht kenne. Wenn man zwei Messpunkte auf einer Graden hat, könnte man nie bestimmen ob das Signal von rechts oder von links kommt. Es wäre allerdings super wenn ihr mich eines besseren belehren könntet 
Wenn ich die Voronoi zerlegung richtig verstehe, sieht das doch schon schwer nach der Richtung aus in der wir gedacht hatten chris? Man hat verschiedene Punkte und "Signalstärken". Je höher die Signalstärke und desto mehr messpunkte man hat, desto genauer wird das ganze. Das ganze geht auch sehr in richtung triangulation... Kann man denn mit der Voronoi zerlegung auch signalschwankungen kompensieren? Gruß redy. |
||||||
| 21.12.2011, 07:58 | redy. | Auf diesen Beitrag antworten » | ||||
(sorry, ich bin auf "abschicken" gekommen bevor ich die Rechtschreibschitzer beseitigen konnte) |
||||||
| 21.12.2011, 14:14 | chili_12 | Auf diesen Beitrag antworten » | ||||
Du hast natürlich recht. Die Quadratischen Gleichungen führen zu mehreren Lösungen: {a = 50.15350213, b = 8.802757687, k = 0.07209474245}, {a = 50.15261851, b = 8.803230927, k = 0.01973806504} P1(a,b) mfg |
||||||
| 21.12.2011, 21:43 | Iridium | Auf diesen Beitrag antworten » | ||||
Ja, Voronoi-Zerlegung (die Methode hat auch noch andere Namen, weil sie so oft und unabhängig voneinander wiederentdeckt wurde) ist ein klassischer Ansatz, wenn man irgendeine Punktmenge hat (in dem Fall die Positionen der Sender) und das Gebiet dazwischen systematisch aufteilen will. Üblicherweise bedeutet die Zerlegung nur, daß alle Gebiete zusammengefasst werden, die räumlich näher an Sender X liegen, als an allen anderen Sendern. Das Einzugsgebiet sozusagen. Oder der Wirkungsbereich. Je nach Zusammenhang. Die Grenzlinien zwischen Bereichen kennzeichnen dann Orte, die gleichweit von zwei Sendern liegen, die Eckpunkte dann Orte, die gleichweit zu drei Sendern liegen. In der Ebene wars das dann. Aber das Prinzip ist verallgemeinerbar, in Räume höherer Dimension z.B. oder eben durch Einführung von Gewichtungsfaktoren, in deinem Fall die unterschiedliche Signalstärke. Triangulation beschreibt dann übrigens das mathematisch definierte duale Muster. D.h. man tauscht Ecken mit Flächen und Flächen mit Ecken aus. Dann bekommt man die dazugehörige Delaunay (auch Delone) Triangulation. Signalschwankungen schließlich lassen sich berücksichtigen, wenn man das Ganze dynamisch berechnet. Wenn ein Signal schwächer wird, dann wird entsprechend das zugehörige Gebiet, d.h. der Flächeninhalt des Voronoi-Polygons, kleiner. Wenn die Signalstärke Null ist, dann hat man quasi den Fall, als ob es erst gar keinen Sender an diesem Ort gäbe und entsprechend verschwindet auch der zugehörige Wirkungsbereich. Will man von einem Eckpunkt der Voronoi-Zerlegung ein Maß für die Nähe eines Senders haben, dann kann man z.B. die Größe des ebenen bzw. Raumwinkels heranziehen, in der Kristallographie kann man auf diese Weise für verschiedene Atome in unterschiedlichem Abstand von einem Zentralatom ihren Einfluß auf dessen Koordination gewichten. Das einzige Problem, das ich noch sehe, ist, daß die Voronoi-Zerlegung nicht unbedingt angibt, ob es Bereiche gibt, die durch einen Sender nicht erreicht werden, aber das kann man sicher auch berücksichtigen, grob allein schon dadurch, daß man den Flächeninhalt des Sendekreises mit dem des Voronoi-Polygons vergleicht oder evtl. auch die Asymmetrie des Polygons berücksichtigt. Sind alle Sender gitterartig angeordnet, z.B. hexagonal, dann sollten beide Flächen beinahe gleichgroß und sehr symmetrisch angeordnet sein. Das sind so meine spontanen Gedanken. Das Thema wird aber in vielen Wissenschaften, von der Kristallographie über die Physik, Geographie usw. ausführlichst behandelt, so daß es denke ich ausreicht, nur die anschaulichen Ideen zu schildern. Und einige Stichworte sind ja auch gefallen, so daß man Details leicht finden sollte. Gruß |
||||||
| 22.12.2011, 06:33 | chris_78 | Auf diesen Beitrag antworten » | ||||
Es mag daran liegen, dass die Voronoi Zerlegung für mich etwas Neues ist und ich nicht damit vertraut bin, aber in der Problemstellung geht es doch darum, dass es nur einen Sender gibt und man dessen Standort ermitteln will, indem man von verschiedenen Messpunkten den Abstand(=Signalstärke) zum Sender bestimmt. Inwiefern da die Zerlegung helfen sollte sehe ich nicht. Und wenn ich meine obige Beispielgrafik anschaue, dann sind die Schnittpunkte auch keine Eckpunkte der Voronoi Zerlegung. Mein Ansatz wäre wäre weiterhin so (hab gefunden dass das Lateration heißt): 1. Um jeden Messpunkt einen Kreis legen (Radius abhängig von der Signalstärke) 2. Die Schnittpunkte bestimmen, die jeder Kreis mit den den anderen Kreisen hat (Kreis1 mit Kreis2, Kreis1 mit Kreis3, Kreis2 mit Kreis3 usw je nach Anzahl) 3. Jetzt hat man bestenfalls zu jedem Schnitt zweier Kreise 2 Schnittpunkte, wobei einer der beiden Schnittpunkte nah am Sender ist, der andere irgendwo anders. Durch Hinsehen könnte man nun die Schnittpunkte finden, die nah am Sender sind (weil sie halt alle nah beieinader liegen), die anderen lässt man rausfallen. Will man das z.b. in ein Programm packen könnte man über die Abstände der Schnittpunkte zueinander die "falschen" rausfallen lassen. 4. Die Schnittpunkte begrenzen nun die Fläche, in der der Sender vermutet wird. Ich würde nun jeweils die Mittelwerte der x und y Koordinaten bilden, um die Koordinaten des Senders zu ermitteln. (Schwerpunkt der Fläche erscheint mir weniger sinnvoll, weil z.B. Ausreisser die Fläche unnötig vergrößern könnten. Und es ist auch deutlich schwieriger zu berechnen). Das größte Problem dürfte nun sein, die Signalstärke in einen passenden Radius umzurechnen. Die r=150-Signalstärke scheinen mir da nicht passend. Wie weit reicht denn Dein Signal? Wie weit weg ist man bei z.B. 80%, wie weit bei 50%? Daraus könnte man dann einen Radius ableiten. |
||||||
| 22.12.2011, 21:51 | Iridium | Auf diesen Beitrag antworten » | ||||
Ja und nein. Man geht zwar von einem Sender aus, aber zusätzlich hat man Orte drumherum und kodierte Information über den Abstand zum Sender, nämlich durch die gemessene Signalstärke. Also müsste man meiner Meinung nach das Problem auch gedanklich umkehren können, indem man so tut, als ob die Orte selber Sender wären. Die unterschiedliche Signalstärke sorgt für die Gewichtung der Voronoi-Zerlegung, die dann nicht mehr mit der üblichen Methode der Mittelsenkrechten auf den Verbindungsstrecken zu tun hat, sondern den Ort der Senkrechten entsprechend der relativen Signalstärke zu dem einen oder anderen Punkt verschiebt. Damit verschiebt sich entsprechend auch der Schnittpunkt mehrerer Senkrechten, und damit wiederrum der Ort des ursprünglichen Senders. Jedenfalls wird man an der geometrischen Beziehung nichts ändern. Der Ansatz mit den Kreisradien ist im Grunde sehr ähnlich, in gewisser Weise auch physikalisch anschaulicher, weil die Signalausbreitung gleichmäßig erfolgt. Die Voronoi-Zerlegung ist in gewisser Weise auch nichts anderes als kleine Kreise um zuvor festgelegte Punkte, deren Radius stetig wächst und die irgendwann aneinander stoßen. Wenn sie das tun, bilden sich die Grenzflächen. Das Muster der Grenzflächen wird durch die konstante unterschiedliche Ausbreitungsgeschwindigkeit bestimmt, also die unterschiedlichen Signalstärken. Insofern, kennt man die Signalstärken und die Orte, müsste man das Problem nur umdrehen und entsprechend zurückrechnen. |
||||||
| 23.12.2011, 01:59 | chili_12 | Auf diesen Beitrag antworten » | ||||
Hi, es wäre praktisch wenn du uns reale Messwerte und Zielkoordinaten geben könntest um die Güte unserer Lösungsansätze zu testen. Ich vermute, dass man mit meinem Verfahren mit 5-6 Messungen einigermaßen gute Annährungen erreichen kann. Wie man die Signalstärke in einen Radius umrechnen kann kannst du in meinem vorherigen Posts sehen. Man kann k entweder durch Tests einmal festlegen. Oder für jede 3er Messgruppe neu berechnen. Dies könnte evtl. Signalschwankungen ausgleichen. Man müüsste es halt mal ausprobieren. mfg |
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
