只有三角形内部的一些点被认为是 'inside' 三角形

Question

我一直在尝试制作一个简单的 pygame 程序来检查光标是在三角形内部还是外部。我这样做是通过找到较大三角形的面积，然后从鼠标位置到所有三个点制作三个内部三角形并找到它们的面积。

根据我的理解，如果三个内部三角形的面积之和等于总面积之和，则该点在三角形内部。但是，我的代码只返回它在三角形内的特定像素上的三角形内，而不是整个区域。

我不确定这是数学错误还是编程错误，但不管怎样，这里是代码：

import pygame
from math import sqrt

pygame.init()
DISPLAY = pygame.display.set_mode((400, 400))

def drawTriangle(pointA, pointB, pointC, color):
    pygame.draw.polygon(DISPLAY, color, [pointA, pointB, pointC], 5)

def getLine(pointA, pointB):
    return sqrt((pointB[0] - pointA[0])**2 + (pointB[1]-pointA[1])**2)

def getArea(pointA, pointB, pointC):

    AB = getLine(pointA, pointB)
    BC = getLine(pointB, pointC)
    CA = getLine(pointC, pointA)

    s = (AB + BC + CA) / 2

    return sqrt(s*(s-AB) * (s-BC) * (s-CA))

A = [100, 100]
B = [200, 100]
C = [150, 200]
Color = (255, 255, 255)

while(True):

    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            break

    mpx, mpy = pygame.mouse.get_pos()
    posArray = [mpx, mpy]

    drawTriangle(A, B, C, Color)

    Area = getArea(A, B, C)

    trigA = getArea(A, B, posArray)
    trigB = getArea(posArray, B, C)
    trigC = getArea(A, posArray, C)

    if(trigA + trigB + trigC == Area):
        Color = (0, 255, 0)

    else:
        Color = (255, 255, 255)

    pygame.display.update()

到目前为止，我最好的猜测是这是一个舍入问题，但我不确定如果是的话如何解决。我认为通过使第一个 if 语句 <= 可以修复舍入错误，并且确实改善了结果，但它仍然不完美。感谢任何帮助。

Answer 1

我建议使用更高效的算法来计算三角形的面积。可以在 Check whether a given point lies inside a triangle or not:

找到算法

def getArea(pointA, pointB, pointC): 
    x1, y1 = pointA
    x2, y2 = pointB
    x3, y3 = pointC
    return abs((x1*(y2-y3) + x2*(y3-y1)+ x3*(y1-y2))/2.0)

请注意，您仍然可以使用自己的算法。但是

if(trigA + trigB + trigC == Area):

比较浮点数。由于浮点数的准确性有限，此测试失败（请参阅 Floating-point arithmetic - Accuracy problems）。
您必须考虑 epsilon。执行 abs(a - b) < epsilon 而不是 a == b。它不是比较两个对象的值，而是将差异与一个足够低的值进行比较，以实际保证值相同。例如：

if abs(trigA + trigB + trigC - Area) < 0.001:
    Color = (0, 255, 0)
else:
    Color = (255, 255, 255)

只有三角形内部的一些点被认为是 'inside' 三角形

Only some points inside of triangle are considered 'inside' the triangle

python

pygame

trigonometry