alle Integerkoordinaten eines Kreises

[Delphi-Narr]

Hallo, ich suche nach einer Schleife, die alle Integerkoordinaten eines Kreises in einem Shape ausspuckt, wenn man ihr die Left, Top, Width und Heigthwerte des Shapes gibt.
Hab leider keine Ahnung, wie ich das angehen soll, da ich in Mathematik so erwas noch nicht gemacht habe...

Liebe Grüße!

[mkinzler]

0<i<2*Pi
X-Koordinate: sin(i)*r
y-koordinate: cos(i)*r

[Delphi-Laie]

Zitat:

Zitat von mkinzler

0<i<2*Pi
X-Koordinate: sin(i)*r
y-koordinate: cos(i)*r

Oben wurden aber Integerkoordinaten erbeten.

Wegen der Transzendenz der Winkelfunktionen gibt es aber kaum welche. Auf Anhieb fallen mir nur der Mittelpunkt und die vier Punkte "oben", "unten", "links" und "rechts" ein. Dann gibt es noch ganz wenige Punkte, die bei "integrem" Winkel wenigstens eine rationale (gute Voraussetzung für integre) Koordinate haben: sin 30°=cos 60°=0,5 (analog die an 90° gespiegelten Winkel sowie alle negativen Pendants).

Also wird man sich mit Rundung (Funktion "round") behelfen müssen.

[alzaimar]

Eventuell könnte der Bresenham-Algorithmus gemeint sein.

[Phoenix]

Such mal nach dem Bresenham-Algorithmus. Der ist genau das, was Du willst.

Edith sagt: Zu langsam :cry:

[Delphi-Narr]

Also wenn ich das jetzt richtig verstanden habe, dann muss das so gemacht werden:

Shape: Alle Werte = 100

Delphi-Quellcode:

var
SL:TStringlist;

...


while 0<i<2*pi do
  begin
       SL.Add(IntToStr(round(sin(i))));
       SL.Add(IntToStr(round(cos(i))));
  end;

Stimmt das so. Wenn die Werte nur ungefähr sind, reicht das völlig aus.
Ich aber wirklich ALLE Punkte, die IM Kreis liegen, also auch Mittelpunkt, Mittelpunkt -1 etc...
Wird dies durch diese Schleife erreicht?

[Medium]

Dann hättest du anders fragen müssen, weil die Punkte im Kreis gehören nicht zum Kreis! In dem Fall langt es einfach jeden möglichen Pixel auf seinen Abstand zum Mittelpunkt hin zu überprüfen. Ist der > Width bzw. Height (welche ja gleich sein sollten, sonst ist's eine Ellipse), gehört der Pixel nicht zur Kreisfläche. Kreismittelpunkt sollte ja kein Problem darstellen, und der Vektor von einem Pixel p0 zum Mittelpunkt M ist einfach (M-p0). Davon die Länge, und du bist fast fertig.

[Delphi-Narr]

Ja gut, also ich hab mich unverständlich ausgedrückt...
Ich muss nicht die Koordinaten haben, sondern möchte nur wissen, ob bestimmte Koordinaten X Y im Kreis liegen. Das ginge bestimmt auch nur mit den Umfangskoordinaten.

[mkinzler]

http://www.delphipraxis.net/internal...t.php?t=148748

[Delphi-Narr]

Da blick ich nicht so ganz durch...
Da diese Kreise unvorhersehbar auch nicht-integer Radien haben, klappt das doch nicht, oder?

[Wolfgang Mix]

Wir haben

- U = 2 * r * pi

- A = r * r * pi

- r2 = Sqrt(x * x + y * y)

- r = Shapebreite / 2

Alles, was kleiner als r ist (also r2), liegt im Kreis, also

Delphi-Quellcode:

If r2 < r then ImKreis.

Damit müßte sich doch 'was machen lassen!

Gruß

Wolfgang

[Medium]

Warum antworte ich eigentlich wenn es doch keinen interessiert? :roll:

[Wolfgang Mix]

Dann bin ich wohl der Einzige :mrgreen:

Gruß

Wolfgang

PS: Das sind ja nur Denkanstöße, man sollte es von möglichst vielen
Seiten angehen können

[schöni]

Zitat:

Zitat von Delphi-Narr

Da blick ich nicht so ganz durch...
Da diese Kreise unvorhersehbar auch nicht-integer Radien haben, klappt das doch nicht, oder?

Warum müssen denn das unbedingt nur die Integer Koordinaten sein. Was willst Du denn überhaupt damit machen?

[Delphi-Narr]

Diese Shapes stellen Löcher dar, wenn jetzt also der Mittelpunkt eines anderen Shapes im Lochshape ist, dann fällt das zweite Shape rein...
Da ich das nur ungefähr brauche und mit Left+width div 2 bzw. Top+height div 2 arbeiten will, wäre der Rest überflüssig und nich verwertbar...

Ich probier mal die Methode von Wolfgang, müsste eigentlich ja klappen.
Du meinst aber doch bestimmt

Delphi-Quellcode:

r,
r2:integer;

r:=Loch.width div 2;
r2:=round(sqrt(sqr(xWert_PunktA-xWert_Mittelpunkt_Loch)+sqr(yWert_PunktA-yWert_Mittelpunkt_Loch)));

oder habe ich da wieder was falsch verstanden?

[Medium]

Genau davon reden wir hier alle seit spätestens Beitrag 7, und nicht mehr ;)

Bzw. hattest du ja nach allen Punkten im Kreis gefragt, woraufhin richtigerweise Prüfen aller Pixel im Quadrat um den Kreis vorgeschlagen war, bzw. eine Schleife für den Kreisrand davor. Bis jetzt grad eben war uns vorenthalten, dass du eigentlich nur einen einzigen Punkt erfragen möchtest, und daher natürlich auch um nichts eine Schleife basteln musst. Die liebe Kunst des Fragenstellens...

[Delphi-Narr]

Oh, tut mir Leid...
Es würde jedoch auch mit allen Punkten im Kreis gehen, wenn ich prüfe, ob der Punkt A in der Liste der Punkte innerhalb des Kreises ist... So hatte ich mir das am Anfang vorgestellt. Also wenn ich missverstanden worden bin, tuts mir Leid.
Danke für die Hilfe!

[mkinzler]

Es ist aber einfacher zu prüfen, ob der Punkt innerhalb Kreis liegt als ihn mit allen Punkten im Kreis zu vergleichen

[Delphi-Narr]

Ja, das ist mir nur nicht so klar gewesen, als ich den Beitrag geschrieben habe...

[Delphi-Laie]

Zitat:

Zitat von Medium

Dann hättest du anders fragen müssen, weil die Punkte im Kreis gehören nicht zum Kreis!

Der Kreis ist eine Fläche, also gehören auch die Punkte darin dazu. Was Sie meinen, ist die Kreislinie. Fälschlicherweise wird aber auch letzteres oft vereinfacht als Kreis bezeichnet.

[Medium]

[equote="Wikipedia sagt im ersten Absatz im Artikel 'Kreis' dazu:"]
Ein Kreis ist definiert als Menge [...] aller Punkte der euklidischen Ebene, deren Abstand von einem vorgegebenen Punkt M gleich einer festen positiven reellen Zahl r ist. Diese Definition entspricht dem Zeichnen eines Kreises mit dem Zirkel.

(Edit: Weiter unten heisst es dann noch)
Nach der gegebenen Definition ist ein Kreis eine Kurve, also ein eindimensionales Gebilde, und keine zweidimensionale Fläche. Da das Wort „Kreis“ aber oft ungenau für die eingeschlossene Fläche benutzt wird, verwendet man zur Verdeutlichung häufig die Begriffe Kreislinie oder Kreisrand anstatt Kreis – im Gegensatz zur Kreisfläche oder (geschlossenen) Kreisscheibe. Diese ist definiert als die Menge aller Punkte der Ebene, deren Abstand von M höchstens r ist. Das Innere dieser Fläche bezeichnet man als offene Kreisscheibe. Ihre Punkte haben von M einen Abstand kleiner als r.
[/equote]
So hab ich es auch gelernt, und bei meinen paar Jährchen grafischer Programmierung nie anders definiert gesehen. Man spricht ja auch von "Punkten im Kreis", statt von "Punkten auf dem Kreis" wenn von Punkten der Kreisfläche die Rede ist. (Bei Punkten auf dem Perimeter wird man die erste Variante weit häufiger antreffen.)

Wir sind hier übrigens alle Kumpels: "Du" statt "Sie" hat sich eingebürgert ;)

[Delphi-Laie]

Nun, ich lernte es anders, bestehe aber bei dieser letztlich Sopihisterei nicht darauf, daß meine Begrifflichkeiten korrekt sind. Letztlich sollte man, um Unklarheiten zu beseitigen und als Kompromißvorschlag, vielleicht generell von Kreisfläche und Kreislinie sprechen. Aber eine kleine Analogie erlaube ich mir dennoch zu strapazieren: Was ist z.B. ein Rechteck: Eine Umrandung (einer Fläche) oder diese Fläche selbst inkl. Randlinie(n)? :wink: In jeder mir bekannten Formelsammlung findet man Formeln/Gleichungen für den Flächeninhalt z.B. des Kreises oder Rechteckes, nie jedoch für die von den gleichnamigen Linien eingeschlossenen Flächen.

Die Wikipediaargumentation ist in einer Beziehung Unfug: Der Kreis - wenn man ihn denn als zweidimensionales Gebilde, also als Fläche annimmt - ist mitnichten die von der Kreisfläche eingeschlossene Punktmenge, sondern seine Punktmenge besteht aus dieser Punktmenge und der (Punktmenge der) Kreislinie.

Zitat:

Zitat von Medium

Man spricht ja auch von "Punkten im Kreis", statt von "Punkten auf dem Kreis" wenn von Punkten der Kreisfläche die Rede ist. (Bei Punkten auf dem Perimeter wird man die erste Variante weit häufiger antreffen.)

Für was soll das ein Argument sein?

Punkte können bei einer Fläche, die aus Sicht des Betrachters die Dimension null, also fehlende Dicke hat, nie (dar)"auf" liegen, völlig richtig. Im Kreis ist damit richtig. Innerhalb der Kreislinie schon nicht mehr, weil man damit die Punkte der Kreislinie ausschließt.

[Medium]

Ob nun die Kreislinie bei der Berechnung der Fläche dazu zählt oder nicht ist garnicht von Belang, da ihr Beitrag ohnehin =0 wäre. Die "Frage" an sich macht wenn überhaupt nur in diskretisierten Fällen Sinn. Die Korrektheit der Begrifflichkeiten... naja, ich hab das nicht angefangen ;) (Bin aber ein großer Freund möglichst präziser Ausdrucksweise, grad wenn es um Mathe und Programmieren geht, den Schuh zieh ich mir gern an.)

Ein Rechteck (an und für sich) ist im Übrigen genauso nur der Rand der Fläche die seine Kanten umschließen (also die Kanten selbst). Und dass es Formeln gibt, um die vom Rand eingeschlossene Fläche zu errechnen, ist noch lange kein Indiz dafür dass diese durch das Objekt unmittelbar beschrieben ist. Oder ist dein Garten auch eigentlich dein Zaun? (Oder die Grundfläche des Zaunes wenn du das lieber magst. (Ich bin mir fast sicher, dass da wieder einer einen Weg finden wird die Analogie zu behacken :D))

Mit dem "darauf" und "darin" wollte ich nur darauf hinaus, dass sogar in der intuitiven Alltagssprache die Unterscheidung richtig gemacht wird. Dazu braucht man auch keine 3. Dimension, da man bei Gleichheit nicht selten von "auf" (dem Wert, der Linie etc.) spricht, wenn ein Punkt Teil der betreffenden Menge ist. Dagegen spricht man von "in", wenn sich etwas innerhalb von Begrenzungen befindet. (Zugegeben, bei "Menge" wird "in" benutzt, vermutlich weil es hier anschaulicher ist.) Ich will das nicht unbedingt tiefer diskutieren (hätte aber auch keine Angst davor), da es nur der Versuch einer intuitiven sprachlichen Brücke war.

Was ich letztlich nur wollte: Die falsche Korrektur korrigieren, damit potentielle Leser des Threads sich nicht evtl. auch die nicht zutreffende Definition aneignen.

[Wolfgang Mix]

Da wir gerade bei Begriffsbestimmungen sind:
Was sind

Zitat:

alle Integerkoordinaten eines Kreises

[Delphi-Laie]

Medium, das ist auch (und gerade?) eine Frage der Exaktheit der Aussage(n) über eine bzw. mehrere Punktmengen. Der Flächeninhalt ändert sich nicht, wenn man die Begrenzungslinie subtrahiert (Mengesubtraktion), das Gebilde ist dennoch nicht mehr vollständig, so ist z.B. der Durchmesser infinitesimal geringer - ja, ja, als Grenzwertbetrachtung bleibt er natürlich gleich.

Zitat:

Zitat von Medium

Oder ist dein Garten auch eigentlich dein Zaun? (Oder die Grundfläche des Zaunes wenn du das lieber magst. (Ich bin mir fast sicher, dass da wieder einer einen Weg finden wird die Analogie zu behacken :D))

Ei gewiß! Zaun + Garten = Grunstück! Bauen Sie doch mal den Zaun gleich neben Ihrem Grundstück, damit aber eindeutig außerhalb Ihres Grundstückes!

Oder allgemeiner: Die Grenzen gehören ganz einfach mit dazu und sind nicht darum. Ein wenig, aber nicht allzusehr vom Thema abgewichen: begin und end (so wie auch repeat until u.ä.) gehören für mich zum Block mit dazu, und deshalb bin ich allergisch gegen das (zugegebenermaßen ziemlich weit verbreitete) Einrücken der Codezeilen innerhalb solcher Begrenzungen. Sogar in den neueren Delphi-Compilern scheint sich diese (m.E. Un-)Sitte eingebürgert zu haben. Alles Geschmackssache, in meinen Augen erschwert es aber die Lesbarkeit ein Quentchen, objektiv bläht es die Größe der Quellcodedateien unnötig ein wenig auf.

[Wolfgang Mix]

Da wir gerade bei Begriffsbestimmungen sind:
Was sind eigentlich

Zitat:

alle Integerkoordinaten eines Kreises

:?: :?: :?:

[Medium]

Ich "darf" meinen Zaun aber nur auf meinem Grundstück bauen :D. Nein, Witz beiseite - jetzt wird's zwar schon nahezu philosophisch, aber gut. Die Fläche wird unendlich gering kleiner, das kann man so stehen lassen ja. Die Frage ist dann nur: Wen juckt's? Also effektiv! Weil der Wert den ich nachher hinschreibe, der ist der selbe. Ob er nun aus einem Grenzwertprozess stammt, oder einer expliziten Formel macht im "Alltag" keinen Unterschied. Es mag vielleicht 1-3 Konstrukte oder Beweise geben bei denen das eine Rolle spielt, dann aber auch nur der Prozess, nicht der Wert.

Jetzt darf ich aber auch mal: Codeblockbegrenzer haben nicht die "Masse" 0, weshalb es da einen effektiven Unterschied macht ob ich's dazu nehme oder nicht. Die Anzahl gebrauchter Zeilen (bzw. Tokens) ändert sich ja - anders als bei einer geometrischen Figur die Fläche. Token sind schließlich auch quasi "diskret" (oder genauer: Die Menge der Tokens ist abzählbar (und endlich, macht hier aber nix)).

Zur Einrückung sag ich lieber nichts, da sind wir wohl auch sehr extrem unterschiedlicher Meinung, aber das gehört hier nun endgültig nicht mehr hin :)

Fakt ist und bleibt: Gerade, Kreis, Rechteck, Ellipse, Polygon, etc. sind "Kurven" (nicht alle stetig und differenzierbar, klar), und haben als solche nur eine Länge, die Figuren an sich beschreiben keine Fläche. Ob und wie man dann die eingeschlossene Fläche interpretiert, hat damit primär nichts zu tun. Die kann ja gerne auch den Perimeter beinhalten - dieser bleibt davon ja erstmal unberührt, solang man ihn nicht umdefiniert. Im R³ z.B. schiebt sich das alles dann eine Dimension hoch: Kugeln haben kein Volumen, sie haben eine (Ober-)Fläche. Aber innerhalb dieser befindet sich ein definiertes Volumen dass ich berechnen kann. Und wenn man sich die allgemeine Definition einer Kugelformel mal anschaut, unterstützt sie das genau so wie die Kreisformeln. Beide bedingen "Abstand = r", nicht etwa "Abstand <= r" (was ja auch keine Gleichung mehr wäre). Da kannst du glauben und philosophieren was du magst, das ist heutzutage der Konsens in der Geometrie, und somit so lange als "Wahrheit" zu behandeln bis jemand einen geprüften und anerkannten Gegenbeweis aufstellt. So und nicht anders läuft das in Naturwissenschaften nun mal.


(Tut mir leid wenn ich hier jetzt im Thread so klugscheisserig rüber komme, aber das kann man echt so nicht stehen lassen sonst. :cheers:)

Achso! Wolfgang zeigt so schnippsend auf :) "Integerkoordinaten eines Kreises" ist eigentlich Käse, ja. Im Zusammenhang war's hier aber zumindest sehr gut vermutbar was gemeint ist. ("Integerkoordinaten" für sich genommen ist aber okay, es sind halt ganzzahlige Koordinaten auf Denglisch.)

[Delphi-Narr]

Alle Integerkoordinaten eines Kreises sind
nach einer Fassung nach alle Integerkoordinaten, die auf der Kreislinie liegen oder
nach der zweiten Fassung alle Integerkoordinaten der Kreisfläche und der Kreislinie zusammen.

Integerkoordianten selbst sind entweder gerundete Realkoordinaten oder nur ein Teil alle Punkte im Kreis.
Bei Delphi ist die zweite Methode wohl besser, da sonst eine unendliche Schleife durchlaufen wird, da jedes Gebilde unendlich viele Punkte umfasst.

Ich meinte in meiner Formulierung die Kreisfläche und die Kreislinie, diese war jedoch nicht zwingend für mich, da ich nur ungefähre Werte brauchte...

[Wolfgang Mix]

Ich veruche, das 'mal meiner Frau zu erklären, vielleicht
versteht die das, die denkt da praktischer als ich :)

[Edit] Der Umfang im Einheitskreis ist ungefähr 6,28 (real), der Durchmesser 2
oder eine Anzahl von Pixeln (Integer), und was definierst Dü?
Erstes macht nicht viel Sinn, weil zu weinig Integerwerte (0 .. 6) [/Edit]

[Delphi-Narr]

Ja, das wären dann nur 6 Werte... Ich brauch das aber nur ungefähr. Das andere Shape hat ja keine Koordinaten von 14,243632 sondern nur Integerkoordinaten. Und die will ich ja vergleichen.

[Wolfgang Mix]

Vielleicht erklärt mir das einer von meinen Kumpels hier,
die das verstanden haben

[turboPASCAL]

Man möge es mir verzeihen, aber ich blicke nicht so recht durch was der TE nun
versuchen möchte.

Vill. wäre es besser wenn er uns erklären würde was er überhaupt beabsichtigt zu tun,
bzw. was er damit anstellen möchte.

Eine Kollisionsabfrage ?

:gruebel:

[Medium]

Er möchte wissen, ob sich der Mittelpunkt eines Kreises innerhalb eines zweiten Kreises befindet. Da er es nicht hochgradig genau braucht, genügt ihm die Arbeit mit ganzzahligen Näherungen für alle beteiligten Werte. Ich vermute ganz stark, dass es um das Versenken von Billardkugeln in Taschen geht, weil so eine Kugel eben genau dann fällt wenn ihr Kontaktpunkt mit dem Tisch (der üblicherweise von oben gesehen in der Mitte liegt) über ein Loch gerät :glaskugel:
(Normalerweise bin ich doch der, der nach präziser gestellten Fragen fragt... Muss an Weihnachten liegen :))

[Wolfgang Mix]

Ich frage 'mal meine Glaskugel :)

[Delphi-Narr]

Nein, um Billard gehts nicht, sondern um Labyrinth. Habs mal hochgeladen, ist die neuere Version als im entsprechenden Thread. Bisher waren die augenscheinlich runden Löcher als Quadrate im Programm gespeichert, sodass ich das nur durch Verschiebung der Shapes einigermaßen ausgleichen konnte, jetzt kann ich das auch genauer machen. Ich habs mal hochgeladen, ist noch mit "rechteckigen" Löchern, klappt aber auch einigermaßen.
Ordnersystem muss beibehalten werden!

Anleitung für den Editor:

Öffnen
Startpunkt durch klicken auswählen
Zielpunkt durch Klicken auswählen
info: Balkenmodus ist aktiviert worden
Durch Ziehen kann man Balken plazieren - Wichtig: Man muss IMMER OBEN LINKS anfangen, da sonst negative Integerwerte entstehen...
Mausrad nach oben drehen aktiviert den Lochmodus
Löcher ebenso wie die Balken plazieren. Für Standardlöcher nur Klicken
Mausrad nach unten drehen aktiviert wieder den Balkenmodus
Unten links steht der aktivierte Modus
In das Editfeld unten einen Namen für die Map eingeben, zum speichern auf das Editfeld einen Doppelklick

Achtung: Der Editor 3 enthält noch keine Ladefunktion, Maps können nach Schließen des Programmes nicht mehr geändert werden.

Spiel:
Map auswählen
Einmal auf das Spiel klicken
Pfeiltasten für die Richtung, funktioniert mit Gegensteuern
Esc zum beenden

[Delphi-Narr]

Hm, da fällt mir noch was ein.
Wenn ich jetzt eine Ladenfunktion hinzufügen will, dann gibts ein Problem: Ich möchte alle zur Laufzeit erstellten Komponenten wieder löschen... wie kann ich das machen?