首页 > 试题广场 >

判断一个点是否在三角形内部

[编程题]判断一个点是否在三角形内部
  • 热度指数:1703 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
在二维坐标系中,所有的值都是double类型,那么一个三角形可以由3个点来代表,给定3个点代表的三角形,再给定一个点(x, y),判断(x, y)是否在三角形中


输入描述:
输入有四行,每行两个浮点数。

前三行的6个数分别代表三角形的三个顶点的坐标

最后两个数分别表示(x, y)


输出描述:
若(x, y)在三角形中,输出"Yes"

否则输出"No"
示例1

输入

-1.00 0.00
1.50 3.50
2.73 -3.12
1.23 0.23

输出

Yes

说明

样例中的图形大致如下

示例2

输入

-1.00 0.00
1.50 3.50
2.73 -3.12
2333.33 233333.33

输出

No

备注:
#include <bits/stdc++.h>
using namespace std;

struct P{
    double x,y;
};

double F(P a, P b){
    return acos((a.x*b.x+a.y*b.y)/(sqrt(a.x*a.x+a.y*a.y)*sqrt(b.x*b.x+b.y*b.y)));
}

int main(){
    P p[4], d[3];
    for(int i=0;i<4;i++)
        cin>>p[i].x>>p[i].y;
    for(int i=0;i<3;i++){
        d[i].x = p[i].x - p[3].x;
        d[i].y = p[i].y - p[3].y;
    }
    double a = F(d[0], d[1]);
    double b = F(d[1], d[2]);
    double c = F(d[2], d[0]);
    if(abs((a+b+c) - 2*acos(-1)) < 1e-6)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}

发表于 2020-03-09 01:12:54 回复(0)
#include<iostream>
using namespace std;
struct point {
public:
	double x, y;
	point& operator-(point& q) {
		point* p = new point();
		p->x = x - q.x;
		p->y = y - q.y;
		return *p;
	}
};
double crossZ(point p, point q) {
	return p.x * q.y - p.y * q.x;
}
int main() {
	point p, a, b, c;
	cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y;
	cin >> p.x >> p.y;

	point la = b - a, lb = c - b, lc = a - c;
	int j = crossZ(p - a, la), k = crossZ(p - b, lb), l = crossZ(p - c, lc);
	if ((l > 0 && j > 0 && k > 0) || (l < 0 && j < 0 && k < 0))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

精度不知道怎么办了
发表于 2022-08-14 21:56:09 回复(0)
#include <iostream>
#include <cmath>
using namespace std;

struct Point
{
	double x;
	double y;
	Point(double x = 0.0, double y = 0.0) : x(x), y(y) {}
};

bool IsAntiClockwise(const Point& p1, const Point& p2, const Point& p3)
{
	// 利用叉乘判断 如果p1 p2 p3 三个是逆时针顺序 
	// 即p3在p1 p2右侧 那么 p1p2 × p1p3 > 0
	// a × b = axby - aybx
	// p1p2 = (p2.x - p1.x, p2.y - p1.y)
	// p1p3 = (p3.x - p1.x, p3.y - p1.y)
	return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x) > 0;
}

bool inTriangle(const Point& p1, const Point& p2, const Point& p3, const Point& o)
{
	// 确保p1 p2 p3 是一个逆时针顺序
	if (!IsAntiClockwise(p1, p2, p3)) return inTriangle(p1, p3, p2, o);
	return IsAntiClockwise(p1, p2, o) && IsAntiClockwise(o, p2, p3) && IsAntiClockwise(o, p3, p1);
}

int main()
{
	Point p1, p2, p3, o;
	// cout << "plz enter point p1 as x y : ";
	cin >> p1.x >> p1.y;
	// cout << "plz enter point p2 as x y : ";
	cin >> p2.x >> p2.y;
	// cout << "plz enter point p3 as x y : ";
	cin >> p3.x >> p3.y;
	// cout << "plz enter point o as x y : ";
	cin >> o.x >> o.y;
	if (inTriangle(p1, p2, p3, o))
		cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

发表于 2022-08-11 15:24:07 回复(0)
假设,三角形其中一条边的两个端点为(x1,y1)和(x2,y2),待判断位置的点为(x,y),通过向量(x2-x1,y2-y1)和(x-x1,y-y1)叉积的符号可以判断点(x,y)与向量(x2-x1,y2-y1)的位置关系(大于0为顺时针方向,小于0逆时针方向,等于0为共线)
如果点(x,y)对于三角形任意一条边的向量都位于同一侧,则点在三角形内。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        int i = 0;
        // 三角形三个顶点的坐标以及待判断点的坐标
        double[] x = new double[4];
        double[] y = new double[4];
        while((line = br.readLine()) != null){
            String[] params = line.trim().split(" ");
            x[i] = Double.parseDouble(params[0]);
            y[i] = Double.parseDouble(params[1]);
            i ++;
        }
        // 看待检测点是否在三角形三条边的同一方向即可
        int res = Math.abs(crossProduct(x[0], y[0], x[1], y[1], x[3], y[3]) + crossProduct(x[1], y[1], x[2], y[2], x[3], y[3]) + crossProduct(x[2], y[2], x[0], y[0], x[3], y[3]));
        if(res == 3)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
    
    private static int crossProduct(double x1, double y1, double x2, double y2, double x, double y) {
        x2 -= x1;
        y2 -= y1;
        x -= x1;
        y -= y1;
        double crossRes = x * y2 - x2 * y;
        if(crossRes > 0)
            return 1;
        else if(crossRes < 0)
            return -1;
        else
            return 0;
    }
}
这里说明一下为什么通过向量a=(x2-x1,y2-y1)和b=(x-x1,y-y1)叉积的符号可以判断点(x,y)与向量(x2-x1,y2-y1)的位置关系。
由于a×b=|a||b|sinθ,不妨设θ表示向量a顺时针旋转到b的角度,如果sinθ<0,表示旋转超过了180°,相当于b向量的终点在a向量的逆时针侧,sinθ>0时在顺时针侧,sinθ=0时表示旋转了0°或180°,是共线的。同样地,θ表示向量a时针旋转到b的角度也可以得到类似的结论。
编辑于 2021-07-13 09:20:56 回复(0)
#$$头像 #$$
叉乘判断方向
#include <iostream>
using namespace std;
struct node {
    double x, y;
    double operator ^(node b) {
        return x * b.y - y * b.x;
    }
    node operator - (node b) {
        node ans;
        ans.x = x - b.x;
        ans.y = y - b.y;
        return ans;
    }
}a[7];
int main()
{
    node Temp;
    for (int i = 1;i <= 3;i++)
    {
        cin >> a[i].x >> a[i].y;
     }
    cin >> Temp.x >> Temp.y;
    node ab = a[2] - a[1];
    node bc = a[3] - a[2];
    node ba = a[1] - a[3];
    
    node aT = a[1] - Temp;
    node bT = a[2] - Temp;
    node cT = a[3] - Temp;
    double one = ab ^ aT;
    double two = bc ^ bT;
    double three = ba ^ cT;
    if ( (one > 0 && two > 0 && three > 0) || (one < 0 && two < 0 && three < 0))
    {
        cout << "Yes" << endl;
    }
    else 
    {
        cout << "No" << endl;
    }
   
}


发表于 2020-07-28 10:30:04 回复(0)
use std::io::{prelude::*, BufReader};

pub fn main() {
    let mut triangle_and_point: Vec<Vec<f32>> = vec![];
    read_triangle_and_point(&mut triangle_and_point);
    
    let point_a = (triangle_and_point[0][0], triangle_and_point[0][1]);
    let point_b = (triangle_and_point[1][0], triangle_and_point[1][1]);
    let point_c = (triangle_and_point[2][0], triangle_and_point[2][1]);
    let point = (triangle_and_point[3][0], triangle_and_point[3][1]);
    
    let vec_ab = (point_b.0 - point_a.0, point_b.1 - point_a.1);
    let vec_bc = (point_c.0 - point_b.0, point_c.1 - point_b.1);
    let vec_ca = (point_a.0 - point_c.0, point_a.1 - point_c.1);
    
    let ans = 
        is_ipsilateral(vec_ab, 
            (point.0 - point_a.0, point.1 - point_a.1), 
            (point_c.0 - point_a.0, point_c.1 - point_a.1)) &&
        is_ipsilateral(vec_bc, 
            (point.0 - point_b.0, point.1 - point_b.1), 
            (point_a.0 - point_b.0, point_a.1 - point_b.1)) &&
        is_ipsilateral(vec_ca, 
            (point.0 - point_c.0, point.1 - point_c.1), 
            (point_b.0 - point_c.0, point_b.1 - point_c.1));
    
    if ans {
        println!("Yes");
    } else {
        println!("No");
    }
}

//判断是否同侧
fn is_ipsilateral(vec_main: (f32, f32), vec1: (f32, f32), vec2: (f32, f32)) -> bool {
    let sign_a = if vec_main.0 * vec1.1 - vec1.0 * vec_main.1 > 0.0 {true} else {false};
    let sign_b = if vec_main.0 * vec2.1 - vec2.0 * vec_main.1 > 0.0 {true} else {false};
    return sign_a == sign_b;
}

fn read_triangle_and_point(triangle_and_point: &mut Vec<Vec<f32>>) -> Result<(), std::io::Error> {
    let stdin = std::io::stdin();
    let handle = stdin.lock();//手动上锁,避免每次读取加锁的开销
    let mut reader = BufReader::new(handle);//使用带缓冲的读取
    let mut v1_tmp: Vec<f32>;

    for _ in 0..4 {
        let mut tmp_str = String::new();
        reader.read_line(&mut tmp_str).expect("read matrix error!");
        v1_tmp = tmp_str.trim().split(' ').map(|x| x.parse::<f32>().unwrap()).collect();
        triangle_and_point.push(v1_tmp);
    }

    Ok(())
}

发表于 2022-03-23 14:54:31 回复(1)

算法导论——计算几何学一章提到,使用向量外积的正负性,判断点和向量之间的位置关系

#include <bits/stdc++.h>
using namespace std;

int direction(double x1, double y1, double x2, double y2, double x3, double y3){
    /*
    求向量V和点(x3, y3)之间的位置关系,(x1, y1)是V的起点,(x2, y2)是V的终点
    */
    //得到向量V
    x2 -= x1;
    y2 -= y1;
    //V的起点(x1, y1)与目标点(x3, y3)构成新的向量U
    x3 -= x1;
    y3 -= y1;
    double res = x3 * y2 - x2 * y3;//求两向量U和V的外积(叉积)
    if(res < 0) return -1;//<0在逆时针方向
    if(res == 0) return 0;//=0共线
    if(res > 0) return 1;//>0说明点在向量顺时针方向
}

int main(){
    double x1, y1;
    double x2, y2;
    double x3, y3;
    cin >> x1 >> y1;
    cin >> x2 >> y2;
    cin >> x3 >> y3;

    double x4, y4;
    cin >> x4 >> y4;

    //(x1, y1)与(x2, y2)构成向量V1
    //(x2, y2)与(x3, y3)构成向量V2
    //(x3, y3)与(x1, y1)构成向量V3
    int res1 = direction(x1, y1, x2, y2, x4, y4);
    int res2 = direction(x2, y2, x3, y4, x4, y4);
    int res3 = direction(x3, y3, x1, y1, x4, y4);

    if(abs(res1 + res2 + res3) == 3){//全-1或全1,表示点(x4, y4)同时在三个向量的同一侧
        cout << "Yes";
    }else {
        cout << "No";
    }
    return 0;
}
编辑于 2020-06-30 21:12:03 回复(0)
if __name__ == "__main__":
# 读取三个坐标点的值
p1=input().split()
p2=input().split()
p3=input().split()
p0=input().split()
"""
p1_x = float(input())
p1_y = float(input())
p2_x = float(input())
p2_y = float(input())
p3_x = float(input())
p3_y = float(input())
p0_x = float(input())
p0_y = float(input())
"""
p1_x = float(p1[0])
p1_y = float(p1[1])
p2_x = float(p2[0])
p2_y = float(p2[1])
p3_x = float(p3[0])
p3_y = float(p3[1])
p0_x = float(p0[0])
p0_y = float(p0[1])
p_x=[p1_x,p2_x,p3_x]
p_y=[p1_y,p2_y,p3_y]
if p0_x<min(p_x) or p0_x>max(p_x) or p0_y<min(p_y) or p0_y>max(p_y):
print("No")
else:

if p2_x == p1_x:
p02_y=((p3_y-p1_y)/(p3_x-p1_x))*(p0_x-p1_x)+p1_y
p01_y=((p2_y-p3_y)/(p2_x-p3_x))*(p0_x-p3_x)+p3_y
if p0_y==p01_y or p0_y==p02_y:
print(0)
elif p0_y>max(p01_y,p02_y) and p0_y<min(p01_y,p02_y):
print("No")
else:
print("Yes")
elif p2_x==p3_x:
p03_y=((p2_y-p1_y)/(p2_x-p1_x))*(p0_x-p1_x)+p1_y
p02_y=((p3_y-p1_y)/(p3_x-p1_x))*(p0_x-p1_x)+p1_y
if p0_y==p03_y or p0_y==p02_y:
print(0)
elif p0_y>max(p03_y,p02_y) and p0_y<min(p03_y,p02_y):
print("No")
else:
print("Yes")
elif p1_x==p3_x:
p03_y=((p2_y-p1_y)/(p2_x-p1_x))*(p0_x-p1_x)+p1_y
p01_y=((p2_y-p3_y)/(p2_x-p3_x))*(p0_x-p3_x)+p3_y
if p0_y==p01_y or p0_y==p03_y:
print(0)
elif p0_y>max(p01_y,p03_y) and p0_y<min(p01_y,p03_y):
print("No")
else:
print("Yes")

else:
p01_y=((p2_y-p3_y)/(p2_x-p3_x))*(p0_x-p3_x)+p3_y
p02_y=((p3_y-p1_y)/(p3_x-p1_x))*(p0_x-p1_x)+p1_y
p03_y=((p2_y-p1_y)/(p2_x-p1_x))*(p0_x-p1_x)+p1_y
p0123_y=[p01_y,p02_y,p03_y]
p0123_y.sort()
if min(p_y)<p0123_y[0]:
if p0_y>p0123_y[0] and p0_y<p0123_y[1]:
print("Yes")
elif p0_y in p0123_y:
print(0)
else:
print("No")
if max(p_y)>p0123_y[2]:
if p0_y<p0123_y[2] and p0_y>p0123_y[1]:
print("Yes")
elif p0_y in p0123_y:
print(0)
else:
print("No")

编辑于 2019-09-04 09:50:18 回复(0)