微信

使用微信服务,更方便

职友集>程序员面试题 > 图形算法题

图形算法题

2015-04-09 06:30:01 阅读( 106 )

414人 收藏本页

标签:程序员面试题

1 如何判断一个点是否在一个多边形内?
提示:对多边形进行分割,成为一个个三角形,判断点是否在三角形内。

一个非常有用的解析几何结论:如果P2(x1,y1), P2(x2,y2), P3(x3,y3)是平面上的3个点,那么三角形P1P2P3的面积等于下面绝对值的二分之一:
| x1 y1 1 |
| x2 y2 1 | = x1y2 + x3y1 + x2y3 – x3y2 – x2y1 – x1y3
| x3 y3 1 |
当且仅当点P3位于直线P1P2(有向直线P1->P2)的右侧时,该表达式的符号为正。这个公式可以在固定的时间内,检查一个点位于两点确定直线的哪侧,以及点到直线的距离(面积=底*高/2)。

这个结论:可以用来判断点是否在点是否在三角形内。法1:判断点和三角形三边所行程的3个三角形的面积之和是否等于原来三角形的面积。(用了三次上面的公式)。
法2:判断是否都在三条边的同一边,相同则满足,否则不在三角形内。

2 给出两个n为向量与0点形成角的角平分线。
提示:对两条边进行归一化,得到长度为1的两点,取两个的中点即可。

来自分智网

下一篇:南京-乐天堂面试题

上一篇:常见算法笔试或面试题

亲~ 如果您有更好的答案 可在评论区发表您独到的见解。

您想查看更多的信息: 面试题