华为oj 之 判断点是否在三角形内

/*
* 任意顶点为A、B、C的三角形,如果点P在三角形内,那么
* 1)点P和点C在AB边的同一侧 2)点P和点A在BC边的同一侧 3)点P和点B在AC边的同一侧
* 反之亦然(充要条件)
*
* 关键:如何判断某两个点在某条直线的同一侧
*    参考图示发现:
*        对于点P: AB*BC的方向 和 AB*BP的方向相同
*        对于点P1: AB*BC的方向 和 AB*BP1的方向不同
*    故:对于边AB,以及点C、P,如果AB*BC的方向 和 AB*BP的方向相同,
*        那么点P和C在边AB的同一侧。
*/

1 public class POINT {
2     int x;
3     int y;
4     public POINT(int x,int y)
5     {
6         this.x=x;
7         this.y=y;
8     }
9 }
 1 public class Main {
 2
 3     /*
 4      *      求叉积   正:Z轴正向 ;负:Z轴负向;绝对值:叉积的模(以两个向量为边的平行四边形的面积)
 5      *      eg : 求a*b  向量a = (x1, y1, z1) 向量b = (x2, y2, z2)
 6      *           因为a和b在三角形中,所以z1 = 0、z2 = 0,
 7      *           所以 |a*b| = |x1·y2 - x2·y1|
 8      *           详见:https://zh.wikipedia.org/zh/%E5%90%91%E9%87%8F%E7%A7%AF
 9      */
10     private static int crossProduct(POINT A, POINT B, POINT C, POINT D) {
11         int x1 = B.x - A.x;
12         int y1 = B.y - A.y;
13
14         int x2 = D.x - C.x;
15         int y2 = D.y - C.y;
16
17         return (x1*y2 - x2*y1);
18     }
19
20     // 叉积得到的方向是否相同 true:方向相同;false:方向不同
21     private static boolean isSameDirection(POINT A, POINT B, POINT C, POINT P) {
22         int Direction1 = crossProduct(A, B, B, C);
23         int Direction2 = crossProduct(A, B, B, P);
24         if (Direction1*Direction2 >= 0) { // 等于0:两个向量平行 (说明P点在三角形的AB边上)
25             return true;
26         }
27         return false;
28     }
29
30     // 判断P点是否在顶点为A、B、C的三角形内(在三角形的边上,也视作在三角形中)
31     public static  boolean isInTriangle(POINT A, POINT B, POINT C, POINT P)
32     {
33         if (isSameDirection(A, B, C, P) && isSameDirection(B, C, A, P) && isSameDirection(C, A, B, P)) {
34             return true;
35         }
36         return false;
37     }
38
39     public static void main(String[] args) {
40
41         POINT A=new POINT(0,0);
42         POINT B=new POINT(0,80);
43         POINT C=new POINT(80,0);
44         POINT P=new POINT(20,60);
45         boolean b1 = isInTriangle(A, B, C, P);  // true
46
47         POINT A2=new POINT(0,0);
48         POINT B2=new POINT(0,80);
49         POINT C2=new POINT(80,0);
50         POINT P2=new POINT(21,60);
51         boolean b2 = isInTriangle(A2, B2, C2, P2);  // false
52
53
54         String result = null;
55         System.out.println(result);
56     }
57 }
时间: 01-10

华为oj 之 判断点是否在三角形内的相关文章

判断点是否在三角形内【转】

概述 给定三角形ABC和一点P(x,y,z),判断点P是否在ABC内.这是游戏设计中一个常见的问题.需要注意的是,这里假定点和三角形位于同一个平面内. 本文介绍三种不同的方法,由浅入深 一 内角和法 连接点P和三角形的三个顶点得到三条线段PA,PB和PC,求出这三条线段与三角形各边的夹角,如果所有夹角之和为180度,那么点P在三角形内,否则不在,此法直观,但效率低下. 二 同向法 假设点P位于三角形内,会有这样一个规律,当我们沿着ABCA的方向在三条边上行走时,你会发现点P始终位于边AB,BC和

判断点是否在三角形内

http://www.cnblogs.com/graphics/archive/2010/08/05/1793393.html#!comments 本文只是翻译和整理,原文在此http://www.blackpawn.com/texts/pointinpoly/default.html 概述 给定三角形ABC和一点P(x,y,z),判断点P是否在ABC内.这是游戏设计中一个常见的问题.需要注意的是,这里假定点和三角形位于同一个平面内. 本文介绍三种不同的方法,由浅入深 一 内角和法 连接点P和三

2D空间中判断一点是否在三角形内

本来打算做三角形填充多边形,但需要用到耳切法正在看.所以先研究了这个 要注意如果是XY坐标轴的2D空间,要取差乘分量z而不是y. 实现原理是,将三角形ABC三个边(AB,BC,CA)分别与比较点判断差乘,如果这3个差乘结果表示的方向一致,说明就在三角形内. 效果: 代码(Unity3D): using UnityEngine; using System.Collections; using System.Collections.Generic; public class TriangleColl

【华为OJ】【094-多线程】

[华为OJ][算法总篇章] [华为OJ][094-多线程] [工程下载] 题目描述 问题描述:有4个线程和1个公共的字符数组.线程1的功能就是向数组输出A,线程2的功能就是向字符输出B, 线程3的功能就是向数组输出C,线程4的功能就是向数组输出D.要求按顺序向数组赋值ABCDABCDABCD, ABCD的个数由线程函数1的参数指定. 输入描述: 输入一个int整数 输出描述: 输出多个ABCD 输入例子: 10 输出例子: ABCDABCDABCDABCDABCDABCDABCDABCDABCD

【华为OJ】【091-数据分类处理】

[华为OJ][算法总篇章] [华为OJ][091-数据分类处理] [工程下载] 题目描述 信息社会,有海量的数据需要分析处理,比如公安局分析身份证号码.QQ用户.手机号码.银行帐号等信息及活动记录. 采集输入大数据和分类规则,通过大数据分类处理程序,将大数据分类输出. 输入描述: ?一组输入整数序列I和一组规则整数序列R,I和R序列的第一个整数为序列的个数(个数不包含第一个整数):整数范围为0~0xFFFFFFFF,序列个数不限 输出描述: ?从R依次中取出R<i>,对I进行处理,找到满足条件

【华为OJ】【083-计算字符串的相似度】

[华为OJ][算法总篇章] [华为OJ][083-计算字符串的相似度] [工程下载] 题目描述 对于不同的字符串,我们希望能有办法判断相似程度,我们定义了一套操作方法来把两个不相同的字符串变得相同,具体的操作方法如下: 1 修改一个字符,如把"a"替换为"b". 2 增加一个字符,如把"abdd"变为"aebdd". 3 删除一个字符,如把"travelling"变为"traveling"

【华为OJ】【076-蛇形矩阵】

[华为OJ][算法总篇章] [华为OJ][076-蛇形矩阵] [工程下载] 题目描述 题目说明 蛇形矩阵是由1开始的自然数依次排列成的一个矩阵上三角形. 样例输入 5 样例输出 1 3 6 10 15 2 5 9 14 4 8 13 7 12 11 输入描述 输入正整数N(N不大于100) 输出描述 输出一个N行的蛇形矩阵. 输入例子 4 输出例子 1 3 6 10 2 5 9 4 8 7 算法实现 import java.util.Scanner; /** * Author: 王俊超 * Da

【华为OJ】【038-iNOC产品部-杨辉三角的变形】

[华为OJ][算法总篇章] [华为OJ][038-iNOC产品部-杨辉三角的变形] [工程下载] 题目描述 1 1 1 1 1 2 3 2 1 1 3 6 7 6 3 1 1 4 10 16 19 16 10 4 1 以上三角形的数阵,第一行只有一个数1,以下每行的每个数,是恰好是它上面的数,左上角数到右上角的数,3个数之和(如果不存在某个数,认为该数就是0). 求第n行第一个偶数出现的位置.如果没有偶数,则输出-1.例如输入3,则输出2,输入4则输出3. 输入n(n <= 1000000000

【华为OJ】201301 JAVA 题目0-1级 将数组分为相等的两组

描述:  编写一个函数,传入一个int型数组,返回该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),能满足以上条件,返回true:不满足时返回false. 知识点: 语言基础,字符串,循环,函数,指针,枚举,位运算,结构体,联合体,文件操作,递归    题目来源: 内部整理  练习阶段: 初级  运行时间限制: 10Sec 内存限制: 128MByte 输入: 输入输入的数据个数 输入一个int型数组 输出: 返