Prüfen, ob Punkt innerhalb von Multipolygon

Communities Deutschland (Germany)
#1

Hallo,

gibt es mit der OSM-API die Möglichkeit, herauszubekommen, ob ein Punkt innerhalb eines Multipolygons liegt (im konkreten Fall eines Bundeslandes)? Oder kennt jemand dazu ein entsprechendes PHP-Skript? Habe schon versucht, meine Mathematik-Kenntnisse mal wieder vorzukramen, dachte aber nach einiger Denkarbeit, dass das entsprechende Rad ja sicher schon erfunden wurde.

Vielen Dank

Johannes

#2

http://wiki.openstreetmap.org/wiki/Overpass_API/Overpass_QL#Query_for_Areas

#3

Vielen Dank!

Ich habe eine weitere Methode außerhalb vom OSM gefunden, den Punkt-in-Polygon-Test nach Jordan:
http://de.wikipedia.org/wiki/Punkt-in-Polygon-Test_nach_Jordan

Habe den Pseudocode aus dem Wikipedia-Eintrag mal in PHP übersetzt:

function punktInPolygon($p,$q) {
	$n = count($p)-1;
	$p[0] = $p[$n];
	$t = -1;
	for($i=0;$i<$n;$i++) {
		$t = $t*kreuzProdTest($q,$p[$i],$p[$i+1]);
	}
			
	return $t;
}
		
function kreuzProdTest($A,$B,$C) {
	$xA = $A[0]; $yA = $A[1];
	$xB = $B[0]; $yB = $B[1];
	$xC = $C[0]; $yC = $C[1];
			
	if($yA == $yB AND $yB == $yC) {
		if(($xB <= $xA AND $xA <= $xC) OR ($xC <= $xA AND $xA <= $xB)) {
			return 0;
		}
		else {
			return 1;
		}
	}
			
	if($yB > $yC) {
		$xBtemp = $xB;
		$yBtemp = $yB;
		$xB = $xC;
		$yB = $yC;
		$xC = $xBtemp;
		$yC = $yBtemp;
	}
			
	if($yA == $yB AND $xA == $xB) {
		return 0;
	}
			
	if($yA <= $yB OR $yA > $yC) {
		return 1;
	}
			
	$delta = (($xB-$xA)*($yC-$yA))-(($yB-$yA)*($xC-$xA));
			
	if($delta > 0) {
		return -1;
	}
	elseif($delta < 0) {
		return 1;
	}
	else {
		return 0;
	}
}

Vielleicht kann es jemand gebrauchen!

Gruß

Johannes

#4

Nahmd,

Ich würde an dieser Stelle schreiben:


$n = count($p);
$p[n] = $p[0]:

alldieweil mit 1 beginnende Indizes beim Programmieren eher unüblich sind und somit schnell zu Fehlern führen.

Just my 2.38¢

Gruß Wolf