判断一个点是否在一个三角形内，怎么做啊？？？
求判断一个点是否在一个三角形内的算法 问题点数：50、回复次数：29Top
1 楼Viali（萧杨）回复于 2003-11-03 20:52:03 得分 5
很简单，假设三角形的三个定点为A B C，任意一点为 P，则如果
面积ABC＝面积ABS＋面积ACS＋面积BCS，则S位于三角形内（包括边上）..luckTop
2 楼Viali（萧杨）回复于 2003-11-03 20:52:57 得分 0
搞错了，任意点为 S，不是P，hohoTop
3 楼dengsf（drklnk@Radical_Dreamer）回复于 2003-11-03 21:23:01 得分 5
设有两个点（X1，Y1），（X2，Y2）决定一有方向的直线，方向从（X1,Y1)->(X2,Y2)。
则对任意点（X，Y），考虑下面式子：
（Y - Y1）（X2 - X1） - （X - X1）（Y2 -Y1）
当 =0 时，表示（X，Y）在直线上面；
当 >0 时，表示（X，Y）在沿直线方向的左侧；
当 <0 时，表示（X，Y）在沿直线方向的右侧；
假设三个点按顺序输入的（顺或逆时针都行），设为（X1，Y1）（X2，Y2），（X3，Y3）。
很明显，三角形内部的点一定都在
(X1,Y1）->(X2,Y2),
(X2,Y2)->(X3,Y3),
(X3,Y3)->(X1,Y1)
的同一侧，而其它的点一定不符合要求的。
所以……Top
4 楼dengsf（drklnk@Radical_Dreamer）回复于 2003-11-03 21:27:38 得分 2
对了，好象这样应该可以推广到任意凸多边形的情况。Top
5 楼Viali（萧杨）回复于 2003-11-04 12:46:07 得分 2
PS: 上层那个式子是 “叉积”，方法有的，不过，对于简单的问题，你的方法似乎太那个了。。。Top
6 楼dengsf（drklnk@Radical_Dreamer）回复于 2003-11-04 13:15:42 得分 2
不过我觉得那方法效率比较高,运算也不多,而且比较精确.对简单的问题应该也适用.
如果用面积,就要和根式或行列式打交道,运算量似乎也不少.Top
7 楼apogeecsj（skysword）回复于 2003-11-04 13:52:43 得分 0
那计算面积时的精度问题怎么处理?(面积ABC＝面积ABS＋面积ACS＋面积BCS)Top
8 楼HUNTON（追求完美）回复于 2003-11-04 16:42:12 得分 5
问题：如何判断一点是否在一个凸多边形的内部
定义：已知三点A（x1,y1）、B（x2,y2）、C（x3,y3）
|x1 x2 x3|
则S(A,B,C) =abs( |y1 y2 y3| )
|1 1 1 |
解决：
设要判断的点为P，凸多边形为A1A2A3、、、An（顺时针或逆时针都可以），
首先计算S = S(A1,A2,A3) + S(A1,A3,A4) + 、、、+S(A1,An-1,An)
然后计算SS = S(P,A1,A2) + S(P,A2,A3) + 、、、+ S(P,An,A1)
最后判断S与SS的关系，
若S=SS，则P在该凸多边形的边上或内部
若S<SS，则P在该凸多边形的外部
S>SS的情况是不存在的。
三角形情况就是：
定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：
|x1 x2 x3|
S(P1,P2,P3) = |y1 y2 y3| = (x1-x3)*(y2-y3) - (y1-y3)(x2-x3)
|1 1 1 |
已知：三角形的三个顶点A,B,C，及平面上的一点P，
若abs( S(A,B,C) ) = abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ，则P在三角形ABC的内部或边上；
若abs( S(A,B,C) ) < abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) ，则P在三角形ABC的外部；
对abs( S(A,B,C) ) = abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) 的情况在理论上是不存在的；Top
9 楼HUNTON（追求完美）回复于 2003-11-04 16:43:50 得分 0
这哪里有什么精度问题啊，都是整数运算。Top
10 楼HUNTON（追求完美）回复于 2003-11-04 16:45:29 得分 2
最后一个式子错了，应该是：
对abs( S(A,B,C) ) > abs( S(P,B,C) ) + abs( S(A,P,C) ) + abs( S(A,B,P) ) 的情况在理论上是不存在的；
Top
11 楼LeeMaRS（小菜虎，仍需努力）回复于 2003-11-04 18:16:06 得分 5
什么方法都行了，一般的介绍的都是:判断点P是否在三角形内，则取三角形中的一点Q(一般取三角形的重心，很好算)，然后判断P、Q是否都在三角形三条边的同侧。同侧即为P在三角形内，否则P在三角形外。边上的情况也很容易处理。Top
12 楼Viali（萧杨）回复于 2003-11-04 21:35:57 得分 2
计算面积是用不着根式的，看一下《ItA》就知道了，经典Top
13 楼HUNTON（追求完美）回复于 2003-11-04 22:38:04 得分 2
判断点与三角形位置关系LeeMaRS的方法也是可以的，不过我个人觉得还是面积的方法比较简便，而且推广到凸多边形也很明了。自从俺提出该方法以来，已经很多人用了，都说很它好使，我们公司做图形的人也用了，说效果不错。Top
14 楼apogeecsj（skysword）回复于 2003-11-04 23:21:34 得分 0
计算面积好方法，up一下Top
15 楼dengsf（drklnk@Radical_Dreamer）回复于 2003-11-05 00:38:42 得分 5
我比较了一下 位置法 和 面积法。
--------------------------------------------------------
空间：
对于位置法，只需要两个变量分别记录“前一次运算结果的符号”和“当前运算结果的符号”；
对于面积法，也只需要记录“多边形面积”和“面积和”。
所以，空间占用基本一样，均为O（1）。
-------------------------------------------------------
时间：
对于位置法，对一个 凸 n 边形，最多需要 n 次运算，每次运算需要 2 次乘法 和 5 次减法。共 2n 次乘法和 5n 次减法；
对每次运算的结果，只需要判定其符号。
对于多边形的内点，要判定 n 次；对于不是内点的，平均只需要判定 n/2 次。
所以，忽略加减，平均运算次数大概是 2n*P + n(1-P)。其中P是任意一个点是多边形内点的概率。
对于面积法，对一个凸 n 边形，要计算 2 次面积。计算“面积和”共需要 5n 次减法， 2n次乘法，n次加法；计算"多边形面积"需要 5（n-1)次减法，2（n-1)次乘法，n-1次加法。
无论是否多边形的内点，面积法均需要将两个面积加起来并比较。
所以，忽略加减，平均运算次数大概是 4n-2 次。
因此，虽然两种方法都是在O（n）内，但“位置法”的系数要比“面积法”的小一半。
------------------------------------------------------------------------
精度 和 容量：
精度方面，大家都是对整数进行运算，不会有误差。
至于判定的精度，“位置法”判定结果的符号，“面积法”判定结果的相等。在没有误差的前提下，基本等价。
容量的意思，在这里是说输入的数据的值最大可以达到多少。由于两者的式子结构类似，所以很明显看出，容量不会有太大的差别。
---------------------------------------------------------------------
使用的方便：
上面几楼好象有点“位置法”相对比较繁琐的意思。可是编码起来，我觉得好象比较简单。
都是一个循环下去，里面直接套式子，最后再加一两句判断就可以了吧。编码的量也不觉得有太大的差别~~~
---------------------------------------------------------------------
综上所述，两种方法能力基本相同。但在时间方面，按照上面的分析，“位置法”略占优势。
上面对“面积法”的时间分析是直接“将多个三角行的面积相加起来”而计算的，不知道是否有更快的方法。Top
16 楼LeeMaRS（小菜虎，仍需努力）回复于 2003-11-05 00:52:30 得分 5
一般来说用"位置法"主要是因为叉乘是基本函数, 不需要再多写一个计算面积的函数, 少写一个, 就少一个可能出现错误的地方. 若是本来就需要计算面积的时候, 用"面积法"可能就更好一些.
另外这还与个人的理解有关系, 对哪种方法理解更深, 记忆更深, 就用哪种方法. 两种方法差异的那一点时间是可以忽略不计的, 呵呵. 说白了用什么法都是看自己个人爱好. 就像判断点在多边形内, 有些人偏爱射线法, 有些人偏爱角度和法.
另外计算几何一般不用整数来做, 这个应该算一个基本要求的, 为了防止溢出, 通常都是用浮点数来做的. 我当时做ZJU 1081的时候就吃了这个亏.Top
17 楼HUNTON（追求完美）回复于 2003-11-05 08:37:16 得分 2
计算几何里一般不用整数来做，但这里的面积的确算出来的只有整数（因为图形中的任意一点的坐标都是用整数来表示的），所以当然就不要再去涉及浮点运算了。但如果有碰到亚象素情况求面积，那就要用浮点运算了。Top
18 楼v_salt（加点盐）回复于 2003-11-05 19:00:11 得分 0
先建系，然后线性规划Top
19 楼EnigmaXJ（花火）回复于 2003-11-05 22:20:22 得分 0
这个很简单啊，用BSP树方法吧。Top
20 楼Viali（萧杨）回复于 2003-11-05 22:24:17 得分 0
re..^_^Top
21 楼LeeMaRS（小菜虎，仍需努力）回复于 2003-11-06 00:21:03 得分 0
呵呵, 计算几何选浮点数的原因主要是整型数据类型的范围通常都太小了. ^_^Top
22 楼Heray（Heray）回复于 2003-11-17 16:28:11 得分 0
也可以判断该点与三角形的三顶点的连线的夹角和，若等于2π，则可判断在三角形内，反之则在三角形外，特殊情况：1：该点与三角形的某一点重合，易判断；2、若有夹角为π的两条连线，则在三角形的一边上。Top
23 楼HUNTON（追求完美）回复于 2003-11-17 16:47:59 得分 0
算夹角，那要用到余弦定理或是叉积运算，然后还有除法，算出来的结果会不会有误差？Top
24 楼Heray（Heray）回复于 2003-11-17 20:23:19 得分 0
算夹角没必要这么复杂啊，可以计算每一个向量的幅角绝对值，在直角坐标系下，计算三顶点以输入点为原点的坐标，根据反三角函数和坐标值的符号，就能得到0~2π范围内的幅角值。我仔细想了一下，根本用不着计算夹角的具体值，如果在三角形以内，OA-OB,OB-OC,OC-OA三个幅角差的绝对值要么全部大于π，要么全部小于π，这点可以判断，误差也比较小Top
25 楼sclfox（冰河）回复于 2003-11-18 21:48:49 得分 0
谢谢各位的踊跃发言，我需要一种算法最快的方法，面积法最基本，算夹角很有新意，位置法似乎是目前认为最好的。我再仔细比较比较。Top
26 楼SimonSui（！熵、焓、自由能！）回复于 2003-11-19 08:40:49 得分 0
可不可以算最近三点与该点连线,若凸多边形所有点都在连线同侧,点就在多边形外侧Top
27 楼caohoujie（）回复于 2003-11-21 17:01:17 得分 1
我试了一下，两种方法都行。
可计算几何上写着用射线法啊！
你们都没有看过吗？
不用作一堆乘法减法什么的，
只需要很简单的比较就行了，
而且还适用于凹多边形的情况。Top
28 楼caohoujie（）回复于 2003-11-21 17:15:21 得分 0
靠！射线法看起来很麻烦的样子Top
29 楼stephen85（）回复于 2003-11-22 13:36:47 得分 5
我用射线法写的代码：
#include "iostream.h"
#include "fstream.h"
#include "stdlib.h"
//函数声明
bool Isinside(float *x,float *y,int n);
//主函数
void main()
{
int n,i;
float *x,*y;
fstream f;
f.open("input.txt",ios::in);
f>>n;
x=(float *)malloc((n+1)*sizeof(float));
y=(float *)malloc((n+1)*sizeof(float));
for(i=0;i<=n;i++)
f>>x[i]>>y[i];
if(Isinside(x,y,n))
cout<<"true";
else cout<<"false";
cout<<endl;
}
/////////////////////////////////////////
bool Isinside(float *x,float *y,int n)
{
bool *visited;
int i,j,k,count=0;
visited=(bool *)malloc((n+1)*sizeof(bool));
for(i=0;i<=n;i++)
visited[i]=false;
for(i=1;i<=n;i++)
{
if(!visited[i])
{
visited[i]=true;
float tx,ty;
j=i+1;
if(j>n) j=1;
ty=y[0];
if(y[i]==y[j])
{
if(y[i]==ty)
{
if((x[i]-x[0])*(x[j]-x[0])<=0)
return true;
}
}
else
{
tx=(x[j]-x[i])/(y[j]-y[i])*(ty-y[i])+x[i];
if((x[i]+y[i]-tx-ty)*(x[j]+y[j]-tx-ty)<0)
{
if(tx==x[0]) //该点恰在该多边形的边上
return true;
else if(tx>x[0])
count++;
}
if(x[j]==tx&&y[j]==ty)
{
if(tx==x[0])
return true;
else if(tx>x[0])
{
k=j+1;
if(k>n) k=1;
if((y[i]-ty)*(y[k]-ty)<0) //处于射线异侧
count++;
else if((y[i]-ty)*(y[k]-ty)>0) //处于射线同侧
count+=2;
else if(y[k]==ty)
{
if((x[j]-x[0])*(x[k]-x[0])<=0)
return true;
else
{
visited[k]=true;
int m=k+1;
if(m>n) m=1;
if((y[m]-ty)*(y[i]-ty)<0)
count++;
else if((y[m]-ty)*(y[i]-ty)>0)
count+=2;
}
}
}
}
}
}
}
if(count%2!=0) return true;
else return false;
}
Top
