两个图形算法题

发表于 | 更新于 | 分类于 |
本文字数： 4.9k | 阅读时长 ≈ 4 分钟

写在前面

之前一直没有接触过关于图形的算法题，这次在牛客网上看直播的时候有讲到两个图形题，在此做一个总结，图形题主要是需要关于数学方面的知识，其本身应该是一个数学问题，代码方面不是很难。所以需要我们了解图形方面的数学知识。

题目

题目一

题目描述：
判断一个点是否在矩形内部。

在二维坐标系中，所有的值都是double类型，那么一个矩形可以由4个点来代表，（$x_1$, $y_1$）为最左的点、（$x_2$, $y_2$）为最上的点、（$x_3$, $y_3$）为最下的点、（$x_4$, $y_4$）为最右的点。给定4个点代表的矩形，在给定一个点（x, y）,判断（x, y）是否在矩形中。

输入描述：
输入是矩形4个点的坐标：$x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$, $x_4$, $y_4$及给定点的坐标$x, y$

输出描述：
True: 给的点$x, y$在矩形内部
False: 给的点$x, y$不在矩形内部

解题思路：
首先这个题目的矩形的位置分两种情况，一种是矩形和$x$轴，y轴是平行的，一种是矩形与坐标轴是不平行的。前一种情况是很简单的，只需要判断给定点的x是否在$x_1$和$x_4$之前，给定点的y是否在$y_1$和$y_4$之间。而对于第二种情况，我们只需进行图形的旋转即可变为第一种情况。

对于点($x$, $y$)关于某点旋转$\theta$度后的坐标（$x_1$, $x_2$）的求解，即为平面内的坐标点的旋转公式。

下面进行简单的讲解。
坐标旋转
对于上图，求C(c, d)关于B(a, b)旋转$\beta$°后的点A($x$, $y$)的坐标。

  1. 设点C旋转前的角度为$\theta$,即∠CBx, 旋转后的角度则为$\theta-\beta$.
  2. 求C、B两点距离，$|CB| = c / cos\theta = d/sin\theta$
  3. 求A、B两点距离, $|AB| = x/cos(\theta - \beta) = y/sin(\theta - \beta)$
  4. 显然$|CB| = |AB| = r$，所以
  5. 由三角函数两角和差公式知：所以：由上可知，旋转后的坐标只与旋转前的坐标和旋转角度有关。
    根据上面的数学知识，我们就可以编写代码了。
    具体代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    public static boolean isInside(double x1, double y1, double x4, double y4,
                double x, double y) {
        if (x <= x1) {
            return false;
        }
        if (x >= x4) {
            return false;
        }
        if (y >= y1) {
            return false;
        }
        if (y <= y4) {
            return false;
        }
        return true;
    }

    public static boolean isInside(double x1, double y1, double x2, double y2,
            double x3, double y3, double x4, double y4, double x, double y) {
        if (y1 == y2) {
            return isInside(x1, y1, x4, y4, x, y);
        }
        double l = Math.abs(y4 - y3);
        double k = Math.abs(x4 - x3);
        double s = Math.sqrt(k * k + l * l);
        double sin = l / s;
        double cos = k / s;
        double x1R = cos * x1 + sin * y1;
        double y1R = -x1 * sin + y1 * cos;
        double x4R = cos * x4 + sin * y4;
        double y4R = -x4 * sin + y4 * cos;
        double xR = cos * x + sin * y;
        double yR = -x * sin + y * cos;
        return isInside(x1R, y1R, x4R, y4R, xR, yR);
    }

题目二

判断一个点是否在三角形内部
在二维坐标系中，所有的值都是double类型，那么一个三角形可以由3个点来代表，给定3个点代表的三角形，再给定一个点(x, y)，判断(x, y)是否在三角形中。

输入描述：
输入是三角形3个点的坐标：$x_1$, $y_1$, $x_2$, $y_2$, $x_3$, $y_3$及给定点的坐标$x, y$

输出描述：
True: 给的点$x, y$在三角形内部
False: 给的点$x, y$不在三角形内部

解题思路：
首先我们可以想到的是利用面积的思路，假设给定的点在三角形内部，那么由这个点与原三角形的三个点形成的3个小三角形的面积必然等于原来三角形的面积。而如果给定的点在三角形的外部，则3个三角形的面积必然超过原来三角形的面积。已知三角形的3个点，求三角形的面积，我们可以根据海伦公式求面积。

第二种方法就是如果给定的点在三角形内部，那么在原三角形上沿着逆时针的方向，可以发现给定的点都在左边，如果给点的点不在三角形的内部，那么必然存在一边，给定的点在边的右边。我们可以利用这个性质来进行判断。关于点在线段的左侧还是右侧，可以利用叉乘进行判断。

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static boolean isInside1(double x1, double y1, double x2, double y2,
        double x3, double y3, double x, double y) {
    double area1 = getArea(x1, y1, x2, y2, x, y);
    double area2 = getArea(x1, y1, x3, y3, x, y);
    double area3 = getArea(x2, y2, x3, y3, x, y);
    double allArea = getArea(x1, y1, x2, y2, x3, y3);
    return area1 + area2 + area3 <= allArea;
}

public static double getArea(double x1, double y1, double x2, double y2,
        double x3, double y3) {
    double side1Len = getSideLength(x1, y1, x2, y2);
    double side2Len = getSideLength(x1, y1, x3, y3);
    double side3Len = getSideLength(x2, y2, x3, y3);
    double p = (side1Len + side2Len + side3Len) / 2;
    return Math.sqrt((p - side1Len) * (p - side2Len) * (p - side3Len) * p);
}

public static double getSideLength(double x1, double y1, double x2,
        double y2) {
    double a = Math.abs(x1 - x2);
    double b = Math.abs(y1 - y2);
    return Math.sqrt(a * a + b * b);
}

public static boolean isInside2(double x1, double y1, double x2, double y2,
        double x3, double y3, double x, double y) {
        // 保证逆时针方向
    if (crossProduct(x3 - x1, y3 - y1, x2 - x1, y2 - y1) >= 0) {
        double tmpx = x2;
        double tmpy = y2;
        x2 = x3;
        y2 = y3;
        x3 = tmpx;
        y3 = tmpy;
    }
    if (crossProduct(x2 - x1, y2 - y1   , x - x1, y - y1) < 0) {
        return false;
    }
    if (crossProduct(x3 - x2, y3 - y2, x - x2, y - y2) < 0) {
        return false;
    }
    if (crossProduct(x1 - x3, y1 - y3, x - x3, y - y3) < 0) {
        return false;
    }
    return true;
}

public static double crossProduct(double x1, double y1, double x2, double y2) {
    return x1 * y2 - x2 * y1;
}
您的支持将鼓励我继续创作！