3. Punkte in Vieleck validieren

Punkte in Vieleck validieren

  • S

    Hi Community,

    Ich komme bei einem Problem nicht weiter... Und zwar habe ich ca. 60 tausend Punkte als Geokoordinaten und bekomme von einer anderen Quelle 3-x Koordinaten und ich soll alle Punkte ausgeben die in diesen Vieleck liegen.
    Das ganze sollte schon relativ performant funktionieren und ich habe noch keine wirkliche Idee um dies zu lösen. Meine mathematischen Fähigkeiten beschränken sich leider auch nur auf ein Leistungskurs den ich mit 12 Punkten abgeschlossen habe.

    Ich weiß das es nicht direkt ein Problem in C++ ist aber ich habe keine Kategorie gefunden in die es besser passen könnte da ich dies mit C++ verwirklichen muss.

    Mit freundlichen Grüßen
    Synonym

    0

  • Als Algorithmus kannst du dir ersteinmal Punkt-in-Polygon-Test nach Jordan anschauen.
    Evtl. könntest du auch versuchen ein umspannendes Rechteck um das Zielpolygon zu legen und dann schonmal die Punkte außerhalb des Rechtecks verwerfen, so daß dann nur noch die inneren Punkte näher betrachtet werden müssen.

    0
  • Mod

    http://de.wikipedia.org/wiki/Punkt-in-Polygon-Test_nach_Jordan
    Schnell den Pseudo-Code implementiert:

    template< typename T >
struct Point
{
	T x, y;
};

template< typename T, typename U>
bool operator==( Point<T> const& lhs, Point<U> const& rhs )
{
	return lhs.x == rhs.x && lhs.y == rhs.y;
}

template< typename T >
bool in_between_included( T a, T b, T c )
{
	if( a > c )
		return c <= b && b <= a;
	return a <= b && b <= c;
}

template< typename T >
int sgn(T val)
{
	return (T{0} < val) - (val < T{0});
}

#include <algorithm> // std::swap

template< typename T >
int crossProdTest( T a, T b, T c )
{
	if( a.y == b.y && b.y == c.y )
		return !in_between_included( b.x, a.x, c.x );

	if( b.y > c.y )
		std::swap(b, c);

	if( a.y == b.y && a.x == b.x ) return 0;
	if( a.y <= b.y || a.y >  c.y ) return 1;

	auto const delta = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

	return -1 * sgn(delta);
}

#include <iterator> // std::prev / std::next

template< typename BidirectionalIterator,
          typename T >
int pointInPolygon( BidirectionalIterator first, BidirectionalIterator last, T Q )
{
	if( first == last ) return 0;

	auto last_iter = std::prev(last);

	int t = -1 * crossProdTest( Q, *last_iter, *first );

	for(; first != last_iter; ++first )
		t *= crossProdTest( Q, *first, *std::next(first) );

	return t;
}

#include <iostream>

int main()
{
	// Test whether (2, 2) is in the parallelogram
	Point<double> points[]{ 0, 0,
	                        1, 2,
	                        0, 4,
	                        5, 2 };

	std::cout << pointInPolygon( std::begin(points), std::end(points), Point<double>{2, 2} );
}

    Edit^4: Und jetzt sitzt die Formattierung nicht richtig... und die Gelegenheit habe ich auch gleich genutzt um die Namensgebung anzupassen 🤡

    0
  • S

    Arcoth schrieb:

    http://de.wikipedia.org/wiki/Punkt-in-Polygon-Test_nach_Jordan
    Schnell den Pseudo-Code implementiert:

    template< typename T >
struct Point
{
	T x, y;
};

template< typename T, typename U>
bool operator==( Point<T> const& lhs, Point<U> const& rhs )
{
	return lhs.x == rhs.x && lhs.y == rhs.y;
}

template< typename T >
bool in_between_included( T a, T b, T c )
{
	if( a > c )
		return c <= b && b <= a;
	return a <= b && b <= c;
}

template< typename T >
int sgn(T val)
{
	return (T{0} < val) - (val < T{0});
}

#include <algorithm> // std::swap

template< typename T >
int crossProdTest( T a, T b, T c )
{
	if( a.y == b.y && b.y == c.y )
		return !in_between_included( b.x, a.x, c.x );

	if( b.y > c.y )
		std::swap(b, c);

	if( a.y == b.y && a.x == b.x ) return 0;
	if( a.y <= b.y || a.y >  c.y ) return 1;

	auto const delta = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);

	return -1 * sgn(delta);
}

#include <iterator> // std::prev / std::next

template< typename BidirectionalIterator,
          typename T >
int pointInPolygon( BidirectionalIterator first, BidirectionalIterator last, T Q )
{
	if( first == last ) return 0;

	auto last_iter = std::prev(last);

	int t = -1 * crossProdTest( Q, *last_iter, *first );

	for(; first != last_iter; ++first )
		t *= crossProdTest( Q, *first, *std::next(first) );

	return t;
}

#include <iostream>

int main()
{
	// Test whether (2, 2) is in the parallelogram
	Point<double> points[]{ 0, 0,
	                        1, 2,
	                        0, 4,
	                        5, 2 };

	std::cout << pointInPolygon( std::begin(points), std::end(points), Point<double>{2, 2} );
}

    Edit^4: Und jetzt sitzt die Formattierung nicht richtig... und die Gelegenheit habe ich auch gleich genutzt um die Namensgebung anzupassen 🤡

    Super Sache 🙂 Vielen lieben dank 😃 ich freu mich wie ein Schnitzel 😃
    Muss das nur noch auf C++98 umschreiben und dann sollte es funktionieren 🙂

    @Th69 : Auch dir vielen Dank 🙂

    0
Anmelden zum Antworten