# Berechnung aller im Kreis liegenden X/Y Koordinaten?



## Joe (2. Juni 2012)

Hallo alle,

ich überlege wie ich es hinbekomme alle Koords, innerhalb eines Kresies/Kreisauschnitt, aus einem X/Y Koordinatensystem zu bekommen.
Das Koordinatensystem fängt bei x1/y1 oden links an und endet bei x200/y200
Wobei ein Feld bei mir eine Grösse von 10px*10px hat.

Wie muss die Berechnung aussehen wenn ich alle Koordinaten von Mittelpunkt x100/y100 und einem Radius von 50Pixel (oder 5 Feldern) hätte?

Wie würde ich einen Kreisabschnitt berechnen? Als Beispiel nehme ich mal nen 25%schnitt (Gradzahl is egal oder besser flexibel).

Sprache wird php sein.

Ich hoffe mir kann jemand bei diesen mathematischen Problem weiterhelfen ich hab leider ungenügend schuliches Wissen wie das zu lösen ist.

Grüsse Joe.


----------



## Matthias Reitinger (3. Juni 2012)

Hallo,

die einfachste Methode wäre wohl, wenn du sämtliche Felder im kleinsten umschließenden Quadrat darauf testest, ob deren Mittelpunkt im Kreis liegt. Ein Punkt liegt in einem Kreis, wenn dessen Abstand vom Mittelpunkt betragsmäßig höchstens der Kreisradius ist. In Pseudocode:


```
mittelpunkt = (100, 100)
radius = 50
feldgröße = 10

box_min = (mittelpunkt.x - radius, mittelpunkt.y - radius) / feldgröße
box_max = (mittelpunkt.x + radius, mittelpunkt.y + radius) / feldgröße

for (x, y) from box_min to box_max do
    feld_mittelpunkt = (x + 0.5, y + 0.5) * feldgröße
    abstand = sqrt((mittelpunkt.x - feld_mittelpunkt.x)^2 + (mittelpunkt.y - feld_mittelpunkt.y)^2)
    if abstand <= radius then
        print "Feld ", (x, y), " ist im Kreis"
    end if
end for
```

Bei Kreisabschnitten müsste man noch zusätzliche Abfragen einbauen, weiß aber aus dem Kopf auch nicht genau welche.

Grüße,
Matthias


----------



## Joe (3. Juni 2012)

Super gelöst,

dachte erst ich müsste erst die ganzen Koords 1/1 - 200/200 durchrödeln.
So schnell wäre ich nicht auf diese Lösung gekommen.

```
$mittelpunkt=array();
$mittelpunkt['X'] = 100;
$mittelpunkt['Y'] = 100;
$radius = 5;
$feldgröße = 10;
$InBereich=array();
$k=0;
$box_min=array();
$box_max=array();
$box_min['X']=$mittelpunkt['X']-$radius;
$box_min['Y']=$mittelpunkt['Y']-$radius;
$box_max['X']=$mittelpunkt['X']+$radius;
$box_max['Y']=$mittelpunkt['Y']+$radius;
$feld_mittelpunkt=array();
for($x=$box_min['X']; $x<=$box_max['X']; $x++){
	for($y=$box_min['Y']; $y<=$box_max['Y']; $y++){
		$feld_mittelpunkt['X'] = $x*$feldgröße+0.5 ;
		$feld_mittelpunkt['Y'] = $y* $feldgröße + 0.5 ;
		$abstand = abs($mittelpunkt['X']* $feldgröße - $feld_mittelpunkt['X']) + abs($mittelpunkt['Y']* $feldgröße - $feld_mittelpunkt['Y']);
		if ($abstand <= $radius* $feldgröße) {
			$k++;
			echo "<p>Abstand: $abstand | Feld $x, $y ist im Kreis</p>";
		}
	}
}
echo "<p>$k</p>";
```


Den Kreisauschnitt schieb ich mal kurz zur Seite (wenn natürlich wem was einfällt).

Zuletzt bin ich noch bissel ratlos wenn ich die Koords aus einem unregelmässiges Dreieck holen wollte, wie dies umzusetzen ginge. Vermutlich der Satz des Pytagoras und der Ansatz ähnlich wie im obrigen Beispiel.?

Danke und Gruss Joe.


----------



## Matthias Reitinger (4. Juni 2012)

Hallo Joe,

zu solltest deine Übersetzung in PHP nochmal überprüfen, da stimmen einige Berechnungen nicht (z.B. die des Abstands).

Bei Dreiecken kannst du analog vorgehen. Die Bestimmung, ob ein Punkt im Dreieck liegt, ist dabei aber etwas komplizierter. Prinzipiell musst du für jede Kante des Dreiecks überprüfen, auf welcher „Seite“ der Punkt liegt. Die Seite ergibt sich durch das Vorzeichen, das beim Einsetzen des Punktes in die Normalform rauskommt. Liegt der Punkt bezüglich aller Kanten innen, so liegt der Punkt im Dreieck.

Grüße,
Matthias


----------



## Joe (4. Juni 2012)

Ok hier muss ich kapitulieren.
Musste grade schmerzlich feststellen das mein mathematisch logisches Verständnissvermögen eklatant unzureichend ist. Mir gelingt es nicht mal alle Punkte auf eine Linie zwischen 2 punkten zu berechnen. Obwohl ich denke das sollte sogar noch einen Laien gelingen... mir nicht so einfach :-(

Was den Kreis betrifft schau ich mir nochmal an es schien mir als kamen die richtigen Koordinaten raus. (Aus dem obrigen Beispiel mit dem gegebenen Raius waren es exakt 55 Koordinaten)

Wozu ich das eigentlich brauche:
Ich versuche ein Strahlungsfeld auf einer Karte darzustellen. Das Feld sollte variabel (Radius) und beweglich sein. Dabei aber nicht überlagern.. deswegen die genaue Berechnung aller betroffenen Felder.

Einen Kreis kann ich nun also wie gewünscht realisieren. Ursprünglich wollte ichs "etwas" komplexer machen: Mittelpunkt mit 3-6 Linien, jede Linie hat variable Länge, die Linienenden haben wiederum variable Kreise, Dann wollte ich einfach nen Halbkreis dazwischen setzen (zwecks der leichteren Berechnung wenn dieses Strahlendingens fluktuiert).



Aber da ich nun vor der Tatsache stehe das ich die Felder nicht mathematisch erfassen kann denke ich es wird ein Kreis tun.. realistisch hätte dieses Feldgebilde auch nicht gerade ausgesehen.
Wäre zwar schön wenn ich dem Kreis irgendwelche zufällig ausbrechenden Muster  mitgeben könnte aber dies würde man noch weniger berechnen können, und wäre nach einigen "Runden" der Fluktuation vermutlich eher grotesk verzerrt. Einzigst der Radius ist variabel.

Gut würde mich freuen falls ihr zur Problematik Ideen hättet.

Danke Matthias Reitinger.
Gruss Joe.


----------



## Joe (7. Juni 2012)

*Dreieck*

Nun irgendwie hat mich diese komplizierte Problemstellung nicht mehr losgelassen.
Es ist mir tatsächlich gelungen der Lösung sehr nahe zu kommen. Sehr nahe deshalb weil meine Schleife für den gesamten Flächeninhalt noch nicht alle Eventualitäten abfängt.
Würde mich freuen wenn ihr mir vieleicht nen Stück helfen könntet welche If-Abfragen ich noch eibauen muss das jedes Dreieck richtig vektorisiert werden kann.

Die Linien die für die Lösung unerlässlich waren, habe ich mit Hilfe der Linienrasterung nach dem Bresenham Algorythmus berechnet. (Eine Übersetzung eines Javascript-codes welchen ich im Netz fand, die 2 PHP-Versionen im Netz hab ich nicht zum laufen gebracht^^).


```
// 3 Koordinatenpunkte des Dreiecks
$data=array();
$data[0]['X']=4;
$data[0]['Y']=12;
$data[1]['X']=50;
$data[1]['Y']=50;
$data[2]['X']=35;
$data[2]['Y']=25;


// Sortieren der Punkte nach kleinsten XWert bis maximal X-Wert
$sortArray = array();
foreach($data as $key => $array) {
	$sortArray[$key] = $array[0];
}
array_multisort($sortArray, SORT_ASC, SORT_NUMERIC, $data);

//// Rasterung von Linien nach Bresenham-Algorithmus
// Für jede Seite des Dreiecks Arrays mit allen darauf liegenden Punkten berechnen/speichern
// Jede Seite ist eine Linie mit x Punkten
//// Rasterung von Linien nach Bresenham-Algorithmus

// Linie1
$x0=$data[0]['X'];
$y0=$data[0]['Y'];
$x1=$data[2]['X'];
$y1=$data[2]['Y'];
$dx = abs($x1 - $x0);
$sx = $x0 < $x1 ? 1 : -1;
$dy = abs($y1 - $y0);
$sy = $y0 < $y1 ? 1 : -1; 
$err = ($dx>$dy ? $dx : -$dy)/2;
while (true) {
    echo "<p>$x0/$y0</p>";
	$Line1['X'][]=$x0;
	$Line1['Y'][]=$y0;
    if ($x0 === $x1 && $y0 === $y1) break;
    $e2 = $err;
    if ($e2 > -$dx) { $err -= $dy; $x0 += $sx; }
    if ($e2 < $dy) { $err += $dx; $y0 += $sy; }
}
// Linie2
$x0==$data[1]['X'];
$y0=$data[1]['Y'];
$x1=$data[2]['X'];
$y1=$data[2]['Y'];
$dx = abs($x1 - $x0);
$sx = $x0 < $x1 ? 1 : -1;
$dy = abs($y1 - $y0);
$sy = $y0 < $y1 ? 1 : -1; 
$err = ($dx>$dy ? $dx : -$dy)/2;
while (true) {
    echo "<p>$x0/$y0</p>";
	$Line2['X'][]=$x0;
	$Line2['Y'][]=$y0;
    if ($x0 === $x1 && $y0 === $y1) break;
    $e2 = $err;
    if ($e2 > -$dx) { $err -= $dy; $x0 += $sx; }
    if ($e2 < $dy) { $err += $dx; $y0 += $sy; }
}
// Linie3
$x0=$data[0]['X'];
$y0=$data[0]['Y'];
$x1=$data[1]['X'];
$y1=$data[1]['Y'];
$dx = abs($x1 - $x0);
$sx = $x0 < $x1 ? 1 : -1;
$dy = abs($y1 - $y0);
$sy = $y0 < $y1 ? 1 : -1; 
$err = ($dx>$dy ? $dx : -$dy)/2;
while (true) {
    echo "<p>$x0/$y0</p>";
	$Line3['X'][]=$x0;
	$Line3['Y'][]=$y0;
    if ($x0 === $x1 && $y0 === $y1) break;
    $e2 = $err;
    if ($e2 > -$dx) { $err -= $dy; $x0 += $sx; }
    if ($e2 < $dy) { $err += $dx; $y0 += $sy; }
}
////
// Dreiecksfläche: Alle Koordinatenpaare innerhalb des Dreiecks
////
for($i=0; $i<count($Line1['X']); $i++){
	$k=0;
	// WENN Y-Wert von PunktX Y-Wert von PunktY übersteigt
	if (!isset($Line3['Y'][$i])) {
		if (!$YLine2Y) {
			foreach ($Line2['Y'] as $key => $value) {
			if ($key=='$x0') {
					$YLine2Y=$key;
				}
			}
		}
		$Limit=$Line1['Y'][$i]-$Line2['Y'][$YLine2Y];
	}
	else {
		$Limit=$Line1['Y'][$i]-$Line3['Y'][$i];
	}
	// WENN X-Wert von PunktX X-Wert von PunktY übersteigt
	if (!$Line1['X'][$i]) {
		if (!$YLine2X) {
			foreach ($Line2['X'] as $key => $value) {
				if ($key=='$x0') {
					$YLine2X=$key;
				}
			}
		}
		$l++;
	}
	for($j=0; $j<=$Limit; $j++){
		// WENN Y-Wert von PunktX Y-Wert von PunktY übersteigt
		if (!isset($Line3['Y'][$i])) {
			$y0=$Line2['Y'][$YLine2Y]+$k;
		}
		else {
			$y0=$Line3['Y'][$i]+$k;
		}
		// WENN X-Wert von PunktX X-Wert von PunktY übersteigt
		if (!$Line1['X'][$i]) {
			$x0=$Line2['X'][$YLine2X]+$l;
		}
		else {
			$x0=$Line1['X'][$i];
		}
		$Dreiecksfläche['X'][]=$x0;
		$Dreiecksfläche['Y'][]=$y0;
		//echo "<p>$x0/$y0</p>";
		$k++;
	}
}


// Optional: Dreicksfläche ausgeben
$count=count($Dreiecksfläche['X']);
for($i=0; $i<=count($Dreiecksfläche['X']); $i++){
	echo "<p>{$Dreiecksfläche['X'][$i]}/{$Dreiecksfläche['Y'][$i]}</p>";
}
```

Also wie angedeutet fehlen in der unteren Schleife zur Berechnung aller Verktoren noch ein paar IF-Abfragen (zb wenn Y-Wert von jenen Punkt grösser dann..). Die Linien hingegen funktionieren so wie gewünscht. 
Würde mich über eure Kommentare freuen.

Gruss Joe.


----------



## Joe (18. Juni 2012)

Ich denke ich konnte die Berechnung zur Dreiecksfläche perfektionieren.
Negative Werte im Kordinatenpaar habe ich nicht getestet könnten aber durchaus funktionieren.

Wenn jemand von euch meine Arbeit nutzen konnte würde ich mich über eine Bewertung und oder Kommentar freuen.


```
//// Testpunkte
// 3 Koordinatenpunkte des Dreiecks
$data=array();
$data[0]['X']=4;
$data[0]['Y']=12;
$data[1]['X']=50;
$data[1]['Y']=50;
$data[2]['X']=35;
$data[2]['Y']=25;
/*
// 3 Koordinatenpunkte des Dreiecks
$data=array();
$data[0]['X']=17;
$data[0]['Y']=28;
$data[1]['X']=3;
$data[1]['Y']=10;
$data[2]['X']=35;
$data[2]['Y']=15;*/

/*
// 3 Koordinatenpunkte des Dreiecks
$data=array();
$data[0]['X']=34;
$data[0]['Y']=76;
$data[1]['X']=53;
$data[1]['Y']=7;
$data[2]['X']=21;
$data[2]['Y']=95;*/


// Sortieren der Punkte nach kleinsten XWert bis maximal X-Wert
$sortArray = array();
foreach($data as $key => $array) {
	$sortArray[$key] = $array[0];
}
array_multisort($sortArray, SORT_ASC, SORT_NUMERIC, $data);
// Sortieren so das Punkt 3 grössten YWert stellt
foreach($data as $key => $array) {
	if ($key==1) {
		$array1=$array;
	}
	if ($key==2 AND $array1['Y']>$array['Y']) {
		$data[1]['X']=$array['X'];
		$data[1]['Y']=$array['Y'];
		$data[2]['X']=$array1['X'];
		$data[2]['Y']=$array1['Y'];
	}
}


//// Rasterung von Linien nach Bresenham-Algorithmus
// 		Für jede Seite des Dreiecks Arrays mit allen darauf liegenden Punkten berechnen/speichern
// 		Jede Seite ist eine Linie mit x Punkten
//// Rasterung von Linien nach Bresenham-Algorithmus

// Linie1 - Bresenham-Algorithmus | diese Linie stellt Preferenz und Rechnungsbezugslinie dar (Minimalster Punkt1 X-Wert zu Punkt3 maximaler Y-Wert)
// Die Schleife durchläuft zuerst die X-Achse und innerhalb dann die Y-Achse
$x0=$data[0]['X']; // Punkt mit kleinsten X-Wert
$y0=$data[0]['Y'];
$x1=$data[2]['X']; 
$y1=$data[2]['Y']; // Punkt mit grössten Y-Wert
$dx = abs($x1 - $x0);
$sx = $x0 < $x1 ? 1 : -1;
$dy = abs($y1 - $y0);
$sy = $y0 < $y1 ? 1 : -1; 
$err = ($dx>$dy ? $dx : -$dy)/2;
// echo "<p>Linie1</p>";
while (true) {
	// Optional: Linie ausgeben:
    // echo "<p>$x0/$y0</p>";
	$Line1['X'][]=$x0;
	$Line1['Y'][]=$y0;
    if ($x0 === $x1 && $y0 === $y1) break;
    $e2 = $err;
    if ($e2 > -$dx) { $err -= $dy; $x0 += $sx; }
    if ($e2 < $dy) { $err += $dx; $y0 += $sy; }
}
// Linie2 - Bresenham-Algorithmus
if ($data[1]['X']<$data[2]['X']) {
	$x0=$data[1]['X'];
	$y0=$data[1]['Y'];
	$x1=$data[2]['X'];
	$y1=$data[2]['Y'];
}
else {
	$x1=$data[1]['X'];
	$y1=$data[1]['Y'];
	$x0=$data[2]['X'];
	$y0=$data[2]['Y'];
}
$dx = abs($x1 - $x0);
$sx = $x0 < $x1 ? 1 : -1;
$dy = abs($y1 - $y0);
$sy = $y0 < $y1 ? 1 : -1; 
$err = ($dx>$dy ? $dx : -$dy)/2;
//echo "<p>Linie2</p>";
while (true) {
	// Optional: Linie ausgeben:
    //echo "<p>$x0/$y0</p>";
	$Line2['X'][]=$x0;
	$Line2['Y'][]=$y0;
    if ($x0 === $x1 && $y0 === $y1) break;
    $e2 = $err;
    if ($e2 > -$dx) { $err -= $dy; $x0 += $sx; }
    if ($e2 < $dy) { $err += $dx; $y0 += $sy; }
}
// Linie3 - Bresenham-Algorithmus
$x0=$data[0]['X'];
$y0=$data[0]['Y'];
$x1=$data[1]['X'];
$y1=$data[1]['Y'];
$dx = abs($x1 - $x0);
$sx = $x0 < $x1 ? 1 : -1;
$dy = abs($y1 - $y0);
$sy = $y0 < $y1 ? 1 : -1; 
$err = ($dx>$dy ? $dx : -$dy)/2;
// echo "<p>Linie3</p>";
while (true) {
	// Optional: Linie ausgeben:
    // echo "<p>$x0/$y0</p>";
	$Line3['X'][]=$x0;
	$Line3['Y'][]=$y0;
    if ($x0 === $x1 && $y0 === $y1) break;
    $e2 = $err;
    if ($e2 > -$dx) { $err -= $dy; $x0 += $sx; }
    if ($e2 < $dy) { $err += $dx; $y0 += $sy; }
}
// Maximal X-Wert ermitteln für SchleifenENDE
// Die Schleife durchläuft zuerst die X-Achse und innerhalb dann die Y-Achse
$Xmaximum=max($data[0]['X'],$data[1]['X'],$data[2]['X']);
$Xminimum=min($data[0]['X'],$data[1]['X'],$data[2]['X']);

///////////////
// Dreiecksfläche: Alle Koordinatenpaare innerhalb des Dreiecks in Array $Dreiecksfläche speichern
///////////////

// Schleife durchläuft X-Achse bis  $Xmaximum Dies ist immer der maximale X-Achsenwert durch obrige Sortierung
for($x=$Xminimum; $x<=$Xmaximum; $x++){
	
	// YAchse-Yminimuma und YAchse-Ende festlegen
	
	// Solange Linie3 und Linie1 auf der X-Achse liegen
	if (end($Line3['X'])>=$x AND end($Line1['X'])>=$x) {
		$Keys=array_keys($Line3['X'], $x);
		$Key=end($Keys);
		$Yminimum=$Line3['Y'][$Key];
		$Keys=array_keys($Line1['X'], $x);
		$Key=$Keys[0];
		$Ymaximum=$Line1['Y'][$Key];
	}
	
	// WENN Grundlinie(Linie3) kürzer als Oberlinie(Linie1)
	if (end($Line3['X'])<$x) {
	//if (!isset($Line3['Y'][$x-$Xminimum])) {
		$Keys=array_keys($Line2['X'], $x);
		$Key=$Keys[0];
		$Yminimum=$Line2['Y'][$Key];
		$Keys=array_keys($Line1['X'], $x);
		$Key=end($Keys);
		$Ymaximum=$Line1['Y'][$Key];
	}
	// WENN Grundlinie länger als Oberlinie
	if (end($Line1['X'])<$x) {
		$Keys=array_keys($Line2['X'], $x);
		$Key=$Keys[0];
		$Ymaximum=$Line2['Y'][$Key];
		$Keys=array_keys($Line3['X'], $x);
		$Key=end($Keys);
		$Yminimum=$Line3['Y'][$Key];
	}
	
	// Schleife Y-Achse
	for($y=$Yminimum; $y<=$Ymaximum; $y++){		
		$Dreiecksfläche['X'][]=$x;
		$Dreiecksfläche['Y'][]=$y;
		
		// Optional: Dreiecksfläche ausgeben:
		// echo "<p>$x/$y</p>";
		
	}
	
	// Trenn-Linie (Debugging)
	// echo "<p>Next Line $x</p>";
}


//// Dreiecksfläche zeichnen (PHP GD-Lib)

// Linien-Legende
echo "<p>rot = Linie 1</p>";
echo "<p>grün = Linie 2</p>";
echo "<p>blau = Linie 3</p>";
$Zooming=15;  // Zoomfaktor - zeigt die Linien genauer (Debugging)
$BILD = imageCreate(100*$Zooming,100*$Zooming);     // Bild erstellt, Bild absolut leer 
imageColorAllocate($BILD,0,0,0);     // erstes Allocate -> der Hintergrund des Bildes wird Schwarz sein 

// Linie 1 zeichnen
$rot = imageColorAllocate($BILD,255,0,0);
for($i=0; $i<=count($Line1['X']); $i++){
	//echo "<p>{$Line1['X'][$i]},{$Line1['Y'][$i]}</p>";
	if ($Line1['X'][$i+1] AND $Line1['Y'][$i+1]) {
		imageLine($BILD,$Line1['X'][$i]*$Zooming,$Line1['Y'][$i]*$Zooming,$Line1['X'][$i+1]*$Zooming,$Line1['Y'][$i+1]*$Zooming,$rot);
	}
}
// Linie 2 zeichnen
$grün = imageColorAllocate($BILD,0,255,0);
for($i=0; $i<=count($Line2['X']); $i++){
	//echo "<p>{$Line2['X'][$i]},{$Line2['Y'][$i]}</p>";
	if ($Line2['X'][$i+1] AND $Line2['Y'][$i+1]) {
		imageLine($BILD,$Line2['X'][$i]*$Zooming,$Line2['Y'][$i]*$Zooming,$Line2['X'][$i+1]*$Zooming,$Line2['Y'][$i+1]*$Zooming,$grün);
	}
}
// Linie 3 zeichnen
$blau = imageColorAllocate($BILD,0,0,255);
for($i=0; $i<=count($Line3['X']); $i++){
	//echo "<p>{$Line3['X'][$i]},{$Line3['Y'][$i]}</p>";
	if ($Line3['X'][$i+1] AND $Line3['Y'][$i+1]) {
		imageLine($BILD,$Line3['X'][$i]*$Zooming,$Line3['Y'][$i]*$Zooming,$Line3['X'][$i+1]*$Zooming,$Line3['Y'][$i+1]*$Zooming,$blau);
	}
}
// Dreiecksfläche
$gelb = imageColorAllocate($BILD,255,255,0);     // rot: 255, grün: 255, blau: 0 --> gelb, siehe Farbenlehre
for($i=0; $i<=count($Dreiecksfläche['X']); $i++){
	//echo "<p>{$Dreiecksfläche['X'][$i]}/{$Dreiecksfläche['Y'][$i]}</p>";
	// Schräge Linien aussparen in der If-Bedingung: AND $Dreiecksfläche['X'][$i]==$Dreiecksfläche['X'][$i+1]
	if ($Dreiecksfläche['X'][$i+1] AND $Dreiecksfläche['Y'][$i+1] AND $Dreiecksfläche['X'][$i]==$Dreiecksfläche['X'][$i+1]) {
		imageLine($BILD,$Dreiecksfläche['X'][$i]*$Zooming,$Dreiecksfläche['Y'][$i]*$Zooming,$Dreiecksfläche['X'][$i+1]*$Zooming,$Dreiecksfläche['Y'][$i+1]*$Zooming,$gelb);
		// Optional: Dreiecksfläche ausgeben:
		//echo "<p>{$Dreiecksfläche['X'][$i+1]}/{$Dreiecksfläche['Y'][$i+1]}</p>";
	}
}

// Bild speichern
imageJPEG($BILD,"img/triangle.jpg",100);
// Bild ausgeben
echo "<img src=\"img/triangle.jpg\">";
```

Grüsse Joe.


----------



## ikosaeder (18. Juni 2012)

Für den Kreisausschnnitt musst du zuerst prüfen, ob der Punkt im Kreis liegt und dann den Winkel zwischen den beiden Rändern so wie den Winkel zwischen dem Vektor M->P und einem Rand bestimmen. http://www.mathe-online.at/materialien/Andreas.Pester/files/Vectors/winkel_zwischen_vektoren.htm Ist der Winkel mit M->P kleiner liegt der Punkt im Kreisausschnitt. (Vorzeichen beachten)

Für das Dreieck wird hier http://www.zum.de/Foren/mathematik/archiv/a24.html eine Lösung vorgeschlagen.

Ich glaube, das es einfacher ist, in einer Schleife alle Koords zu prüfen, als sich für jeden Fall zu überlegen wie die Vereinfachung aussieht. Bei 200 Koordinaten sollten das kein Problem sein.


----------



## Joe (18. Juni 2012)

@ikosaeder hast du den Post über dir überlesen oder ignoriert?
Es ist mir bereits klar das es um Vektorechnung bzw Algebra geht.
Die Lösung zum Kreis ist weiter oben beschrieben wurden und *meine Lösung zum Dreieck* in PHP habe ich im gesamten Netz nirgends gesehen.

Der Punkt ist aber *ich habe bereits die Lösung* in PHP ausformuliert 
Intressant wäre jetzt noch der Halbkreis daher habe ich das Thema noch offengelassen (noch nicht als erledigt markiert). Der ist ansich nicht mehr das Problem, werde die Lösung ohne Winkel dann hier noch später aufzeigen.


----------



## ikosaeder (18. Juni 2012)

Ich habe den Beitrag schon gelesen, aber vielleicht nicht richtig verstanden. 
Mein Ansatz für den Kreisausschnitt lässt sich auch auf den Halbkreis übertragen, ich sehe aus deinen Beiträgen nicht, wie der Halbkreis bei dir definiert ist (Mittelpunkt, Radius, Winkel und ein Eckpunkt?).


----------



## Joe (18. Juni 2012)

Die Halbkreise ergeben sich aus den Schnittpunkten der Kreise (s. Zeichnung). Die Linie dazwischen halbiert den Kreis. Ich habe also 2 Schnittpunkte und der Durchmesser/Radius ergibt sich aus diesen beiden Punkten. (Der Winkel wäre also 180° aber ich denke die Berechnung damit wäre noch komplizierter)
Dieser Halbkreis soll dann aus den vorher berechneten Dreieck rausgerechnet werden.

Mit Array_merge führe ich dann alle Koordinaten zusammen und habe dann die gesamte Fläche diesen Gebildes. Das Gebilde wird sich in zeitlichen Intervallen bewegen und dabei an Kreisradius Linienlänge und Kreismittelpunkt variieren. Auch sollen 2 Geblilde sich nicht überlagern und abgebildet werden auf der Karte (färben der betroffenen Koords). Das ist der Grund warum ich die betroffenen Koordinaten berechnen will. Auch wenn das grad etwas OffTopic geworden ist.


----------

