102. 三角形包含(Triangle containment)

在笛卡尔坐标系中随机选取三个不同的点,其中\(-1000\le x,y \le1000\) ,然后用这三个点组成一个三角形。考虑下面两个三角形:

$$ A\left( -340,495 \right) ,B\left( -153,-910 \right) ,C\left( 835,-947 \right)\\ X\left( -175,41 \right) ,Y\left( -421,-714 \right) ,Z\left( 574,-645 \right) $$
可以验证三角形\(ABC\)包含直角坐标系的原点,而三角形\(XYZ\)不包含。文本文件triangles.txt包含1000个随机三角形的顶点坐标,试问这一千个三角形中有多少个包含原点。

注:文件中的前两个三角形就是上面举的这两个例子。

分析:这是一道经典的计算机图形学入门问题,验证特定的点是否位于一个三角形中一般三种方法。第一种是面积法,即如果某个点在三角形内部,比如说点\(P\)在三角形\(ABC\)内部,则以点P为顶点的三个三角形PAB、PAC与PBC的面积之和等于三角形ABC的面积。

img

如果点P在三角形外部,这个关系就不满足,所以可以用这个性质来判断某个点是否在三角形内部。第二种和第三种方法分别是向量法与重心坐标法,相对来说,他们的效率要比面积法要高,但原理和计算也更为复杂一些。考虑到这道题的问题规模不大,面积法的效率已经让人很满意了,所以我使用了面积法。对后两种方法感兴趣的同学可以上网自行搜索。

使用面积法的核心问题是根据三角形的顶点坐标计算它的面积,可以直接套用相应的公式。设三角形ABC的顶点坐标分别为\(A\left( x_1,y_1 \right) ,B\left( x_2,y_2 \right) ,C\left( x_3,y_3 \right)\),则三形的面积为:

$$ S_{\bigtriangleup ABC}=\frac{1}{2}|\left( x_1-x_3 \right) \left( y_2-y_1 \right) -\left( x_1-x_2 \right) \left( y_3-y_1 \right) | $$

根据这个公式,我们就可以用三角形的顶点坐标求出它的面积,然后再使用面积法判断原点是否位于三角形内部。代码如下:

# time cost = 9.9 ms ± 310 µs

def area_of_triangle(xa,ya,xb,yb,xc,yc):
    area = abs((xa-xc)*(yb-ya)-(xa-xb)*(yc-ya)) / 2
    return area

def main():
    counter = 0
    with open('ep102.txt') as f:
        coords = [x.strip().split(',') for x in f.readlines()]
        for coord in coords:
            xa,ya,xb,yb,xc,yc = [int(x) for x in coord]
            abc = area_of_triangle(xa,ya,xb,yb,xc,yc)
            aob = area_of_triangle(xa,ya,0,0,xb,yb)
            aoc = area_of_triangle(xa,ya,0,0,xc,yc)
            boc = area_of_triangle(xb,yb,0,0,xc,yc)
            if abc == aob + aoc + boc:
                counter += 1
    return counter