项目5 判断点是否在圆内

• 请编写一个Java应用程序，判断给定的平面点坐标(x1,y1)是否在一个指定半径的圆内。程序先请求输入圆的半径，再请求输入点的x坐标和y坐标，然后给出判断点是否在圆内并打印输出结果。假定圆心的位置在坐标原点(0,0)，在圆上的点也被认为是在圆内。点到圆心的距离计算可以参考之前的DistanceBetweenTwoPoints.java源程序文件。当一个点判断完毕后，程序给出操作选择提示信息：是否继续判断还是退出程序。
  本项目要求实现三个方法：calculateDistance()方法用来计算两个点之间的距离，返回两点间的距离值；isInCircle()方法用来判断点是否在圆内，通过比较圆心到点的距离和指定的半径值返回true或false的结果；printResult()方法根据isInCircle()方法的返回结果输出相应的信息。

• 参考代码：

  package FifthProject;
  
  import java.util.Scanner;
  
  public class LuoYu_5 {
      public static void main(String[] args) {
          Scanner input = new Scanner(System.in);
          System.out.print("What is the radius of the circle? ");
          double radius = input.nextDouble();
          System.out.print("\nEnter the x coordinate: ");
          double x = input.nextDouble();
          System.out.print("Enter the y coordinate: ");
          double y = input.nextDouble();
          System.out.printf("The point (%.2f,%.2f), ",x,y);
          printResult(x,y,radius);
          int flag = -1;
          System.out.print("Enter 0 to exit or 1 to continue: ");
          while ((flag = input.nextInt()) == 1){
              System.out.print("Enter the x coordinate: ");
              x = input.nextDouble();
              System.out.print("Enter the y coordinate: ");
              y = input.nextDouble();
              System.out.printf("The point (%.2f,%.2f), ",x,y);
              printResult(x,y,radius);
              System.out.print("Enter 0 to exit or 1 to continue: ");
          }
      }
  
      public static double calculateDistance(double x,double y){
          return Math.sqrt(x * x + y * y);
      }
      public static boolean islnCircle(double x,double y,double patterndisance) {
          if (calculateDistance(x,y) > patterndisance) {
              return false;
          }
          else
              return true;
      }
  
      public static void printResult(double x,double y,double p){
          if (islnCircle(x,y,p))
              System.out.printf("is in of the circle with radius %.2f\n\n",p);
          else
              System.out.printf("is out the circle with radius %.2f\n\n",p);
      }
  }
  
  

• 结果显示：

  What is the radius of the circle? 27
  
  Enter the x coordinate: 22
  Enter the y coordinate: 26
  The point (22.00,26.00), is out the circle with radius 27.00
  
  Enter 0 to exit or 1 to continue: 1
  Enter the x coordinate: 17
  Enter the y coordinate: 22
  The point (17.00,22.00), is out the circle with radius 27.00
  
  Enter 0 to exit or 1 to continue: 1
  Enter the x coordinate: 5
  Enter the y coordinate: 7
  The point (5.00,7.00), is in of the circle with radius 27.00
  
  Enter 0 to exit or 1 to continue: 0
  
  Process finished with exit code 0
  
  

我们在下面的介绍中，只讨论三种图形，分别是矩形（包括正方形）、椭圆（包括圆）和多边形。对于矩形和椭圆，比较常见的描述方法是(x,y,w,h)，另外再加一个旋转角度a（绕中心旋转）。而对于多边形，一般的描述方法是一个二维点的数组。事实上矩形也是多边形（四边形），因为它的描述方法不一样，所以我们分开讨论。

一、无旋转矩形

 这是最简单的一种情况，判断方法也简单。只要判断点的横坐标是否在[x,x+w]、纵坐标是否是[y,y+h]内即可。

二、旋转矩形

 对于旋转矩形，比较常规的做法是：

1、求出未旋转状态下的四个顶点。

2、算出四个顶点绕中心旋转后的坐标。

3、用判断多边形的方法（后面才介绍呢），算出点是否在这个四边形内。

很容易看出，这个方法要做4次旋转计算，以及1次多边形边界计算。事实上，我们有更好的方法。

其实可以转换一下思维，把要判断的点，绕矩形中心，以相反方向旋转，再跟未旋转的矩形相比较即可。这种方法只需要做1次旋转计算，而且是否在未旋转矩形内的判断是很简单的。

三、旋转椭圆

我们知道，最简单的椭圆方程是：

 它是一个以原点为中心，以2a为长轴，以2b为短轴的椭圆。对于这个椭圆，如果代入一个点P(x,y)，使得C>1，那么P在椭圆外，反之，如果C<1，那么P在椭圆内。

所以，我们只要求出在(x,y,w,h,a)这种描述下的椭圆方程即可。

我们令：

ca = w / 2;
cb = h / 2;
dx = x + ca;
dy = y + cb;
sin = sin(a);
cos = cos(a);
rx = px - dx;
ry = py - dy;

那么椭圆方程是：

四、多边形

 判断一个点是否在多边形内的核心思想是，由点向任意方向引出一条射线，如果点跟多边形的交点为奇数，则点在多边形内，如果为偶数，则点在多边形外。

下面的代码可完成这一功能：

bool InPolygon(Point point, Point[] polygon)
{
    bool _in = false;
    for (int i = 0, j = polygon.Length - 1; i < polygon.Length; j = i++)
    {
        if (((polygon[i].Y > point.Y) != (polygon[j].Y > point.Y)) &&
            (point.X < (polygon[j].X - polygon[i].X) * (point.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) + polygon[i].X))
            _in = !_in;
    }
    return _in;
}

简述

在网上看到了很多种方法来判断“点是否在多边形内部”，最终选择了一种简单易懂，且适合所有多边形的方法--水平/垂直交叉点数判别法。

方法

如果从点P作水平向左的射线的话，假设P在多边形内部，那么这条射线与多边形的交点必为奇数，如果P在多边形外部，则交点个数必为偶数（0也在内）。所以，我们可以顺序（顺时针或逆时针）考虑多边形的每条边，求出交点的总个数。还有一些特殊情况要考虑。假如考虑边(P1,P2)，
1) 如果射线正好穿过P1或者P2,那么这个交点会被算作2次，处理办法是如果P的从坐标与P1,P2中较小的纵坐标相同，则直接忽略这种情况
2) 如果射线水平，则射线要么与其无交点，要么有无数个，这种情况也直接忽略。
3) 如果射线竖直，而P的横坐标小于P1,P2的横坐标，则必然相交。
4) 再判断相交之前，先判断P是否在边(P1,P2)的上面，如果在，则直接得出结论：P再多边形内部。

//作用：判断点是否在多边形内
//p指目标点， ptPolygon指多边形的点集合， nCount指多边形的边数
int BlobDetect::PtInPolygon (Point p, vector<cv::Point>& ptPolygon, int nCount)  
{  
	// 交点个数  
	int nCross = 0;  
	for (int i = 0; i < nCount; i++)   
	{  
		Point p1 = ptPolygon[i];  
		Point p2 = ptPolygon[(i + 1) % nCount];// 点P1与P2形成连线  

		if ( p1.y == p2.y )  
			continue;  
		if ( p.y < min(p1.y, p2.y) )  
			continue;  
		if ( p.y >= max(p1.y, p2.y) )  
			continue;  
		// 求交点的x坐标（由直线两点式方程转化而来）   

		double x = (double)(p.y - p1.y) * (double)(p2.x - p1.x) / (double)(p2.y - p1.y) + p1.x;  

		// 只统计p1p2与p向右射线的交点  
		if ( x > p.x )  
		{  
			nCross++;  
		}  

	}  

	// 交点为偶数，点在多边形之外  
	// 交点为奇数，点在多边形之内
	if ((nCross % 2) == 1)
	{
		g_proj_log.ShowInfo("点在区域内");
		return BLOB_OK;
	}
	else
	{
		g_proj_log.ShowInfo("点在区域外");
		return BLOB_FAIL;
	}
} 

附上直线两点式方程式，如下图： 

最后，附上一篇我看到的关于“点在多边形内部”的博客，有兴趣的话可以研究下 。相关链接