2011-5-2
最近又写了一个检查点在多边形内部的程序，主要还是为了XX公司那边的一个项目做点小事情。好了，下面开始讲解原理。
射线法检测，其实就是在已知点内，固定好该点的X或者Y坐标，然后对任意X或者Y轴做垂线（固定X对Y轴做垂线，固定Y对X轴做垂线）。垂线和线段如果相交的次数是奇数，证明点在多边形内部，如果是偶次，说明点在多边形外部。
但是，要讨论的是凸多边形会有特殊情况。
上图，P1的时候做射线，交了3点，但是在多边形外，P2交了2点，但是在多边形内部。
还有的情况就是
和上边的类似，只是在程序处理上，坐标y一个是从高到低，一个低到高
遇到这两种情况，只能当做相交了一次，在那个拐弯点。
用程序处理如下：
if((*this.Point_Is_On_Line)(FixedLinePoints[i], *MovePoint, this.RadialLineEndP))//从这里往下主要是判断凸多边形2种的特殊情况
{
if(FixedLinePoints[i].y > FixedLinePoints[j].y )
{
this.CrossCount++;
}
}
else if((*this.Point_Is_On_Line)(FixedLinePoints[j], *MovePoint, this.RadialLineEndP))
{
if(FixedLinePoints[j].y > FixedLinePoints[i].y)
{
this.CrossCount++;
}
}
else if((*this.Check_Two_Lines_Intersect)(FixedLinePoints + i, FixedLinePoints + j, MovePoint, &this.RadialLineEndP))//判断射线与线段是否相交
{
this.CrossCount++;
}
有优先级别的判断，先是第一种情况，后是第二种情况，最后是普通情况的判断。就可以了。
测试条件：
struct Vertex_PointXY testtab[4] = {
{0,0},{0,8},{2,2},{4,0},
};
struct Vertex_PointXY a = {-1, 2};
struct Vertex_PointXY b = {100, 100};
struct Vertex_PointXY c = {0 , 0};
struct Vertex_PointXY d = {1,2};
实验结果如下：
2
Point is outside the polygon!
2
Point is outside the polygon!
1
Point is on the polygon!
0
Point is in the polygon!
下面是实现代码：
#ifndef CHECK_POINT_IN_POLYGON_H_
#define CHECK_POINT_IN_POLYGON_H_
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdint.h>
#include <string.h>
#ifndef INFINITY
#define INFINITY 1e10
#endif
#ifndef ESP
#define ESP 1e-5
#endif
#ifndef MAX_N
#define MAX_N 1000
#endif
struct Vertex_PointXY
{
double x;
double y;
};
struct Vertex_List
{
uint32_t vertex_num;
struct Vertex_PointXY *vertex_point;
};
struct Bounded_Rectangle
{
double min_x;
double min_y;
double max_x;
double max_y;
};
struct Check_Two_Points_Same_Side_Of_Beeline_Private
{
double CTPSSB_dx;
double CTPSSB_dy;
double CTPSSB_dx1;
double CTPSSB_dy1;
double CTPSSB_dx2;
double CTPSSB_dy2;
};
struct Check_Two_Lines_Intersect_Private
{
int return_value;
int temp[2];
};
struct Point_Is_On_Line_Private
{
double *temp;
int return_value;
};
struct Check_Point_In_Polygon_Private
{
struct Bounded_Rectangle BoundedRectangle;
void (*Get_Vertices_Bound) (struct Vertex_PointXY *Vertex_P, uint32_t Vertex_Num, struct Bounded_Rectangle *BoundedResult);
int32_t (*Check_Two_Lines_Intersect) (\
struct Vertex_PointXY *line1_start_p,\
struct Vertex_PointXY *line1_end_p,\
struct Vertex_PointXY *line2_start_p,\
struct Vertex_PointXY *line2_end_p\
);
int (*Point_Is_On_Line) (struct Vertex_PointXY point, struct Vertex_PointXY fixed_line_p1, struct Vertex_PointXY fixed_line_p2);
struct Vertex_PointXY RadialLineEndP;
int CrossCount;
int return_value;
};
//该函数完成Check_Point_In_Polygon的私有成员变量和函数的初始化工作
#define REGISTER_CHECK_POINT_IN_POLYGON_PRIVATE_VALUE(NAME) \
struct Check_Point_In_Polygon_Private NAME;\
NAME.Get_Vertices_Bound = Get_Vertices_Bound;\
NAME.Check_Two_Lines_Intersect = Check_Two_Lines_Intersect;\
NAME.Point_Is_On_Line = Point_Is_On_Line; \
struct Check_Point_In_Polygon_Public
{
struct Vertex_PointXY *FixedLinePoints;
uint32_t LinePointsNum;
struct Vertex_PointXY *MovePoint;
int (*Check_Point_In_Polygon)( \
struct Vertex_PointXY *FixedLinePoints,\
uint32_t LinePointsNum,\
struct Vertex_PointXY *MovePoint\
);
};
//提供给外部函数的接口
#define CHECK_POINT_IN_POLYGON_INTAFACE(FIXEDPOINTS, NUM, MOVEPOINT) Check_Point_In_Polygon(FIXEDPOINTS, NUM, &MOVEPOINT)
extern int Check_Point_In_Polygon( \
struct Vertex_PointXY *FixedLinePoints,\
uint32_t LinePointsNum,\
struct Vertex_PointXY *MovePoint\
);
#endif
#include "check_point_in_polygon.h"
//私有函数声明区
static int32_t Check_Two_Points_Same_Side_Of_Beeline( \
struct Vertex_PointXY *fixed_line_PS,\
struct Vertex_PointXY *fixed_line_PE,\
struct Vertex_PointXY *moved_1_PM,\
struct Vertex_PointXY *moved_2_PM\
);
static int32_t Check_Two_Lines_Intersect(\
struct Vertex_PointXY *line1_start_p,\
struct Vertex_PointXY *line1_end_p,\
struct Vertex_PointXY *line2_start_p,\
struct Vertex_PointXY *line2_end_p\
);
static void Get_Vertices_Bound(struct Vertex_PointXY *Vertex_P, uint32_t Vertex_Num, struct Bounded_Rectangle *BoundedResult);
static int Point_Is_On_Line(struct Vertex_PointXY point, struct Vertex_PointXY fixed_line_p1, struct Vertex_PointXY fixed_line_p2);
//公共函数声明区
//私有函数定义区
static int32_t Check_Two_Points_Same_Side_Of_Beeline( \
struct Vertex_PointXY *fixed_line_PS,\
struct Vertex_PointXY *fixed_line_PE,\
struct Vertex_PointXY *moved_1_PM,\
struct Vertex_PointXY *moved_2_PM\
)
{
int return_value = 0;
struct Check_Two_Points_Same_Side_Of_Beeline_Private *this = (struct Check_Two_Points_Same_Side_Of_Beeline_Private *)malloc(sizeof (struct Check_Two_Points_Same_Side_Of_Beeline_Private));
this->CTPSSB_dx = fixed_line_PE->x - fixed_line_PS->x;
this->CTPSSB_dy = fixed_line_PE->y - fixed_line_PS->y;
this->CTPSSB_dx1 = moved_1_PM->x - fixed_line_PS->x;
this->CTPSSB_dy1 = moved_1_PM->y - fixed_line_PS->y;
this->CTPSSB_dx2 = moved_2_PM->x - fixed_line_PE->x;
this->CTPSSB_dy2 = moved_2_PM->y - fixed_line_PE->y;
return_value = ((this->CTPSSB_dx * this->CTPSSB_dy1 - this->CTPSSB_dy * this->CTPSSB_dx1) * (this->CTPSSB_dx * this->CTPSSB_dy2 - this->CTPSSB_dy * this->CTPSSB_dx2) > 0 ? 1 : 0);
free(this);
return return_value;
}
static int32_t Check_Two_Lines_Intersect(\
struct Vertex_PointXY *line1_start_p,\
struct Vertex_PointXY *line1_end_p,\
struct Vertex_PointXY *line2_start_p,\
struct Vertex_PointXY *line2_end_p\
)
{
struct Check_Two_Lines_Intersect_Private CTLIP_V;
memset(&CTLIP_V, 0, sizeof(CTLIP_V));
CTLIP_V.temp[0] = Check_Two_Points_Same_Side_Of_Beeline(line1_start_p, line1_end_p, line2_start_p, line2_end_p);
CTLIP_V.temp[1] = Check_Two_Points_Same_Side_Of_Beeline(line2_start_p, line2_end_p, line1_start_p, line1_end_p);
CTLIP_V.return_value = ((CTLIP_V.temp[0] == 0) && (CTLIP_V.temp[1] == 0)) ? 1 : 0;
return CTLIP_V.return_value ;
}
static void Get_Vertices_Bound(struct Vertex_PointXY *Vertex_P, uint32_t Vertex_Num, struct Bounded_Rectangle *BoundedResult)
{
int i = 0;
if(Vertex_Num > 0)
{
BoundedResult->min_x = Vertex_P[0].x;
BoundedResult->max_x = Vertex_P[0].x;
BoundedResult->min_y = Vertex_P[0].y;
BoundedResult->max_y = Vertex_P[0].y;
}
else
{
BoundedResult->min_x = 0;
BoundedResult->max_x = 0;
BoundedResult->min_y = 0;
BoundedResult->max_y = 0;
}
for(i = 1; i < Vertex_Num; i++)
{
if(Vertex_P[i].x < BoundedResult->min_x)
{
BoundedResult->min_x = Vertex_P[i].x;
}
if(Vertex_P[i].y < BoundedResult->min_y)
{
BoundedResult->min_y = Vertex_P[i].y;
}
if(Vertex_P[i].x > BoundedResult->max_x)
{
BoundedResult->max_x = Vertex_P[i].x;
}
if(Vertex_P[i].y > BoundedResult->max_y)
{
BoundedResult->max_y = Vertex_P[i].y;
}
}
}
//计算差乘 P0P1 X P0P2
static double Multiplication_Cross(struct Vertex_PointXY P1, struct Vertex_PointXY P2, struct Vertex_PointXY P0)
{
return ((P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y));
}
static int Point_Is_On_Line(struct Vertex_PointXY point, struct Vertex_PointXY fixed_line_p1, struct Vertex_PointXY fixed_line_p2)
{
struct Point_Is_On_Line_Private this;
this.temp = (double *) malloc(3 * sizeof(double));
//if(this.temp == NULL)
// return 1;
this.temp[0] = Multiplication_Cross(fixed_line_p1, fixed_line_p2, point);
this.temp[1] = (point.x - fixed_line_p1.x) * (point.x - fixed_line_p2.x);
this.temp[2] = (point.y - fixed_line_p1.y) * (point.y - fixed_line_p2.y);
this.return_value = (fabs(this.temp[0]) < ESP) && (this.temp[1] <= 0) && (this.temp[2] <= 0);
free(this.temp);
return this.return_value;
}
//公共函数声明区
int Check_Point_In_Polygon(\
struct Vertex_PointXY *FixedLinePoints,\
uint32_t LinePointsNum,\
struct Vertex_PointXY *MovePoint\
)
{
//struct Check_Point_In_Polygon_Private this;
int i = 0;
int j = 0;
//this.Get_Vertices_Bound = Get_Vertices_Bound;
//this.Check_Two_Lines_Intersect = Check_Two_Lines_Intersect;
//this.Point_Is_On_Line = Point_Is_On_Line;
REGISTER_CHECK_POINT_IN_POLYGON_PRIVATE_VALUE(this);
if(LinePointsNum < 3)
{
return 0;
}
(*this.Get_Vertices_Bound)(FixedLinePoints, LinePointsNum, &this.BoundedRectangle);
if(MovePoint->x < this.BoundedRectangle.min_x || MovePoint->x > this.BoundedRectangle.max_x || MovePoint->y < this.BoundedRectangle.min_y || MovePoint->y > this.BoundedRectangle.max_y)
{
return 2;
}
this.RadialLineEndP.x = this.BoundedRectangle.max_x;
this.RadialLineEndP.y = MovePoint->y;
for(i = 0; i < LinePointsNum; i++)
{
j = (i + 1) % LinePointsNum;
if((*this.Point_Is_On_Line)(*MovePoint, FixedLinePoints[i], FixedLinePoints[j]))
{
return 1;
}
if(fabs(FixedLinePoints[i].y - FixedLinePoints[j].y) < ESP)//如果固定点平行射线就不管了，肯定不会相交
{
continue;
}
if((*this.Point_Is_On_Line)(FixedLinePoints[i], *MovePoint, this.RadialLineEndP))//从这里往下主要是判断凸多边形2种的特殊情况
{
if(FixedLinePoints[i].y > FixedLinePoints[j].y )
{
this.CrossCount++;
}
}
else if((*this.Point_Is_On_Line)(FixedLinePoints[j], *MovePoint, this.RadialLineEndP))
{
if(FixedLinePoints[j].y > FixedLinePoints[i].y)
{
this.CrossCount++;
}
}
else if((*this.Check_Two_Lines_Intersect)(FixedLinePoints + i, FixedLinePoints + j, MovePoint, &this.RadialLineEndP))//判断射线与线段是否相交
{
this.CrossCount++;
}
}
if(this.CrossCount % 2 == 1) //是奇数，说明点在多边形内，返回0
{
return 0;
}
else
{
return 2; //偶数返回2，说明点在多边形外
}
}
#include "check_point_in_polygon.h"
void display(num)
{
switch(num)
{
case 0 : printf("Point is in the polygon!\n");break;
case 1 : printf("Point is on the polygon!\n");break;
case 2 : printf("Point is outside the polygon!\n");break;
}
}
int main(void)
{
struct Vertex_PointXY testtab[4] = {
{0,0},{0,8},{2,2},{4,0},
};
struct Vertex_PointXY a = {-1, 2};
struct Vertex_PointXY b = {100, 100};
struct Vertex_PointXY c = {0 , 0};
struct Vertex_PointXY d = {1,2};
printf("%d \n",CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, a));
display(CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, a));
printf("%d \n",CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, b));
display(CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, b));
printf("%d \n",CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, c));
display(CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, c));
printf("%d \n",CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, d));
display(CHECK_POINT_IN_POLYGON_INTAFACE(testtab, 4, d));
return 0;
}