Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Schnittmenge beliebig vieler Kreise

Schnittmenge beliebig vieler Kreise

Universität / Fachhochschule

angewandte lineare Algebra

Tags: Angewandte Lineare Algebra, Kreis, Schnittmenge

ckohrt aktiv_icon

00:27 Uhr, 15.04.2010

Hallo,

ich benötige eher eine Idee als eine Lösung, wobei letzteres auch schön wäre.

Gegeben:

K_{1} : {(x - a_{1})}^{2} + {(y - b_{1})}^{2} = 1

K_{2} : {(x - a_{2})}^{2} + {(y - b_{2})}^{2} = 1

. .

K_{n} : {(x - a_{n})}^{2} + {(y - b_{n})}^{2} = 1

. .

.

Ich möchte zunächst die Kreise

K_{1}

und

K_{2}

betrachten und berechne die Schnittmenge, zB durch Gleichsetzen. Wenn nun ein 3. Kreis

K_{3}

dazu kommt könnte ich 3 Gleichungen Gleichsetzen. Nun weiß ich aber vorher nicht wieviele Kreise kommen und ich möchte bei jedem neuen Kreis nicht alle anderes Kreise anschauen müssen, da ich das auf dem Computer in einem Algorithmus anwenden möchte. Die Laufzeit spielt eine große Rolle.

Hintergrund:
Ich möchte bei gegebenen Kugeln im

3 D

herausfinden, ob diese mit einer Toleranz 1 hintereinander liegen auf einer Geraden. Dabei gibt es den Punkt

P_{0},

der fix und ohne Toleranz ist. Die Gerade geht also von

P_{0}

durch alle Kugeln bzw. ich möchte wissen, ob es eine Gerade gibt, die durch alle Kugeln geht und natürlich durch

P_{0}

.
Ich muß sicherstellen, dass alle Kugelmittelpunkte die maximale Entfernung 1 zur Gerade haben und für letztere muß mit jeder Kugel eine neue Lage berechnet werden.

Oben versuche ich das Problem auf den

2 D

Fall zu reduzieren indem ich erstmal einen erlaubten Bereich (=Schnittmenge aller Kreise) berechne und eine Ebene definiere, die orthogonal zu meiner Geraden liegt.Dort können dann die Kugeln als Kreise abgebildet werden.

Ideen sind nun gefragt!

Gruß
Christian

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:
Kreiszahl (Mathematischer Grundbegriff)
Kreis (Mathematischer Grundbegriff)
Elementare Kreisteile (Mathematischer Grundbegriff)

Online-Übungen (Übungsaufgaben) bei unterricht.de:

Grundbegriffe der ebenen Geometrie
Kreis und Mittelsenkrechte
Kreis: Umfang und Flächeninhalt
Kreise und Lagebeziehungen
Mengenlehre
Thaleskreis, Umkreis, Inkreis und Lage von Kreis und Gerade

Zu diesem Thema passende Musteraufgaben einblenden

Bogenmaß und Gradmaß eines Winkels

Was ist der Unterschied zwischen Bogenmaß und Gradmaß eines Winkels?

Elementare Kreisteile

Wie berechne ich den Flächeninhalt eines Kreissegments und eines Kreissektors?

Flächeninhalt eines Kreisrings

Wie berechnet man den Flächeninhalt eines Kreisrings?

Kreis - Umfang und Inhalt

Wie berechne ich den Umfang und Flächeninhalt eines Kreises?

Kreiszahl Pi

Für was steht die Zahl

π

und was bringt sie mir?

arrow30

01:07 Uhr, 15.04.2010

moin

Meine Idee ist simpel . du nimmst i-einen Kugel von denen mit MittelPunkt

M_{1} \to (\begin{matrix} m_{1} \\ m_{2} \\ m_{3} \end{matrix})

. und der Punkt

P_{0}

sei

\to (\begin{matrix} p_{1} \\ p_{2} \\ p_{3} \end{matrix})

. jetzt kann man eine Gerade zwischen

M_{1}

und

P_{0}

bilden

(2

Punkte bestimmen nur eine Gerade ) . die sieht im Raum so aus :

g = : (\begin{matrix} m_{1} \\ m_{2} \\ m_{3} \end{matrix}) + t \cdot (\begin{matrix} m_{1} - p_{1} \\ m_{2} - p_{2} \\ m_{3} - p_{3} \end{matrix}) \to t \in ℝ

es bleibt nur noch zu prüfen ob der Abstand aller Mittelpunkten von dieser Gerade

\leq 1

ist . dafür gibt es ja Formel. Abstand Punkt-Gerade
Gruß Arow

ckohrt aktiv_icon

08:35 Uhr, 15.04.2010

Hallo Arow,

daran habe ich auch schon gedacht. Damit würde aber die erste Kugel schon meine gerade

g_{1}

festlegen. Damit würde ich den Lösungsraum verkleinern, da es sein könnte, dass die Gerade auch in der ersten Kugel schon den Abstand 1 hat, weil folgende Kugeln nicht auf

g_{1}

liegen. weil ich die gerade nicht festlegen kann wollte ich von Kugel zu Kugel berechnen was der Lösungsraum ist. Daher müßte die Gerade von Kugel zu Kugel neu berechnet werden und ich muß für diese dann prüfen, ob sie im erlaubten (=bisherigen) Lösungsraum liegt. Wenn nicht, dann gibt es keine Gerade mehr und ich kann den Algorithmus stoppen, sonst mache ich weiter bis ich eine Kugel finde die nicht mehr auf der Geraden liegt:

1. setze

n = 1

2. berechne erlaubten Bereich

B_{n}

für die Gerade

g_{n}

von

P_{0}

nach

M_{n}

aus der Tangentenschar

t_{n} (P_{0}

mit allen Tangenten von

M_{n}

die durch

P_{0}

laufen - für die Toleranz)
3. Addiere neue Kugel

M_{n + 1}

und berechne neuen erlaubten Bereich

B_{n + 1}

aus der Tangentenschar

t_{n + 1} (P_{0}

mit allen Tangenten von

M_{n + 1}

die durch

P_{0}

laufen - für die Toleranz)
4. Berechne

g_{n + 1},

so dass sie innerhalb des erlaubten Bereiches

B_{n + 1}

liegt
5. prüfe, ob

g_{n + 1}

existiert
wenn ja:

n = n + 1,

goto 2.
wenn nein goto 4.
4. Beginne von neuem mit neuen Kugeln

Hier ergeben sich die folgenden Schwierigkeiten:

a)

die erlaubten Bereiche sind Schnittmengen

\to

sehr schwer zu berechnen

b)

die Gerade

g_{n + 1}

innerhalb des erlaubten Bereiches

B_{n + 1}

ist schwer zu berechnen

Ich dachte schon an Regressionsgeraden, aber da bin ich nicht wirklich weiter gekommen.

Christian

ckohrt aktiv_icon

09:07 Uhr, 15.04.2010

Evtl. ginge auch so eine Lösung:

Eine Gerade

g_{n}

durch

P_{0}

3 D

kann durch Punkt, Richtung und Abstand

r

dargestellt werden, wobei die Richtung aus 2 Winkel

α

und

β

besteht (Kugelkoordinaten):

Umrechnung von kart. nach Kugelkoordinaten (mit

K_{n}

seien die Kugelmittelpunkte):

zur Vereinfachung, da

P_{0}

nicht im Ursprung liegt:

D_{n}_x = K_{n}_x - P_{0}_x

D_{n}_y = K_{n}_y - P_{0}_y

D_{n}_z = K_{n}_z - P_{0}_z

r = \sqrt{D_{n}_x^{2} + D_{n}_y^{2} + D_{n}_z^{2}}

α =

arccos

(D_{n}_\frac{z}{r})

β =

arctan2

(D_{n}_\frac{y}{D_{n}}_x)

(arctan2 siehe en.wikipedia.org/wiki/Atan2

Nun könnte ich für jeden Richtungswinkel folgende Formel anwenden:

α = α_{K_{{min}}} + \frac{α_{K_{{max}}} - α_{K_{{min}}}}{2}

β = β_{K_{{min}}} + \frac{β_{K_{{max}}} - β_{K_{{min}}}}{2}

wobei

z . B

β_{K_{{min}}}

das kleinste

β

aller bisheriger Kugeln

K

ist.

Anschaulich:
Ich möchte jeweils immer die Winkelhalbierende der Punkte nehmen, die am weitesten entfernt liegen, jeweils für die Komponente

α

und

β

.

Pseudo-code:
0.

n = n + 1

1. Berechne neue Kugel

K_{n}

die Geradenwinkel

α_{n}

und

β_{n}

2. Prüfe ob

α_{n}

und

β_{n}

die Winkel

α_{K_{{min}}}

oder

α_{K_{{max}}}

ändert
3. Falls nein, goto 4. Falls ja, goto 5.
4. Prüfe, ob

K_{n}

die Gerade berührt
5. Falls ja goto

0 .,

sonst goto 8.
6. Prüfe ob alle

K

die Gerade berühren
7. Falls ja, goto

0 .,

falls nein goto 8.
8. Beende Berechnung der Geraden und beginne komplett neu

Problem:

a)

Von der Rechenzeit ist es unschön jedesmal alle Punkte prüfen zu müssen, ob sie die Gerade berühren.

Ist das ein gangbarer Weg?

Christian

arrow30

14:59 Uhr, 15.04.2010

hallo
Zitat 1.
"Damit würde aber die erste Kugel schon meine gerade

g 1

festlegen. Damit würde ich den Lösungsraum verkleinern, da es sein könnte, dass die Gerade auch in der ersten Kugel schon den Abstand 1 hat, weil folgende Kugeln nicht auf

g 1

liegen."

ich fürchte ich verstehe dich nicht gut. was meinst du mit "Lösungsraum verkleinern "?

2.
" es könnte sein, dass die Gerade auch in der ersten Kugel schon den Abstand 1 hat, weil folgende Kugeln nicht auf

g 1

liegen"

ist doch prima wenn die nächste Kugel den Abstand

d > 1

hat ,wäre ja optimal .dann muss man nicht weiter prüfen .

3. deine 2. Lösung ist nach dem Verfahren ->" Warum einfach , wenn es auch schwerer geht ? "

ckohrt aktiv_icon

15:24 Uhr, 15.04.2010

Hallo Arrow,

du hast Recht, bisher ist alles sehr kompliziert. Ich finde keine andere Lösung. Vielen Dank für deine Hilfe! Ich versuche auf deine Fragen zu antworten (bin in der Arbeit, daher heute Abend evtl. mit Zeichnung):

Zitat 1.
"Damit würde aber die erste Kugel schon meine gerade

g 1

festlegen. Damit würde ich den Lösungsraum verkleinern, da es sein könnte, dass die Gerade auch in der ersten Kugel schon den Abstand 1 hat, weil folgende Kugeln nicht auf

g 1

liegen."

ich fürchte ich verstehe dich nicht gut. was meinst du mit "Lösungsraum verkleinern "?

Antwort:
Nun, wenn ich bei der ersten Kugel schon die Linie festlege, obwohl sie eine Toleranz haben darf, dann schränke ich mögliche Lösungen ein. Wenn ich mir vorstelle, dass ich irgendweine Gerade finden muss die duch

P_{0}

und die Kugeln geht, dann kann ich diese Gerade zu jedem Zeitpunkt neu festlegen. Wenn ich mir also 2 Kugeln vorstelle, die sich gerade berühren, und die Gerade läuft von

P_{0}

durch Mittelpunkt der 1. Kugel, dann gibt es Fälle, wo die Gerade nicht durch die 2. Kugel läuft. Wenn ich die Gerade neu berechne schon. Wenn dem so ist schränke ich mir den Lösungsraum ein.

2.
" es könnte sein, dass die Gerade auch in der ersten Kugel schon den Abstand 1 hat, weil folgende Kugeln nicht auf

g 1

liegen"

ist doch prima wenn die nächste Kugel den Abstand

d > 1

hat ,wäre ja optimal .dann muss man nicht weiter prüfen .

Antwort:
Schon, allerdings versuche ich ja eine Gerade durch zu legen, und nicht Fälle zu finden, wo dies nicht möglich ist. Obiger Fall könnte eintreten, wenn ich die Gerade mit Kugel

2 . .

. neu berechne und am Ende sich herasustellt, dass alle Kugeln nacheinander liegen, is auf die erste. Die erste könnte eine Position immernoch im Abstand 1 zur Geraden einnehmen, während die anderen alle auf bzw. nahe der neu berechneten Geraden liegen.

3. deine 2. Lösung ist nach dem Verfahren ->" Warum einfach , wenn es auch schwerer geht ? "

Antwort:
Deshalb versuche ich eine möglichst einfache Lösung zu finden.....

Ich bin für jede Idee dankbar und gehe alle Möglichkeiten nach!

Christian

arrow30

16:00 Uhr, 15.04.2010

hallo Christian

wenn ich die Aufgabe gut verstehe , du sollst einen Alg. schreiben ,der prüft ,ob die Kugel auf einer Linie liegen (mit Toleranz

1)

.Die Rückgabe dieses Alg. ist Ja die sind auf einer Gerade oder nein sind sie nicht.

"wenn ich bei der ersten Kugel schon die Linie festlege, obwohl sie eine Toleranz haben darf, dann schränke ich mögliche Lösungen ein. "

\to

das musst du dir noch mal überlegen. Toleranz hat mit

P

nichts zu tun. siehe Bild mag sein verstehst du mich dann besser.

ckohrt aktiv_icon

23:12 Uhr, 15.04.2010

Hallo Arrow,

nicht ganz aber ich versuche die Aufgabe zu beschreiben:

Aufgabe:
Ich bekomme eine Liste von Punkten im

3 D

Raum.
Die Punkte beschreiben entweder eine Linie, einen Kreis oder keines von beiden also unbestimmt.
Nun können es

1000

Punkte und mehr sein.

Anforderungen:
1. Kurze Laufzeit
2. der erste Punkt muß auf der Linie liegen
3. alle anderen Punkte dürfen einen maximalen Abstand von 1 haben

Den Kreis konnte ich schon lösen. die vermeintlich einfache Aufgabe Linie nicht.

Hier habe ich eine Zeichnung, die ich glaube, dass sie nach deinem Ansatz zu einem "Nein, nicht auf der Linie" führt und bei meinem finde ich eine Lösung.

...Bild gezeichnet... und mir ist aufgefallen, dass mein obiger Ansatz auch icht funktioniert... da ich die 2 Kugeln, die den größten und kleinsten Winkel aufweisen als Winkelhalbierende verwende.

Daher habe ich hier vielleicht auch gleich eine zweite Zeichnung. Hier müßte man die Abstände zu der Geraden ermitteln (kein Problem) und die Gerade y=mx+t so berechnen, dass der Abstand eben

\leq 1

ist.

Im

2 D

und Punkt

P_{0} = (0; 0)

und

t = (0; 0)

d_{n} = \frac{| g \times (K_{n} - t) |}{| g |}

d_{n} = \frac{| g \times K_{n} |}{| g |}

g

sei die Richtung der Geraden.

Also

\frac{| g \times K_{n} |}{| g |} \leq 1

\frac{| g | \cdot | K_{n} | \cdot sin (α_{n})}{| g |} \leq 1

mit

α_{n} =

Winkel zwischen

g

und

K_{n}

.

Mit

| g | = 1

| K_{n} | \cdot sin (α_{n}) \leq 1

Also mit

ε_{n} =

arcsin

(\frac{1}{| K_{n} |})

- ε_{n} \leq α_{n} \leq ε_{n}

Christian

ckohrt aktiv_icon

11:33 Uhr, 16.04.2010

Hallo Arrow,

du würdest einfach die Linie mit dem neuen Mittelpunkt verbinden und prüfen, ob die anderen Kugelmittelpunkte in der Toleranz liegen. Richtig?

Gruß
Christian

ckohrt aktiv_icon

13:23 Uhr, 17.04.2010

Vielen Dank Arrow, deine Fragen haben mich auf die richtige Lösung gebracht.

Anbei Bilder mit Lösung!

Christian

748655

747868

	Status: nicht eingeloggt	Noch nicht registriert?