c++ 怎么判断一个点在三角形内

来源:百度知道 编辑:UC知道 时间:2024/09/23 20:47:36
已知三角形3点(x1,y1),(x2,y2),(x3,y3)和任意1点(x,y),怎么用程序判断点(x,y)在三角形内

我有个想法,就是先判断该点是否在三角形上,如过是就不用在判断了,否则从该点做一条平行于x轴的射线,判断此射线与三角形的边有几个交点,如果是一个,则在三角形内,如果是0个或2个则在三角形外。

可以用一个点类,来产生三个点,再求出三点中横坐标最大和最小的两个点,再和第四点横坐标比较,只要第四点小于最大横坐标,大于最小横坐标,并且纵坐标小于最大纵坐标和大于最小纵坐标,就可以判断该点在这个三角形里。否则不在

一楼说的没错,这样讲会把人家吓跑的。这个问题太简单了,不需要很高深的算法。
二楼的做法错,考察三角形(0,0),(0,3),(3,0)。点(2,2)在三角形外!
三楼的说法基本正确,但是判断实数相等不是那么容易的噢,由其是(x,y)非常靠近某一边的时候很可能会由于舍入误差造成判断错误。(这个问题有一些办法来处理,但是需要用到比较高深的知识)
我的做法在下面的链接里,本质上和三楼的方法一样,也没有去处理舍入误差的影响。但是至少实数和0比大小比一般两个实数判断相等要容易一些。

该点与任意2顶点分别围成的3个三角形面积和,等于原三角形面积则在其内,否则在其外。

这个问题属于计算机图形学的范畴了,
比如多边形的填充里面的扫描线算法,种子填充算法;线或者多边形的裁剪问题等等,就是专门研究这类判断两个对象之间的位置问题。