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
