急救：如果判断一个点在一个区域内？

Question

那位仁兄知不知道，有没有现成的算法，判断一个点是不是在一个区域内。区域最复杂为五边形，都是凸多边形。最简单为三角形，如一个三角形三点坐标为（0，0）（10，0）（7，3），怎么判断一个点是否在其区域内？最好有现成的函数库。谢谢。

Answer 1

一般的就是
BOOL PtInRect(
   POINT point 
) const throw( );

Answer 2

lixiaosan(小三) 多谢，我先试试。

Answer 3

http://astronomy.swin.edu.au/~pbourke/geometry/insidepoly/

Answer 4

但一想不对了，那个RECT是个正方形，我这里主要是三角形和五边形。

Answer 5

有这个的CRgn::PtInRegion
This method checks whether the point specified by x and y is in the region stored within the CRgn object.BOOL PtInRegion( 
int x, 
int y ) 
const; BOOL PtInRegion( 
POINT point ) 
const; 或者
BOOL PtInRegion(
  HRGN hrgn,  // handle to region
  int X,      // x-coordinate of point
  int Y       // y-coordinate of point
);一个点是否在某个区域内

Answer 6

PtInRegion是可以的，但不准用，但是现在要求自己找算法写一个出来。

Answer 7

“PtInRegion是可以的，但不准用，但是现在要求自己找算法写一个出来。”晕…………
加油…………

Answer 8

这里更有详细思路，可参考http://jane3s.blogchina.com/blog/243789.html

Answer 9

http://community.csdn.net/Expert/FAQ/FAQ_Index.asp?id=198803

Answer 10

问题：如何判断一点是否在一个凸多边形的内部定义：已知三点A（x1,y1）、B（x2,y2）、C（x3,y3）

           |x1 x2 x3|
  则S(A,B,C) =abs( |y1 y2 y3| )= (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)
           |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在该凸多边形的边上或内部
       P在第i边上的附加条件是S(P,Ai,Ai+1)=0
    若S<SS，则P在该凸多边形的外部
    S>SS的情况是不存在的。