LeetCode 补充题 19. 判断一个点是否在三角形内

Categories:

题目描述
思路分析
1. 解法一：向量叉积同号法（推荐）
相似题目

题目描述

✅ 补充题 19. 判断一个点是否在三角形内

思路分析

解法一：向量叉积同号法（推荐）

核心思路：

计算点 P 分别位于三条边的哪一侧，使用叉积判断方向。

若三次叉积结果同号（或为 0），点在三角形内或边界上。

该方法对浮点误差不敏感，可用整型计算。

复杂度分析：

时间复杂度：O(1)，只做常数次计算。

空间复杂度：O(1)，仅使用常数额外空间。

class Solution {
    static class Point {
        int x;
        int y;

        Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public boolean isPointInTriangle(Point a, Point b, Point c, Point p) {
        long c1 = cross(a, b, p);
        long c2 = cross(b, c, p);
        long c3 = cross(c, a, p);

        // 叉积同号或为 0，表示点在三角形内或边界上
        boolean hasNeg = (c1 < 0) || (c2 < 0) || (c3 < 0);
        boolean hasPos = (c1 > 0) || (c2 > 0) || (c3 > 0);
        return !(hasNeg && hasPos);
    }

    private long cross(Point o, Point a, Point b) {
        return (long) (a.x - o.x) * (b.y - o.y) - (long) (a.y - o.y) * (b.x - o.x);
    }
}

type Point struct {
	X int
	Y int
}

func isPointInTriangle(a, b, c, p Point) bool {
	c1 := cross(a, b, p)
	c2 := cross(b, c, p)
	c3 := cross(c, a, p)

	// 叉积同号或为 0，表示点在三角形内或边界上
	hasNeg := c1 < 0 || c2 < 0 || c3 < 0
	hasPos := c1 > 0 || c2 > 0 || c3 > 0
	return !(hasNeg && hasPos)
}

func cross(o, a, b Point) int64 {
	return int64(a.X-o.X)*int64(b.Y-o.Y) - int64(a.Y-o.Y)*int64(b.X-o.X)
}

相似题目

题目	难度	考察点
812. 最大三角形面积	简单	几何
469. 凸多边形	中等	几何
223. 矩形面积	中等	几何
836. 矩形重叠	简单	几何
149. 直线上最多的点数	困难	几何

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/19446425