C# 判断点是否在不规则区域内
(2011-09-09 19:36:09)
标签:
c点在不规则区域内在多边形内判断region类it |
分类: 编程技术 |
来自:http://hi.baidu.com/caokyo/blog/item/2f66aeafe8cff6c57cd92a08
using system.Drawing;/// 如果不存在,那么在工程的“引用”中添加"system.Drawing"
using
System.Drawing.Drawing2D;
方法二 算法 : public int
isLeft(Point P0, Point P1,Point P2)
图形算法:
1,面积法。就是看所有边和目标点组成的三角形面积和是否等于总的多边形面积,如果相等,则在内部。反之在外部。这种方法计算量较大,用到的主要计算是查乘。
2,夹角和法。参见三楼,判断所有边和目标点的夹角和是否为360度。计算量比上面这种方法稍微小点,用到主要是点乘和求模计算。
3,引射线法。就是从该点出发引一条射线,看这条射线和所有边的交点数目。如果有奇数个交点,则说明在内部,如果有偶数个交点,则说明在外部。这是所有方法中计算量最小的方法,在光线追踪算法中有大量的应用。
在C#中的话,有一个Region类,可以直接调用IsVisible判断是否在这个区域内部,我估计内部的实现应该是上面说的第三种方法。主要看你的需求是哪种输入了,如果在C#中,你完全可以用Region类来隐藏内部实现。
另外一种解决方法:
1.
2.
3.
4.
上),否则继续下面的判断;
5.
6.
代码:
const double INFINITY = 1e10;
const double ESP = 1e-5;
const int MAX_N = 1000;
struct Point {
double x, y;
};
struct LineSegment {
Point pt1, pt2;
};
typedef vector<Point> Polygon;
//计算叉乘|P0P1|×|P0P2|
double Multiply(Point p1, Point p2, Point p0)
{
return ( (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y) );
}
//判断线段是否包含点point
bool IsOnline(Point point, LineSegment line)
{
return( ( fabs(Multiply(line.pt1, line.pt2, point)) < ESP ) &&
( ( point.x - line.pt1.x ) * ( point.x - line.pt2.x ) <= 0 ) &&
( ( point.y - line.pt1.y ) * ( point.y - line.pt2.y ) <= 0 ) );
}
//判断线段相交
bool Intersect(LineSegment L1, LineSegment L2)
{
return( (max(L1.pt1.x, L1.pt2.x) >= min(L2.pt1.x, L2.pt2.x)) &&
(max(L2.pt1.x, L2.pt2.x) >= min(L1.pt1.x, L1.pt2.x)) &&
(max(L1.pt1.y, L1.pt2.y) >= min(L2.pt1.y, L2.pt2.y)) &&
(max(L2.pt1.y, L2.pt2.y) >= min(L1.pt1.y, L1.pt2.y)) &&
(Multiply(L2.pt1, L1.pt2, L1.pt1) * Multiply(L1.pt2, L2.pt2, L1.pt1) >= 0) &&
(Multiply(L1.pt1, L2.pt2, L2.pt1) * Multiply(L2.pt2, L1.pt2, L2.pt1) >= 0)
);
}
//判断点在多边形内
bool InPolygon(const Polygon& polygon, Point point)
{
int n = polygon.size();
int count = 0;
LineSegment line;
line.pt1 = point;
line.pt2.y = point.y;
line.pt2.x = - INFINITY;
for( int i = 0; i < n; i++ ) {
//得到多边形的一条边
LineSegment side;
side.pt1 = polygon[i];
side.pt2 = polygon[(i + 1) % n];
if( IsOnline(point, side) ) {
return1 ;
}
//如果side平行x轴则不作考虑
if( fabs(side.pt1.y - side.pt2.y) < ESP ) {
continue;
}
if( IsOnline(side.pt1, line) ) {
if( side.pt1.y > side.pt2.y ) count++;
} else if( IsOnline(side.pt2, line) ) {
if( side.pt2.y > side.pt1.y ) count++;
} else if( Intersect(line, side) ) {
count++;
}
}
if ( count % 2 == 1 ) {return 0;}
else { return 2;}
}
}