Verfasst am: 03.05.2012, 03:36
Titel: Schnittflaeche aus Kreissegment und Rechteck
Hallo!
Ich habe ein Problem, bei dem ich einfach keine Ahnung habe, wie ich auf die Loesung komme...
Ich habe ein Viereck und ein Kreissegment. Das Kreissegment hat immer eine Oeffnung von 100 grad und dreht sich um den Ursprung.
Ich brauche ein Programm, das mir die Schnittflaeche der beiden Elemente zurueckgibt... habe mir auch schon etwas ueberlegt, allerdings kann THETA beliebig variieren und somit ist meine Loesung nur fuer die einfachsten Spezialfaelle richtig.
Ich habe eine Skizze angehaengt in der Hoffnung, dass sie das Problem besser beschreibt.
Konstante Groessen:
Radius r=4.5
Das Rechteck mit l=5 und b=3.5.
alpha+beta=100grad
Die erste Annahme ist, dass das Kreissegment immer ~ungefaehr~ so liegt wie in der Zeichnung. D.H., dass der Punkt P1 quasi immer da sein wird wo er in der Zeichnung liegt. Dann kann ich die Schnittflaeche in ein dreieck und ein kleines Kreissegment aufspalten...
meine Idee war:
Code:
[xout,yout]=linecirc(inf,3.5,0,0,4.5); %gibt mir die schnittlinie eines Kreises mit einer Geraden zurueck.
Z=max(yout); %gibt mir dann den y-wert von P1 zuruck
alpha=atan(Z/3.5);
beta=180-100-alpha;
flaeche=4.95+(4.5*4.5*pi*beta/360)
Hat jemand eine Idee wie ich es richtig mache? Bzw. wie ich es schaffe eine allgemeine Loesung zu finden fuer alle THETAs und im idealfall auch wenn ich das Rechteck beliebig verschiebe. Vielleicht hat jemand ein aehnliches m-file schon erstellt.
Falls noch Fragen sind, lasst es mich wissen, ich bin wirklich um jede Hilfe dankbar!
ein sehr interessantes Problem! Ich mag solche Aufgaben. Kannst du bitte etwas Näheres zu dem sog. allgemeinen Fall sagen. Soll das Rechteck tatsächlich an einer beliebigen Stelle im Koordinatensystem gesetzt werden können? Gilt dies auch für das Dreieck? Je mehr Restriktionen es für die Lage dieser beiden Figuren gibt, desto besser ist das für eine (allg.) rechnerische Lösung!
Jaaa ich mag solche Aufgaben auch, aber ich schaff es einfach nicht ^^, vor allem weil ich nicht soooo der matlab checker bin!
Also, das kreissegment, kann irgendwo liegen, allerdings mit der "spitze" im Ursprung (also rund um den Nullpunkt), hat aber immer den festen Radius und den 100° Öffnungswinkel.
Das Rechteck kann wirklich überall liegen. Da dass aber relativ schwer ist, wäre ich froh, wenn es ja nur eine Lösung gäbe für den Fall, dass es so schon ideal(also schön bündig mit der x und y achse) im 2. Quadranten läge! Oder im 1.,3. oder 4. dann als nächstes. Hammer gut wäre wenn ich es wirklich beliebeig ansetzen könnte!
... bis ich alleine die Lösung finde... oh jeh... das dauert ewig ^^
OK, dass das Kreissegment um den Nullpunkt rotiert, ist kein großes Problem, aber, dass das Rechteck tatsächlich beliebig gesetzt werden soll, macht das ganze sehr komplex. Bist du dir da sicher? Was nützt es da einem, klein anzufangen, wenn man dann letztlich eh alle möglichen Fälle erschlagen muss.
Ja... das ist es eben, was es so kompliziert macht! Dass das Rechteck irgendwo liegen kann...
Ja, da hast du recht, ich bin auch der Meinung, dass man es gleich richtig machen sollte! Allerdings ist das Problem, genau wie du sagst, dadurch, dass das Rechteck beliebig gesetzt werden kann sehr komplex.
ich habs mal mit monte carlo versucht. is aber natürlich nicht sehr schnell und auch nur bedingt genau
x,y sind hir die linke untere ecke des rechtecks und th is theta in grad
Puh, das wird aber eine Menge Arbeit, falls mir nicht noch eine geistreiche Idee für eine wesentliche Vereinfachung einfällt.
Eine Frage noch: Sind die Seiten des Rechtecks immer parallel zu den Koordinatenachsen?
Und nun der, meiner Meinung nach, erste Schritt bei dieser Betrachtung. Es ist die Frage, wann der Fall eintritt, dass es keinen gemeinsamen Flächeninhalt geben kann. Dies gilt, wenn Radius des Kreissegmentes kleinergleich ist als die Beträge aller Ortsvektoren zu den Eckpunkten des Rechtecks. Andernfalls existiert eine Schnittfläche. Nun würde ich systematisch eine Fallunterscheidung hinsichtlich der relativen Lage der Figuren aufbauen. Fange damit an, ich liefere auch Vorschläge.
@Winkow: Dein Ansatz ist prinzipiell natürlich (näherungsweise) zielführend. Mich würde allerdings interessieren, wie du das genau gemacht hast, ohne deinen Code nachzuvollziehen. Kannst du ein paar Worte zu dem Vorgehen verlieren. Es müssen ja Zufallszahlen erzeugt werden einmal für das Innere es Rechtecks (das ist leicht...) und einmal für das Innere des Kreissegmentes. Dann kann man fragen, welche Punkte innerhalb des Schnittes liegen, falls existent. Diese Zahlen bringt man letztlich ins Verhältnis und erhält damit den Flächeninhalt mit stochastischer Konvergenz.
ich erzeuge paare von zufallszahlen innerhalb der grenzen des rechtecks und überprüfe dann wie viele von diesen auch innerhalb des kreisabschnitts liegen.
@MaFam: Ja, das Rechteck ist immer parallel zu den Achsen.
Wobei die Loesung von Winkow absolut ausreichend ist!
@ Winkow: Vielen vielen vielen Dank! Auf genau so etwas habe ich gehofft! Ich bin beeindruckt! So ein komplexes Problem und du loest es in ein paar Zeilen! Wenn es fuer dich ok ist, koenntest du mir das Programm erklaeren!? Weil das ist ja Gold wert! Ich koennte damit ja die Schnittflaechen von Objekten egal welcher Form berechnen! Und... wie kommt man ueberhaupt auf so etwas (Ich meine die "Monte Carlo Methode" zu benutzen)? So etwas moechte ich auch irgendwann mal koennen!
überprüfe ich ob die punkte innerhalb des kreisausschnitts sind. dann wird einfach der anteil der punkte der in beiden liegt im verhältniss zu allen punkten gesetzt und mit der fläche des rechtecks multipliziert.
Hallo, ich hatte gerade ein schweres Matlab-Problem, also dachte ich
mir ich löse im Gegenzug das Problem von jemand anderem.
Zunächst:
In geschlossener Form wie der theta-Versuch wird das Problem nicht lösbar sein, ich bin zwar kein Mathematiker aber die Flächen haben soviele Unstetigkeiten und Singularitäten + Kontaktproblem > keine Chance.
Numerisch (also näherungsweise) geht Monte-Carlo, oder das Kreissegment mit Strahlen abtasten, oder die Fläche gleichmäßig mit Punkten rasten und prüfen usw...da sind der Phantasie keine Grenzen gesetzt
Exakt geht aber auch zum Beispiel mit diesem Algorithmus:
1. Rechteck durch 4 Linien, Segment durch 2 Linien, 1 Kreis beschreiben
2. Eckpunkte beider Körper in ein Array (array1) speichern
3. Eckpkt. aussortieren, die außerhalb des and. Körpers liegen
4. Schnitt: Kreissegmentelemente mit jeder Linie des Rechteckes (Bibliot.)
die Monte-Carlo-Methode hatte ich auch im Kopf. Aus numerischer Sicht ist allerdings davon abzuraten, da eben nur stochastische Konvergenz vorliegt. Oder, man muss eben damit Leben. Wenn man allerdings Wert auf Genauigkeit legen will/muss, dann ist das eher nicht der richtige Weg.
@Bluesmaster: Ich denke, dass eine geschlossene Form machbar ist. Es gibt auch keine Unstetigkeiten oder Singularitäten, sonst wäre dein Vorschlag auch nicht durchführbar. Allerdings ist dieser Weg sehr kompliziert und bedarf vieler Fallunterscheidungen. Praktisch gesehen ist das daher kaum brauchbar.
Deine Idee, die aber auch näherungsweise funktioniert, ist wohl die beste. Man diskretisiert den Rand der Objekte. Durch Prüfung auf Lage der Randpunkte weiß man, welche im Inneren oder auf dem Rand des jeweils anderen Objektes liegen. Mit der Gaußschen Trapezformel ("Matlab: polyarea") für allgemeine Polygone kann man dann den Flächeninhalt ausrechnen. Durch eine Verfeinerung der Diskretisierung auf den Rändern kann man die Genauigkeit beliebig hochschrauben.
Der Algorithmus lässt sich dann wie folgt grob beschreiben:
1. Diskretisierung der Ränder -> Verfeinerung je nach Genauigkeit
2. Prüfen auf Schnittmenge über das Innere und den Rand der Objekte
3. Gaußsche Trapezformel für Polygone anwenden: http://de.wikipedia.org/wiki/Gau%C3%9Fsche_Trapezformel
Du hast meinen Algorithmus falsch verstanden. Er arbeitet sehr wohl
exakt. Es geht nicht um die Annäherung der Schnittfläche durch ein
Polygon sondern um die Unterteilung der Schnittfläche in:
- Polygon + Kreissegment (rosa fläche in Skizze)
Unstetigkeiten:
=========
1. Das Kontaktproblem: Ab der Berührung der beiden Flächen steigt die
Schnittfläche "schlagartig" an
2. Rechteck und Kreisausschnitt lassen sich nicht durch geschlossene
Kurven beschreiben sondern haben ECKEN!
Fallunterscheidungen = "nicht geschlossen beschreibbar"
also ein Formel nach der Machart:
wird niemand finden. Zumindest nur Spezialfälle von denen ich mal ein
"paar" nennen kann:
- Kreissegment liegt vollständig in Rechteck
- Rechteck liegt vollständig in Kreis
- Spitze des Kreissegments innerhalb/ außerhalb rechteck
- Kreisbogen scheidet eine Rechteckseite einmal/ zweimal
- Kreisbogen schneidet 2/ 3/ 4 Rechteckseiten
- Kreisbogengrenze direkt auf Recheckkante
usw und so fort + Kombinationen
Viel Erfolg für den der für die Fälle Unterscheidungsalgorithmen formuliert und Formeln ausarbeitet
Nein, da steigt nichts schlagartig an. Selbst wenn man das ganze dynamisch auffasst und die Objekte verschiebt, ist das ganze stetig, wenn man stetig verschiebt. Auch der Rand der Schnittfläche ist stetig.
Gut, dann habe ich deinen Algorithmus nicht verstanden. Wie willst du denn im allgemeinen Fall das Kreissegment (es können auch zwei sein) identifizieren?
1. Das Kontaktproblem > Sobald sich die Flächen berühren kommt es
zu einem Knick in der Flächenfunktion. Was akademisch klingt hat die
praktische Konsequenz, dass es hier nicht mehr ohne
Fallunterscheidung geht und Fallunterscheidung ist das Gegenteil von
"geschlossen beschreibbar"
2. Die Flächen selbst lassen sich nicht stetig beschreiben demzufolge auch
die Funktion ihrer Schnittfläche nicht. Passiert der Kreisausschnitt
beispiels weise eine Ecke des Rechteckes wird wieder eine
Fallunterscheidung nötig.
Wahrscheinlich ist der Aufhänger dass ich Fallunterscheidung und "geschlossen beschreibbar" trenne. Meinen werden wir wohl das gleiche.
Zusatz:
-Die Kreissegmente identifiziere ich schon beim Schnittvorgang (indem ich
mir in array2 merke wann der Kreis geschnitten wird)
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS