Punkt in der Schnittmenge dreier Kreise

[Blitzschutz1]

Benötige mal wieder einen (oder auch mehrere) Denkanstöße: Wie kann man die Bildpunkte ermitteln, die in den Schnittmengen dreier Kreise
(für die additive RGB-Farbmischung) enthalten sind?
Wer es sich mal ansehen will, was ich meine http://www.spectrumcolors.de/cor_rgb_demo.php

Danke!

[Michael II]

Falls du genau das nachbilden willst, was ich auf der von dir verlinkten Seite sehe, dann kannst du die drei Kreise zeichnen und danach mit floodfill die gemeinsame Schnittmenge ausmalen. Ein floodfill Beispiel findest du hier. Du benötigst dazu nur einen Punkt P in der gemeinsamen Schnittmenge der drei Kreise K1,K2,K3. Ein solcher lässt sich natürlich leicht ermitteln. P = 1/3(M1+M2+M3), wobei Mi die Mittelpunkte der Kreise Ki.

[Uwe Raabe]

Mathematisch sind die Punkte dadurch beschrieben, dass die drei Abstände zu den Kreismittelpunkten alle kleiner gleich dem Radius sind. Damit kannst du also feststellen, ob ein Punkt P(X,Y) in diesem Bereich liegt.

[Andreas13]

Hallo Blitzschutz1,
Du brauchst zuerst eine Routine, welche die möglichen Schnittpunkte zweier Kreise bestimmt: Möglich sind 0, 1 oder 2 als Lösung eines Gleichungssystems aus zwei quadratischen Gleichungen:

Code:

(x - x_M1)^2 + (y - y_M1)^2 = R1^2    und    (x - x_M2)^2 + (y - y_M2)^2 = R2^2'

(x_M1, y_M1) und (x_M2, y_M2) sind die Koordinaten der beiden Kreismittelpunkte.
[Edit]: R1 und R2 sind die Radien der beiden Kreise.

Das wiederholst Du 3-mal für alle 3 Kombinationen von Kreispaaren:
K1-K2, K1-K3, K2-K3. Damit kannst Du bis zu 6 Schnittpunkte haben, von denen die richteigen 3 ausgewählt werden müssen.

Die "richtigen" Eckpunkte der möglichen Schnittmenge erfüllen folgende Bedingung:
Der Eckpunkt liegt am Umfang zweier Kreise und innerhalb eines der drei Kreise.

Also brauchst Du noch zwei weitere Routinen um festzustellen, ob ein Punkt am Umfang eines (oder zweier) Kreises liegt, und eine zur Feststellung, ob ein Punkt innerhalb eines Kreises liegt.

Hier muß Du unbedingt aufpassen, daß Du bei Gleitkommazahlen immer einen unscharfen Vergleich mit etwa SameValue(..) machst, sonst funken die immer vorhandenen Rundungsfehler dazwischen und kommt nichts Brauchbares raus.

Viel Erfolg!
Gruß, Andreas

[Andreas13]

Zitat:

Also brauchst Du noch zwei weitere Routinen um festzustellen, ob ein Punkt am Umfang eines (oder zweier) Kreises liegt, ...

Diese zweite Routine kannst Du Dir auch sparen, denn die Schnittpunkte zweier Kreise erfüllen diese Forderung ja immer...
Andreas :oops:

[Uwe Raabe]

Das ganze wird in diesem Fall vermutlich noch einfacher, da zum einen die Mittelpunkte alle untereinander denselben Abstand A haben und die Radien R der drei Kreise alle gleich sind. Weiterhin gilt A < R, da es sonst keine Überschneidungen geben würde.

[Blitzschutz1]

Erstmal danke für alle Hinweise!

Mal sehen, ob ich es hinbekomme. Wobei mir das flootfill natürlich am besten gefallen will (weil es so schön einfach zu realisieren scheint).

Aber auch die anderen Lösungen werde ich mir ansehen. Schon umwas dabei zu lernen...

[Michael II]

Zitat:

Zitat von Uwe Raabe (Beitrag 1490848)

Das ganze wird in diesem Fall vermutlich noch einfacher, da zum einen die Mittelpunkte alle untereinander denselben Abstand A haben und die Radien R der drei Kreise alle gleich sind. Weiterhin gilt A < R, da es sonst keine Überschneidungen geben würde.

Nicht ganz:
Sei r der Radius der drei Kreise. Wenn die drei Kreismittelpunkte Eckpunkte eines gleichseitigen Dreiecks mit Seitenlänge a sind, dann haben je zwei Kreise eine gemeinsame Schnittmenge, wenn a<=2*r (bei Gleichheit genau einen Punkt).
Damit alle drei Kreise gemeinsame Punkte haben, muss a<=sqrt(3)*r gelten. (Überlegung: Die drei Kreise haben dann genau einen gemeinsamen Schnittpunkt, wenn sie sich im Schwerpunkt S des Dreiecks treffen. Wir wissen: Der Schwerpunkt S teilt die Seitenhalbierende (und hier gleichzeitig Höhenlinie) des Dreiecks im Verhältnis 2:1. => Die Höhe des Dreiecks beträgt also 1.5*r => Die Seitenlänge a damit r*sqrt(3). => Wenn a < r*sqrt(3) wird aus dem Schnittpunkt eine Schnittfläche.)

[DeddyH]

Wenn man für aus jedem Kreismittelpunkt und dem zu untersuchenden Punkt ein rechtwinkliges Dreieck bildet, so befindet sich der Punkt dann in der Schnittmenge der 3 Kreise, wenn jede der errechneten Hypotenusen kleiner als der Kreisradius ist, oder mache ich da einen Denkfehler?

[Uwe Raabe]

Zitat:

Zitat von DeddyH (Beitrag 1490895)

oder mache ich da einen Denkfehler?

Nein, machst du nicht. Das deckt sich inhaltlich mit dem unter #3 gesagten.

[DeddyH]

Sry, den Beitrag hatte ich wohl übersehen :oops:

[Michael II]

Ja #3 und #9 schreiben über das gleiche Ding.
Der Kreis k mit Mittelpunkt M=(mx,my) und Radius r hat die Gleichung (x-mx)^2 + (y-my)^2 = r^2. Alle Punkte (x,y) innerhalb von k erfüllen (x-mx)^2 + (y-my)^2 < r^2.

Wenn man prüfen will, ob ein Punkt (x,y) in der gemeinsamen Schnittfläche aller Kreise liegt muss man nur prüfen, ob die drei Ungleichungen für die drei Kreise erfüllt sind.


Alternativ zu Abstandsmessung/Kreisgleichung: Man kann hier auch mit Regionen arbeiten. Dann muss man nix rechnen, wenn man wissen will, ob ein Punkt (x,y) innerhalb einer Region liegt.

( Im Code unten findest du ein Beispiel für die Nutzung von floodfill" fürs grüne Ausmalen der gemeinsamen Schnittmenge. )

Mit CreateEllipticRgn() kann man die Menge der Punkte der jeweiligen Kreise definieren. Mittels CombineRgn() wird die gemeinsame Schnittmenge (schnittmenge) ermittelt.

Wenn ein User an Position (x,y) aufs Formular klickt, wird mit if PtInRegion( schnittmenge, x, y ) geprüft, ob (x,y) in der gemeinsamen Schnittmenge (schnittmenge) liegt.

Anstatt floodfill aus der VCL fürs Ausmalen zu nutzen, kann man auch Regionen mit einer Farbe belegen. Dies geschieht unten im Code mittels:

Delphi-Quellcode:

    brush := CreateSolidBrush( $000000ff );
    FillRgn( higru.canvas.Handle, schnittmenge, brush );

Delphi-Quellcode:

var higru : TBitMap;
    schnittmenge : HRGN;
    m : array[1..3] of TPoint;


procedure zeichne;
var r, d : integer;
    ahrgn : array[1..3] of HRGN;
    i : integer;
begin
  r := trunc(higru.height/3+0.5);
  d := trunc(2*r*sqrt(3)/3+0.5);

  // Mittelpunkte der Kreise
  m[1] := Point(r,2*r);
  m[2] := Point(r+d,2*r);
  m[3] := Point(trunc(r+d/2+0.5),r);

  higru.Canvas.Brush.Style := bsClear;
  higru.Canvas.Pen.Color := clBlack;

  for i := 1 to 3 do
  higru.Canvas.Ellipse( m[i].X-r,m[i].Y-r,m[i].X+r, m[i].Y+r );

  higru.Canvas.Brush.Color := clgreen;
  higru.canvas.brush.Style := bsSolid;
  higru.Canvas.FloodFill( trunc((m[1].x+m[2].x+m[3].x)/3), trunc((m[1].y+m[2].y+m[3].y)/3), clBlack, fsBorder );

  // Schnittmenge der drei Kreise berechnen => Region "schnittmenge"
  // Die drei Kreise:
  for i := 1 to 3 do
  ahrgn[i] := CreateEllipticRgn( m[i].X-r,m[i].Y-r,m[i].X+r, m[i].Y+r );

  // Kreis1 mit Kreis2 schneiden und in schnittmenge abspeichern
  CombineRgn( schnittmenge, ahrgn[1], ahrgn[2], RGN_AND );
  // Kreis3 mit schnittmenge schneiden und in schnittmenge abspeichern
  CombineRgn( schnittmenge, schnittmenge, ahrgn[3], RGN_AND );

  for i := 1 to 3 do
    DeleteObject(ahrgn[i]);
end;

procedure TForm114.FormCreate(Sender: TObject);
begin
  higru.SetSize( 500, 400 );
  zeichne;
end;

procedure TForm114.FormMouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
  var brush : HBRUSH;
begin
  if PtInRegion( schnittmenge, x, y ) then
  begin
    brush := CreateSolidBrush( $000000ff );
    FillRgn( higru.canvas.Handle, schnittmenge, brush );
    showmessage ( 'Ich gehöre zu "schnittmenge"' );
    Repaint;
  end;
end;

procedure TForm114.FormPaint(Sender: TObject);
begin
    canvas.Draw( 0,0, higru );
end;

initialization
higru := TBitMap.Create;
schnittmenge := CreateRectRgn(0, 0, 0, 0);
finalization
DeleteObject( schnittmenge );
higru.free;
end.