Forum: Mikrocontroller und Digitale Elektronik Position innerhalb eines Rechtecks?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Peter II (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von guest (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hans schrieb:
> Das Problem ist, das die Linienangaben des Rechteckes durcheinander
> sind.

Dann sortier sie halt bzw. vertausche Anfang und Ende der Linie.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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.
von Possetitjel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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)

von Jim M. (turboj)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Marc V. (Firma: Vescomp) (logarithmus)


Bewertung
0 lesenswert
nicht lesenswert
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
von Georg (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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

von Possetitjel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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).

von Wolfgang (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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 ;-)

von Possetitjel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Johann L. (gjlayde) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
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
von Marc V. (Firma: Vescomp) (logarithmus)


Bewertung
0 lesenswert
nicht lesenswert
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.

von Possetitjel (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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... :)

von Hans (Gast)


Bewertung
0 lesenswert
nicht lesenswert
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;
                    }
                    }
                  }

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.