计算几何：点是否在平面多边形内

WXYZ 的个人资料WXYZ的异人馆照片日志列表

工具

帮助

9月30日

计算几何：点是否在平面多边形内

又是周赛，今天状态还不错。

今天遇到一题判断两个多边形是否有重叠部分。计算几何，这部分没学过，做题过程中临时上网找资料来看了。具体题目副本有PKU的3082题。

判断两个多边形（假设为A和B）是否有重叠部分，可以先求A是否有某个顶点在B内，或B是否有某个顶点在A内，满足其中之一，就可说AB有重叠了。这样问题就转化为一个点是否在多边形内的问题。

上网找找，判断点是否在多边形内有三个步骤：（转自csdn）

   第一步：判断这个点是不是就是多边形的端点；
   第二步：判断这个点是不是落在多边形的边界上；
    第三步：通过这个点横向作一平行射线，判断与多边形的交点数，如果交点是顶点，则交点数加一，结果如果是奇数，则该点落在多边形之内，如果是偶数，则反之。

具体算法涉及向量叉积，具体这部分不详细说了，上网轻易查到，下面贴过主算法函数吧，参考很好用。

还是来自于csdn的。

const double INFINITY = 1e10;
const double ESP = 1e-5;
const int MAX_N = 1000;

struct Point {
double x, y;
};

struct LineSegment {
Point pt1, pt2;
};

inline double max(double x, double y)
{
return (x > y ? x : y);
}

inline double min(double x, double y)
{
return (x < y ? x : y);
}

// 计算叉乘 |P1P0| × |P2P0|
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(Point polygon[], int n, Point point)
{
if (n == 1) {
return ( (fabs(polygon[0].x - point.x) < ESP) && (fabs(polygon[0].y - point.y) < ESP) );
} else if (n == 2) {
LineSegment side;
side.pt1 = polygon[0];
side.pt2 = polygon[1];
return IsOnline(point, side);
}

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) ) {
return true;
}

// 如果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++;
}
}

return ( count % 2 == 1 );
}

最后再贴下某人在csdn上他的计算几何库目录，自己参考一下，有时间自己写个。

㈠点的基本运算
1. 平面上两点之间距离 1
2. 判断两点是否重合 1
3. 矢量叉乘 1
4. 矢量点乘 2
5. 判断点是否在线段上 2
6. 求一点饶某点旋转后的坐标 2
7. 求矢量夹角 2

㈡线段及直线的基本运算
1. 点与线段的关系 3
2. 求点到线段所在直线垂线的垂足 4
3. 点到线段的最近点 4
4. 点到线段所在直线的距离 4
5. 点到折线集的最近距离 4
6. 判断圆是否在多边形内 5
7. 求矢量夹角余弦 5
8. 求线段之间的夹角 5
9. 判断线段是否相交 6
10.判断线段是否相交但不交在端点处 6
11.求线段所在直线的方程 6
12.求直线的斜率 7
13.求直线的倾斜角 7
14.求点关于某直线的对称点 7
15.判断两条直线是否相交及求直线交点 7
16.判断线段是否相交，如果相交返回交点 7

㈢多边形常用算法模块
1. 判断多边形是否简单多边形 8
2. 检查多边形顶点的凸凹性 9
3. 判断多边形是否凸多边形 9
4. 求多边形面积 9
5. 判断多边形顶点的排列方向，方法一 10
6. 判断多边形顶点的排列方向，方法二 10
7. 射线法判断点是否在多边形内 10
8. 判断点是否在凸多边形内 11
9. 寻找点集的graham算法 12
10.寻找点集凸包的卷包裹法 13
11.判断线段是否在多边形内 14
12.求简单多边形的重心 15
13.求凸多边形的重心 17
14.求肯定在给定多边形内的一个点 17
15.求从多边形外一点出发到该多边形的切线 18
16.判断多边形的核是否存在 19

㈣圆的基本运算
1 .点是否在圆内 20
2 .求不共线的三点所确定的圆 21

㈤矩形的基本运算
1.已知矩形三点坐标，求第4点坐标 22

㈥常用算法的描述 22

㈦补充
1．两圆关系： 24
2．判断圆是否在矩形内： 24
3．点到平面的距离： 25
4．点是否在直线同侧： 25
5．镜面反射线： 25
6．矩形包含： 26
7．两圆交点： 27
8．两圆公共面积： 28
9. 圆和直线关系： 29
10. 内切圆： 30
11. 求切点： 31
12. 线段的左右旋： 31
13．公式： 32

1:32 | 写入日志 | 热爱电脑

若要添加评论，请使用您的 Windows Live ID 登录（如果您使用过 Hotmail、Messenger 或 Xbox LIVE，您就拥有 Windows Live ID）。登录

还没有 Windows Live ID 吗？请注册

zhang萬里無雲发表:

虽然我学过C++，但是完全是一头雾水。

真想知道一年后，我大三，在空间发我学的东西会不会被人揍死。

10 月 18 日

引用通告

此日志的引用通告 URL 是：

http://wxyz202.spaces.live.com/blog/cns!D4DC981555112325!502.trak

引用此项的网络日志

日志

计算几何：点是否在平面多边形内

评论 (1)

引用通告