Hallo, ich habe in Eagle die Aufgabe: Prüfe ob ein Punkt innerhalb eines Rechtecks liegt. Das Rechteck wird aber durch die Pos Angaben der 4 Linien bestimmt. Punkt: x, y Rechteck: x1,y1 nach x11,y11 x2,y2 nach x22,y22 x3,y3 nach x33,y33 x4,y4 nach x44,y44 Das Problem ist, das die Linienangaben des Rechteckes durcheinander sind. Beispiel: Punkt: 1.3, 9.6 Rechteck: 0.3,10 nach 0.3,8.5 2.9,10 nach 0.3,10 2.9,8.5 nach 2.9,10 0.3,8.5 nach 2.9,8.5 Also der Punkt liegt innerhalb des Rechtecks. Ich kann nicht immer prüfen ob der Punkt größer als x1 und kleiner als x11 ist .. da es vorkommen kann, das x11 der kleinere und x1 der größere Wert ist. Ich könnte zwar immer zuvor die "Ausrichtung" der Linie prüfen aber das ist aufwendig. Kann man das elegant lösen? Danke
Hans schrieb: > Kann man das elegant lösen? ja, man rechnen vom Punkt aus eine Linie in Beliebiger Richtung. Dann Zählt man die Schnittpunkte mit jeder andere Line von dem Rechteck (oder auch Polygon). Wenn es eine gerade Anzahl ist, dann ist der Punkt außen.
Hans schrieb: > Das Problem ist, das die Linienangaben des Rechteckes durcheinander > sind. Dann sortier sie halt bzw. vertausche Anfang und Ende der Linie.
1) Bilde das arithmetische Mittel der Ecken. Das ist der Schwerpunkt S
des Rechtecks.
Für jede Seite:
2) Stelle die Geradengleichung auf, z.B. g(x) = P + x*R wo P ein Punkt
auf der Geraden ist (z.B. ein auf der Seite liegender Eckpunkt) und
R die Richtung, z.B. R = P1 - P2 für zwei Punkte auf g.
3) Nimm ein Normale auf g, diese habe Richtung N mit N·R = 0.
4) Um zu testen, ob ein Punkt A auf einer bestimmten Seite ("links"
oder "rechts") von g liegt, berechne s(A) = N · (g(A) - A).
5) Falls s(A) = 0 dann liegt der Punkt auf g. Zwei Punkte A und B
liegen auf der gleichen Seite von g wenn s(A) und s(B) gleiches
Vorzeichen haben.
6) Da S im Rechteck liegt, liegt ein Punkt A im Rechteck falls für alle
Seiten g gilt: s(S) * s(A) > 0 (A liegt im Innern des Rechtecks) bzw.
s(S) * s(A) >= 0 (A liegt im Innern oder auf einer Seite).
Ein "Sortieren" der Seiten ist nicht erforderlich.
:
Bearbeitet durch User
Beitrag #4939888 wurde vom Autor gelöscht.
Hans schrieb: > ich habe in Eagle die Aufgabe: In welchem Unterrichtsfach hat man "Eagle"? > Prüfe ob ein Punkt innerhalb eines Rechtecks liegt. Das > Rechteck wird aber durch die Pos Angaben der 4 Linien > bestimmt. > > Punkt: > x, y > > Rechteck: > x1,y1 nach x11,y11 > x2,y2 nach x22,y22 > x3,y3 nach x33,y33 > x4,y4 nach x44,y44 So, wie Du das hier aufgeschrieben hast, sind das acht verschiedene Punkte. Kann man in einem Rechteck wirklich acht (echt verschiedene) Punkte unterbringen? > Kann man das elegant lösen? Definiere "elegant". - Aber, ja, man kann das elegant loesen. Ueberlege Dir zuerst mal, ob das Rechteck in allgemeiner Lage gegeben ist oder ob ein Spezialfall vorliegt (z.B. achsparallele Seiten). Ueberlege Dir dann, wieviel Punkte Deines Rechteckes frei (WIRKLICH frei) waehlbar sind, und welche/wieviele sich zwingend aus den gewaehlten Punkten ergeben. Dann ueberlegst Du Dir, wie Du die charakterisierenden Punkte aus den gegebenen Groeszen (Strecken) extrahieren kannst. Der letzte und einfachste Schritt ist dann, den Testpunkt mit den gefundenen charakteristischen Punkten zu vergleichen.
Johann L. schrieb: > 4) Um zu testen, ob ein Punkt A auf einer bestimmten Seite ("links" > oder "rechts") von g liegt, berechne s(A) = N · (g(A) - A). Muss heißen s(A) = N · (P - A)
Wenn Dein Rechteck nicht gedreht ist, geht es immer von (minX,minY) nach (maxX,maxY). Also einfach die Minima und Maxima der X und Y Werte bestimmen. Ein Punkt ist genau dann innerhalb des Rechteck wenn MinX < x < MaxX und MinY < y <MaxY gilt.
Hans schrieb: > Rechteck: > 0.3,10 nach 0.3,8.5 > 2.9,10 nach 0.3,10 > 2.9,8.5 nach 2.9,10 > 0.3,8.5 nach 2.9,8.5 Wenn es ein Rechteck ist:
1 | MinX = 10000.0; MaxX = -10000.0; |
2 | MinY = 10000.0; MaxY = -10000.0; |
4 Zeilen einlesen, Min und Max Werte finden, mit Punkt vergleichen. Fertisch. P.S. @Jim M. Das ist schon das 3-te Mal dass du um 1 Minute schneller bist. Muss mir etwas ausdenken...
:
Bearbeitet durch User
Hans schrieb: > Kann man das elegant lösen? Die Angaben sind hochgradig wirr, ein Viereck ist nicht durch 8 Punkte bestimmt, sondern durch 4. Und was hat das ganze mit Eagle zu tun? Aber wenn es tatsächlich ein Rechteck ist, könnte man elegant das Koordinatensystem so drehen, dass das Rechteck achsparallel ist, und kommt dann mit 4 simplen Vergleichen aus. Das konkret angegebene Rechteck ist aber schon achsparallel, damit ist das eine total primitive Aufgabe. Georg
Jim M. schrieb: > Wenn Dein Rechteck nicht gedreht ist, geht es immer > von (minX,minY) nach (maxX,maxY). Ja. - Etwas sauberer formuliert: Ein achsparalleles Rechteck ist durch Angabe zweier diagonal liegender Punkte vollstaendig beschrieben. (Es ist also egal, welches der beiden Paare man waehlt.) > Also einfach die Minima und Maxima der X und Y Werte > bestimmen. Genau. > Ein Punkt ist genau dann innerhalb des Rechteck wenn > MinX < x < MaxX und MinY < y <MaxY gilt. Wer (wie ich) zusammengesetzte Vergleiche hasst, kann auch darauf testen, ob der Punkt auszerhalb liegt: x < MinX --> drauszen, x > MaxX --> drauszen... Wenn er nicht drauszen liegt, muss er drinnen liegen (wobei ich den Rand zum Rechteck zaehle).
Georg schrieb: > Und was hat das ganze mit Eagle zu tun? Die Bezugnahme auf EAGLE ist vermutlich die einzige Idee des TOs gewesen, um das Problem thematisch irgendwie in einem Elektronikforum unterzubringen ;-)
Johann L. schrieb: > 1) Bilde das arithmetische Mittel der Ecken. [...] Mich fasziniert jedes Mal die komplizierte Schoenheit Deiner Vorschlaege :) Die Idee mit dem Schwerpunkt ist gut, aber geht das nicht einfacher? Kann man nicht verwenden, dass die Strecke AS genau dann keinen Schnittpunkt mit einer der Seiten hat, wenn A im Rechteck liegt? (Und stimmt diese Aussage ueberhaupt?) Zu einer anderen Zeit in einer anderen Welt gab es mal den Vorschlag, so eine Art Umlaufintegral zu bestimmen. Wenn der Punkt auszerhalb liegt, ist das Integral Null; wenn er innerhalb liegt, verschieden von Null.
Possetitjel schrieb: > Johann L. schrieb: > >> 1) Bilde das arithmetische Mittel der Ecken. [...] > > Mich fasziniert jedes Mal die komplizierte Schoenheit > Deiner Vorschlaege :) Wenn eine Division durch 8 schon zu kompliziert ist S = (P1 + P2 + P3 + P4 + P5 + P6 + P7 + P8) / 8 Schreibarbeit, aber kompliziert? Jedenfalls müssen die Punkte dazu nicht sortiert sein, die Ecken brauchen nicht exakt übereinzustimmen (wegen möglicher Rundungsfehler o.ä.) > Die Idee mit dem Schwerpunkt ist gut, aber geht das > nicht einfacher? Es hat zumindest keine Einschränkung wie Achsparallelität. Wenn P und Q zwei zu einer Seite gehörende Ecken sind, dann ist z.B. N = (Qy-Py, Px-Qx) und s(A) = N · (P - A) = (Qy-Py) * (Px-Ax) + (Px-Qx) * (Py-Ay) 5 Additionen und 2 Multiplikatonen, die Eagle für dich macht. Bevor ich da anfange, Seiten nach Umlauf zu sortieren, überlegen muss welche (doppelt vorhandenen) Punkte wie zusammengehören, Assertions über Achsparallelität einführe, mir den Kopp über Rundungsfehler zerbreche (falls es nicht gerade in Eagle eingesetzt werden soll) lass ich einfach 8 Mal s() ausrechnen. Und das Verfahren funktioniert für alle konvexen Polygone, unanhängig von der Anzahl der Seiten (Komplexität geht linear mit Seitenzahl). :-)) > Zu einer anderen Zeit in einer anderen Welt gab es mal > den Vorschlag, so eine Art Umlaufintegral zu bestimmen. > Wenn der Punkt auszerhalb liegt, ist das Integral Null; > wenn er innerhalb liegt, verschieden von Null. Ich hab grad mal in ne Snake-Implementierung (C für AVR) geschaut, die die Umlaufzahl berechnet, um zu bestimmen, ob ein zufällig gelegter Punkt im Spielfeld liegt. Das Spielfeld besteht aus achsparallelen Linienstücken, ist aber i.d.R. weder konvex noch einfach zusammenhängend (kann Löcher, Ein- und Ausbuchtungen haben). Ist weniger Arithmetik als oben das, aber nicht so einfach nachzuvollziehen.
:
Bearbeitet durch User
Johann L. schrieb: > Und das Verfahren funktioniert für alle konvexen Polygone, unanhängig > von der Anzahl der Seiten (Komplexität geht linear mit Seitenzahl). Es ging aber um Rechteck. 4 Zeilen muss man sowieso einlesen. Ergibt 8 X_Punkte und 8 Y_Punkte die man sich merken muss (oder sonstwie verarbeiten).
1 | MinX = 10000.0; MaxX = -10000.0; |
2 | MinY = 10000.0; MaxY = -10000.0; |
3 | |
4 | // 8 Durchläufe mit jeweils 2 Vergleichen.
|
5 | for (uint8_t zc=0; zc<=7; zc++) { |
6 | if (x[zc] > MaxX) { MaxX = x[zc]; } |
7 | else if (x[zc] < MinX) MinX = x[zc]; |
8 | if (y[zc] > MaxY) { MaxY = y[zc]; } |
9 | else if (y[zc] < MinY) MinY = y[zc]; |
10 | }
|
11 | // Und Vergleich mit Punkt...
|
12 | if ((pointX >= MinX) && (pointX <= MaxX)) & ((pointY >= Miny) && (pointy <= MaxY)) { ... } |
13 | else {... } |
Schneller als dein Vorschlag vielleicht nicht, aber einfacher sicher.
Johann L. schrieb: > Possetitjel schrieb: >> Johann L. schrieb: >> >>> 1) Bilde das arithmetische Mittel der Ecken. [...] >> >> Mich fasziniert jedes Mal die komplizierte Schoenheit >> Deiner Vorschlaege :) > > Wenn eine Division durch 8 schon zu kompliziert ist Die "komplizierte Schoenheit" bezog sich doch nicht auf das arithmetische Mittel, sondern den gesamten Algorithmus. > Schreibarbeit, aber kompliziert? Nicht das Mittel - der Rest! Wenn ich die Kernidee richtig verstanden habe, dann bestimmst Du fuer jede Rechteckseite, ob der Testpunkt A auf derselben Seite der Rechteckseite liegt wie der Schwerpunkt S, der ja bekanntermaszen im Inneren liegt. Wenn das der Fall ist, liegt A im Inneren, ansonsten liegt er auszen. >> Die Idee mit dem Schwerpunkt ist gut, aber geht das >> nicht einfacher? > > Es hat zumindest keine Einschränkung wie Achsparallelität. Es kraenkt mich etwas, dass Du zu meinem Vorschlag mit dem Schnittpunkt nix gesagt hast, denn der hat (wenn ich das recht sehe) auch nur die Einschraenkung, dass das Polygon konvex sein muss. Wenn man die Gerade, auf der S und A liegen, in der Form S+t*(A-S) hat, dann zeigt ein Schnittpunkt mit 0 < t < 1 an, dass der Punkt A auszen liegt; ansonsten liegt er innen. > Bevor ich da anfange, Seiten nach Umlauf zu sortieren, > überlegen muss welche (doppelt vorhandenen) Punkte wie > zusammengehören, Assertions über Achsparallelität einführe, > mir den Kopp über Rundungsfehler zerbreche (falls es nicht > gerade in Eagle eingesetzt werden soll) lass ich einfach > 8 Mal s() ausrechnen. Ich moechte nicht beleidigend werden -- aber gerade in mathematischen Dingen ist das, was Du tust, nicht immer repraesentativ fuer das, was "man" tut... :)
Guten Morgen an alle!
Zuerst möchte ich mich für die Rege Anteilnahme am Thema bedanken.
Ich habe mal versucht alles zu lesen und zu verstehen.
Mathematisch sind mir manche Formeln zu "hoch" :-)
Möchte aber erklären wozu das ganze:
Ich zeichne ein Rechteck als Bus in Eagle. Darin sind meine Bauteile.
Hat aber nichts mit Elektronik zu tun. Verwende Eagle als Signalplan
Software für Medientechnik.
Wenn ich ein Bauteil (das ich selber zeichne) platziere, ist das immer
innerhalb eines Bus Rechteck. Der Bus trägt den Namen des Raumes.
Ich muss nun per ULP alle Bauteile den Räumen zuteilen.
Ich habe es nun gestern soweit geschafft:
x1 und y1 ist das Bauteil.
Ich prüfe für alle Linien (sollten immer 4 Stück sein) immer ob der
Punkt in der Mitte sich befindet. Wenn nicht, kann die Prüfung gleich
abgebrochen werden.
Wenn bei allen Linien der Punkt sich in der Mitte befindet, ist das
Bauteil innerhalb des Rechtecks.
Nicht sehr mathematisch, ich weiß :-)
SH.busses(BS)
{
BS.segments(SG)
{
int check = 0;
SG.wires(W)
{
real xw1; real xw2; real yw1;
real yw2;
xw1 = W.x1 / 8128000.0; yw1 =
W.y1 / 8128000.0; xw2 = W.x2 / 8128000.0;
yw2 = W.y2 / 8128000.0;
if(((x1 > xw1 && x1 < xw2) || (x1 < xw1 && x1 >
xw2)) || ((y1 > yw1 && y1 < yw2) || (y1 < yw1 && y1 > yw2)))
{
check = 1; } else {
check = 0; }
if(check == 0){ break;
}
}
if(check == 1){ fromRoom =
BS.name; break;
}
}
}
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.