Только некоторые точки внутри треугольника считаются «внутри» треугольника - PullRequest
Новая
       36

Только некоторые точки внутри треугольника считаются «внутри» треугольника

1 голос
/ 11 декабря 2019

Я пытался создать простую программу на пигме, которая проверяет, находится ли курсор внутри или снаружи треугольника. Я делаю это, находя область большего треугольника, а затем делаю три внутренних треугольника от положения мыши до всех трех точек и нахожу их области.

Из моего понимания, если сумма площадейтри внутренних треугольника равны сумме общей площади, тогда точка находится внутри треугольника. Однако мой код только возвращает, что он находится внутри треугольника на определенных пикселях внутри треугольника, а не на всей области.

Я не уверен, является ли это математической ошибкой или ошибкой программирования, но вотнезависимо от кода: 

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 a <=, это исправит ошибки округления, и это улучшит результаты, но все равно не будет идеальным. Любая помощь приветствуется. </p>

1 Ответ

2 голосов
/ 11 декабря 2019

Рекомендую использовать более эффективный алгоритм для расчета площадей треугольников. Алгоритм может быть найден в Проверьте, находится ли данная точка внутри треугольника или нет : 

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):

сравнивает числа с плавающей запятой. Из-за ограниченной точности чисел с плавающей запятой этот тест не пройден (см. Арифметика с плавающей запятой - Проблемы точности ).
Вы должны рассмотреть epsilon . Сделайте abs(a - b) < epsilon вместо a == b. Он не сравнивает значения двух объектов, но вместо этого сравнивает разницу со значением, достаточно низким, чтобы фактически гарантировать, что значения одинаковы. Например: 

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

...