雁过无痕
C++博客
::
首页
::
新随笔
::
联系
::
聚合
::
管理
::
<
2011年7月
>
日
一
二
三
四
五
六
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
留言簿
(7)
给我留言
查看公开留言
查看私人留言
随笔分类
C++(14)
(rss)
c++模板(1)
(rss)
编程之美(29)
(rss)
面试题精解(2)
(rss)
算法(24)
(rss)
小作品(4)
(rss)
随笔档案
2014年6月 (1)
2013年3月 (2)
2012年11月 (1)
2012年8月 (2)
2012年5月 (2)
2012年3月 (4)
2012年2月 (2)
2011年9月 (1)
2011年8月 (1)
2011年7月 (8)
2011年5月 (2)
2011年4月 (2)
2011年3月 (4)
2010年12月 (5)
2010年9月 (2)
2010年8月 (20)
2010年7月 (2)
2010年6月 (3)
搜索
最新随笔
1. SEH异常处理专利到期了
2. 面试题: 找出数组中三个只出现一次的数
3. mingw gcc的头文件存在结构定义错误！！
4. c++11 最反直觉的地方
5. decltype的小“陷阱”
6. 内嵌汇编实现的函数转发
7. 一些老游戏CPU 100%占用的解决方法
8. 三国志5剧本修改器 1.2
9. 安全的整数比较
10. 面试题精解 目录
11. 面试题精解之二： 字符串、数组（1）
12. 避免计算过程中出现溢出的一个技巧
13. Fibonacci数计算中的两个思维盲点及其扩展数列的通用高效解法
14. 面试题精解之一： 二叉树
15. 喝汽水问题
16. 三国志5剧本修改器 1.1
17. 对环状数组求连续子数组的最大和
18. 最短摘要的生成（补充）
19. Fibonacci数列的两种O(lgn)解法
20. VC 2010 error D8027，无法执行c1xx.dll的解决方法
最新评论
1. re: 《编程之美》读书笔记02：1.3 一摞烙饼的排序
请问楼主可以换个主题吗，这个主题代码排版太不好了，复制也不方便。。。
--韩
2. re: 一道C++面试题的误区
对前3种算法，将数组长度增加到1e8，并对十组随机数组进行测试，得到结果：
--3d
3. re: 面试题： 找出二叉树上任意两个结点的最近共同父结点。
后序遍历到第一个满足这个条件的节点就是所要求的节点A。另外，还必须对这两个节点在一条线上的情况，做特殊处理。
--3d
4. re: 面试题精解之一： 二叉树
先固定B点不动（即B到C的距离不变），根据上面的公式，可得A到C的距离最大，即点A是C左子树下距离C最远的点，即：
--3d
5. re: 面试题: 找出数组中三个只出现一次的数
，当实际上发生溢出时，就是UB行为，编译器若进行些激进的优化就得不到正确结果。
--3d
6. re: SEH异常处理专利到期了
能让用户不再纠结SJLJ，Dwarf2的选择。
--3d
7. re: 《编程之美》读书笔记23： 1.1 让CPU占用率曲线听你指挥
评论内容较长,点击标题查看
--3d
8. re: 《编程之美》读书笔记15： 4.5 磁带文件存放优化
写的很好，很容易理解，赞
--zhenzhismile
9. re: 多重背包O(N*V)算法详解（使用单调队列）
评论内容较长,点击标题查看
--天天好赢钱
10. re: SEH异常处理专利到期了
评论内容较长,点击标题查看
--121e1212
阅读排行榜
1. 面试题精解之一： 二叉树(9444)
2. 面试题： 找出二叉树上任意两个结点的最近共同父结点。(8710)
3. VC 2010 error D8027，无法执行c1xx.dll的解决方法(7314)
4. 面试题: 找出数组中三个只出现一次的数(6962)
5. 多重背包O(N*V)算法详解（使用单调队列）(6455)
6. 螺旋矩阵 (4900)
7. 《编程之美》读书笔记08：2.9 Fibonacci序列 —— O(log n)求Fibonacci数列（非矩阵法）(4692)
8. 《编程之美》读书笔记23： 1.1 让CPU占用率曲线听你指挥(4605)
9. 《编程之美》读书笔记 目录(4038)
10. 一道C++面试题的误区(3992)
评论排行榜
1. 25匹马取前5(14)
2. 面试题： 找出二叉树上任意两个结点的最近共同父结点。(11)
3. 恶心的转载(11)
4. 《编程之美》读书笔记08：2.9 Fibonacci序列 —— O(log n)求Fibonacci数列（非矩阵法）(11)
5. Fibonacci数计算中的两个思维盲点及其扩展数列的通用高效解法(11)
6. 点在三角形内（1）(9)
7. 内嵌汇编实现的函数转发(8)
8. 一道C++面试题的误区(8)
9. 喝汽水问题(7)
10. decltype的小“陷阱”(5)
点在多边形内
射线法：
射线法
#include
<
iostream
>
#include
<
cfloat
>
#include
<
cassert
>
struct
Point {
double
x, y;
Point() {}
Point(
double
xx,
double
yy) : x(xx), y(yy) {}
};
bool
is_in_polygon(
const
Point arr[], size_t len,
const
Point
&
p)
{
size_t count
=
0
;
const
double
x
=
p.x, y
=
p.y;
Point a
=
arr[len
-
1
];
for
(
const
Point
*
b
=
arr; b
<
arr
+
len; a
=
*
b
++
) {
if
((a.y
<
y)
==
(b
->
y
<
y)) {
if
(a.y
==
b
->
y
&&
y
==
a.y
&&
//
fabs(fabs(a.x - b->x) - fabs(a.x - x) - fabs(b->x - x)) < DBL_EPSILON)
((a.x
>=
x
&&
b
->
x
<=
x)
||
(a.x
<=
x
&&
b
->
x
>=
x)))
return
true
;
}
else
{
//
水平线PP与线段ab的交点，该交点与点p间的水平相对位置
double
delta
=
(y
-
a.y)
*
(b
->
x
-
a.x)
/
(b
->
y
-
a.y)
+
a.x
-
x;
if
(delta
>=
DBL_EPSILON)
++
count;
//
水平射线PP与线段相交
else
if
(delta
>
-
DBL_EPSILON)
return
true
;
//
点p在线段ab上
}
}
return
count
&
1
;
}
int
main()
{
Point point[
3
]
=
{ {
0
,
0
}, {
0
,
4
}, {
4
,
0
}};
assert(is_in_polygon(point,
3
, Point(
0
,
0
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
0
,
4
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
4
,
0
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
-
2
,
0
))
==
0
);
assert(is_in_polygon(point,
3
, Point(
2
,
0
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
6
,
0
))
==
0
);
assert(is_in_polygon(point,
3
, Point(
0
,
-
2
))
==
0
);
assert(is_in_polygon(point,
3
, Point(
0
,
2
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
0
,
6
))
==
0
);
}
矢量同向法：（适用于凸多边形）
矢量同向法
#include
<
cstdio
>
#include
<
cmath
>
#include
<
cfloat
>
#include
<
cassert
>
struct
Vector {
double
x, y;
Vector() {}
Vector(
double
xx,
double
yy) : x(xx), y(yy) {}
double
cross(
const
Vector
&
v)
const
{
return
x
*
v.y
-
y
*
v.x; }
Vector
operator
-
(
const
Vector
&
v)
const
{
return
Vector(x
-
v.x, y
-
v.y); }
};
//
适用于凸多边形
inline
bool
is_in_polygon(
const
Vector vec[], size_t len,
const
Vector
&
v)
{
double
sum_area
=
0
, total_area
=
0
;
Vector va
=
vec[len
-
1
];
for
(
const
Vector
*
vb
=
vec; vb
<
vec
+
len; va
=
*
vb
++
) {
double
area
=
(va
-
v).cross(
*
vb
-
v);
sum_area
+=
area;
total_area
+=
fabs(area);
}
return
fabs(fabs(sum_area)
-
total_area)
<
DBL_EPSILON;
}
int
main()
{
typedef Vector Point;
Point point[
3
]
=
{ {
0
,
0
}, {
0
,
4
}, {
4
,
0
}};
assert(is_in_polygon(point,
3
, Point(
0
,
0
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
0
,
4
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
4
,
0
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
-
2
,
0
))
==
0
);
assert(is_in_polygon(point,
3
, Point(
2
,
0
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
6
,
0
))
==
0
);
assert(is_in_polygon(point,
3
, Point(
0
,
-
2
))
==
0
);
assert(is_in_polygon(point,
3
, Point(
0
,
2
))
==
1
);
assert(is_in_polygon(point,
3
, Point(
0
,
6
))
==
0
);
}
posted on 2011-07-11 22:47
flyinghearts
阅读(2192)
评论(3)
编辑
收藏
引用
所属分类:
算法
评论
#
re: 点在多边形内
2011-07-12 01:24
千暮（zblc）
mark.
回复
更多评论
#
re: 点在多边形内
2012-03-22 23:49
wywcgs
1. 还可以环顾
2. 环顾有绝妙实现可以避免浮点运算同时无精度误差。
回复
更多评论
#
re: 点在多边形内
2012-03-24 21:23
flyinghearts
@wywcgs
如果坐标是整数的话，两种方法都不需要浮点运算。
回复
更多评论
刷新评论列表
只有注册用户
登录
后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！
相关文章:
面试题: 找出数组中三个只出现一次的数
避免计算过程中出现溢出的一个技巧
Fibonacci数计算中的两个思维盲点及其扩展数列的通用高效解法
喝汽水问题
对环状数组求连续子数组的最大和
最短摘要的生成（补充）
Fibonacci数列的两种O(lgn)解法
点在三角形内 之二 （三维坐标系1）
点在多边形内
点在三角形内（1）
网站导航:
博客园
IT新闻
BlogJava
知识库
博问
管理
Powered by:
C++博客
Copyright © flyinghearts