John Jiang

a cup of Java, cheers!
https://github.com/johnshajiang/blog

   :: 首页 ::  :: 联系 :: 聚合  :: 管理 ::
  131 随笔 :: 1 文章 :: 530 评论 :: 0 Trackbacks
判定一个点是否在三角形内
如何判定一个点P是否存在于指定的三角形ABC内,这肯定是一个简单的问题,本文仅用一个图形界面程序展示了该问题,有兴趣的朋友可以看看。(2008.07.24最后更新)

在此处使用一种常见且简便的方法:如果三角形PAB,PAC和PBC的面积之和与三角形ABC的面积相等,即可判定点P在三角形ABC内(包括在三条边上)
可知,该方法的关键在于如何计算三角形的面积。幸运地是,当知道三角形顶点(A,B和C)的坐标((Ax, Ay),(Bx, By)和(Cx, Cy))之后,即可计算出其面积:
= |(Ax * By + Bx * Cy + Cx * Zy - Ay * Bx - By * Cx - Cy * Ax) / 2|

关键的代码如下,
// 由给定的三个顶点的坐标,计算三角形面积。
// Point(java.awt.Point)代表点的坐标。
private static double triangleArea(Point pos1, Point pos2, Point pos3) {
    
double result = Math.abs((pos1.x * pos2.y + pos2.x * pos3.y + pos3.x * pos1.y
            
- pos2.x * pos1.y - pos3.x * pos2.y - pos1.x * pos3.y) / 2.0D);
    
return result;
}

// 判断点pos是否在指定的三角形内。
private static boolean inTriangle(Point pos, Point posA, Point posB,
        Point posC) {
    
double triangleArea = triangleArea(posA, posB, posC);
    
double area = triangleArea(pos, posA, posB);
    area 
+= triangleArea(pos, posA, posC);
    area 
+= triangleArea(pos, posB, posC);
    
double epsilon = 0.0001;  // 由于浮点数的计算存在着误差,故指定一个足够小的数,用于判定两个面积是否(近似)相等。
    if (Math.abs(triangleArea - area) < epsilon) {
        
return true;
    }
    
return false;
}

执行该应用程序,用鼠标在其中点击三次,即可绘制一个三角形,如下组图所示:

然后仅需移动鼠标,就会出现一个空心圆圈。如果圆圈的中心在三角内(包含在三条边上),则圆圈显示为红色;否则,显示为蓝色。如下组图所示:


完整代码如下:
public class CanvasPanel extends JPanel {

    
private static final long serialVersionUID = -6665936180725885346L;

    
private Point firstPoint = null;

    
private Point secondPoint = null;

    
private Point thirdPoint = null;

    
public CanvasPanel() {
        setBackground(Color.WHITE);
        addMouseListener(mouseAdapter);
        addMouseMotionListener(mouseAdapter);
    }

    
public void paintComponent(Graphics g) {
        
super.paintComponent(g);
        drawTriangel(g);
    }

    
private void drawTriangel(Graphics g) {
        
if (firstPoint != null && secondPoint != null) {
            g.drawLine(firstPoint.x, firstPoint.y, secondPoint.x, secondPoint.y);
            
if (thirdPoint != null) {
                g.drawLine(firstPoint.x, firstPoint.y, thirdPoint.x, thirdPoint.y);
                g.drawLine(secondPoint.x, secondPoint.y, thirdPoint.x, thirdPoint.y);
            }
        }
    }

    
private static boolean inTriangle(Point pos, Point posA, Point posB,
            Point posC) {
        
double triangeArea = triangleArea(posA, posB, posC);
        
double area = triangleArea(pos, posA, posB);
        area 
+= triangleArea(pos, posA, posC);
        area 
+= triangleArea(pos, posB, posC);
        
double epsilon = 0.0001;
        
if (Math.abs(triangeArea - area) < epsilon) {
            
return true;
        }
        
return false;
    }

    
private static double triangleArea(Point pos1, Point pos2, Point pos3) {
        
double result = Math.abs((pos1.x * pos2.y + pos2.x * pos3.y + pos3.x * pos1.y
                           
- pos2.x * pos1.y - pos3.x * pos2.y - pos1.x * pos3.y) / 2.0D);
        
return result;
    }

    
private MouseInputAdapter mouseAdapter = new MouseInputAdapter() {

        
public void mouseReleased(MouseEvent e) {
            Point pos 
= e.getPoint();
            
if (firstPoint == null) {
                firstPoint 
= pos;
            } 
else if (secondPoint == null) {
                secondPoint 
= pos;
                Graphics g 
= CanvasPanel.this.getGraphics();
                CanvasPanel.
this.paintComponent(g);
                g.drawLine(firstPoint.x, firstPoint.y, secondPoint.x, secondPoint.y);
            } 
else if (thirdPoint == null) {
                thirdPoint 
= pos;
                Graphics g 
= CanvasPanel.this.getGraphics();
                CanvasPanel.
this.paintComponent(g);
                g.drawLine(firstPoint.x, firstPoint.y, secondPoint.x, secondPoint.y);
                g.drawLine(firstPoint.x, firstPoint.y, thirdPoint.x, thirdPoint.y);
                g.drawLine(secondPoint.x, secondPoint.y, thirdPoint.x, thirdPoint.y);
            }
        }

        
public void mouseMoved(MouseEvent e) {
            Point pos 
= e.getPoint();
            Graphics2D g2 
= (Graphics2D) CanvasPanel.this.getGraphics();
            CanvasPanel.
this.paintComponent(g2);
            
if (firstPoint != null && secondPoint == null) {
                g2.drawLine(firstPoint.x, firstPoint.y, pos.x, pos.y);
            } 
else if (firstPoint != null && secondPoint != null && thirdPoint == null) {
                g2.drawLine(firstPoint.x, firstPoint.y, pos.x, pos.y);
                g2.drawLine(secondPoint.x, secondPoint.y, pos.x, pos.y);
            } 
else if (firstPoint != null && secondPoint != null && thirdPoint != null) {
                
if (inTriangle(pos, firstPoint, secondPoint, thirdPoint)) {
                    g2.setColor(Color.RED);
                } 
else {
                    g2.setColor(Color.BLUE);
                }
                
int radius = 4;
                g2.drawOval(pos.x 
- radius, pos.y - radius, radius * 2, radius * 2);
            }
        }
    };
}

public class Triangle extends JFrame {

    
private static final long serialVersionUID = 1L;

    
private CanvasPanel mainPanel = null;

    
public Triangle() {
        setTitle(
"Triangle");
        setSize(
new Dimension(300200));
        setResizable(
false);

        init();

        Container container 
= getContentPane();
        container.add(mainPanel);

        setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        setVisible(
true);
    }

    
private void init() {
        mainPanel 
= new CanvasPanel();
    }

    
public static void main(String[] args) {
        
new Triangle();
    }
}

posted on 2008-07-24 17:02 John Jiang 阅读(7841) 评论(13)  编辑  收藏 所属分类: JavaSEJavaSwingGUIAlgorithm原创

评论

# re: 判定一个点是否在三角形内(原) 2008-07-24 22:09 qiyadeng
似乎有更好的方法。  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2008-07-25 13:59 长老
学过计算机图形学的都知道, 计算机图形中判断一个点是否在一条直线上, 或三角内, 根本不必要像几何数学中这么精确. 最典型的, 一般都是把点用小正方形表示, 而不是圆, 这样算法大大简化了. 所以上面的情况, 也有更简单好用的算法.  回复  更多评论
  

# re: 判定一个点是否在三角形内(原)[未登录] 2008-07-27 10:27 nile black
楼主至少提出了一种方法  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2008-07-27 20:40 Sha Jiang
> 学过计算机图形学的都知道, 计算机图形中判断一个点是否在一条直线上,
> 或三角内, 根本不必要像几何数学中这么精确.
我这里就是把它当几何问题来处理的。

此处使用的面积法,原理容易理解,也很容易用程序实现。
还可利用线段PA,PB和PC的"走势"来做判断。当然,仍然是基于几何学 :-)  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2008-10-16 01:08 Fu
如果已经知道三角形三个顶点的坐标,如何判断另一点是否在这个三角形内呢?
谢谢!  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2008-10-16 07:52 Sha Jiang
> 如果已经知道三角形三个顶点的坐标,如何判断另一点是否在这个三角形内呢?
这不正是我的这篇Blog所涉及的内容嘛 :-  回复  更多评论
  

# re: 判定一个点是否在三角形内(原)[未登录] 2009-08-21 11:50 zhang
当一个点与一条边的距离十分近的时候,该方法不成立!我在实际应用中使用过  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2009-08-21 18:13 Sha Jiang
> 当一个点与一条边的距离十分近的时候,该方法不成立!我在实际应用中使用过
就算移动的点在某条边上,该方法仍然没有问题啊。  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2009-11-08 04:49 ucdavis
http://www.blackpawn.com/texts/pointinpoly/default.html  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2010-01-28 22:54 eee
三角形ABC,点P。用AB表示从A到B的矢量,用<AB>表示AB/|AB|, 用(X,Y)表示矢量X和矢量Y的内积。如果(<BP>,<BC>)*(<BC>,<BA>)<=(<BP>,<BA>),且(<CP>,<CB>)*(<CB>,<CA>)<=(<CP>,<CA>),则P在三角形ABC内部或在其边上。  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2010-01-29 01:36 eee
三角形ABC,点P。用AB表示从A到B的矢量,用<AB>表示AB/|AB|, 用(X,Y)表示矢量X和矢量Y的内积。如果(<BP>,<BC>)*(<BC>,<BA>)<(<BP>,<BA>),且(<BP>,<BA>)*(<BA>,<BC>)<(<BP>,<BC>),且(<CP>,<CA>)*(<CA>,<CB>)<(<CP>,<CB>),则P在三角形ABC内部。【【更正】】  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2011-04-21 15:39 Patronum
ucdavis给的那个链接上的方法只需要12次浮点数乘法,而楼主的方法需要24次浮点数乘法,加法次数也是楼主的方法比较多,所以相对而言,还是采取连接中给的方法比较好,叉积判定法。  回复  更多评论
  

# re: 判定一个点是否在三角形内(原) 2011-04-21 15:40 Patronum
不过楼主的方法相对容易理解,这一点必须承认。  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: