Abfrage ob Punkt in einem unsymetrischen Vieleck (2d) liegt

NetZwerg

Hi,
Ich habe mit Linien ein Paar Figuren gezeichnet und möchte nun abfragen ,wenn ich ein Punkt mit der Maus angebe, ob der in einer Figur ist.
Die Figuren bestehen halt aus Punkten die mit Linien mit einander verbunden sind.
Wie kann man das möglichst effizient abfragen? Kennt einer ein Algo. dafür und hat einen guten Link, zu diesem Thema, oder kann diesen gut beschreiben?
Google & Co. liefern nicht gerade viele Ergebnisse...

MFG

Jester

http://www.acm.org/pubs/tog/editors/erich/ptinpoly/

rapso

am effizientesten duerfte ein solid-bsp-tree sein. ist auch nicht so aufwendig zu implementieren in 2d, wobei jesters loesung 100mal weniger aufwand beim programmieren ist, wenn du also nicht wirklich auf "Wie kann man das möglichst effizient abfragen" bestehst, nimm seinen

TomasRiker

Aus einem meiner Projekte:
(die Funktion ist ein Template, damit sie mit jeglicher Art von 2D-Vektor zurechtkommt - also float-, double- oder int-Vektor)

Das könnte man noch optimieren, indem man statt oldPos und newPos nur die Iteratoren speichert.

// bestimmt, ob ein Punkt in einem Polygon liegt
template<typename T> bool pointInPolygon( const Vec<2, T>& point,
										  const std::vector<Vec<2, T> >& polygon )
{
	if( polygon.size() < 3 ) return false;

	Vec<2, T> oldPos( polygon.back() );
	Vec<2, T> newPos, p1, p2;
	bool inside = false;

	for( std::vector<Vec<2, T> >::const_iterator it = polygon.begin();
		 it != polygon.end();
		 it++ )
	{
		newPos = *it;

		if( newPos.x > oldPos.x )
		{
			p1 = oldPos;
			p2 = newPos;
		}
		else
		{
			p1 = newPos;
			p2 = oldPos;
		}

		if( ( newPos.x < point.x ) == ( point.x < oldPos.x ) &&
			( point.y - p1.y ) * ( p2.x - p1.x ) < ( p2.y - p1.y ) * ( point.x - p1.x ) )
		{
			inside = !inside;
		}

		oldPos = newPos;
	}

	return inside;
}

TGGC

@Tomas:
Kann es sein, das es so nur fuer konvexe Vielecke geht? Also vorher immer schoen zerlegen. f'`8k

Gruß, TGGC (\-/ has leading)

TomasRiker

TGGC schrieb:

@Tomas:
Kann es sein, das es so nur fuer konvexe Vielecke geht? Also vorher immer schoen zerlegen. f'`8k

Nein, das geht für beliebige Vielecke!

Der Code stammt übrigens von hier:
http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/

TGGC

Stimmt, habe mich geirrt. f'`8k

Gruß, TGGC (\-/ has leading)