时间戳

首页 > 解决方案 > 快速测试以查看 2D 线段是否与 python 中的三角形相交

python - 快速测试以查看 2D 线段是否与 python 中的三角形相交

问题描述

在二维平面中，我有一条线段（P0 和 P1）和一个三角形，由三个点（t0、t1 和 t2）定义。

我的目标是尽可能有效地（在计算时间方面）测试线是否与三角形的边缘之一接触、切穿或重叠。

一切都是二维的！我希望有人可以帮我用python写这个。

感谢大家的帮助！

标签： pythongeometry

解决方案

对我来说幸运的是，线段永远不会在三角形内开始和结束，它总是会相交。下面是我在 python 中的代码。它基于 Kevin 的想法，即您只需一次评估每个线段坐标并查看它们是否相交。如果是直线和三角形，则运行代码 3 次。有人有问题吗？（在python中实现）：

#Check to see if two lines intersect
# return a 1 if they intersect
# return a 0 if the do not intersect
def line_intersection_test( p0_x, p0_y, p1_x, p1_y, p2_x, p2_y, p3_x,p3_y):


    s1_x = float(p1_x - p0_x)
    s1_y = float(p1_y - p0_y)
    s2_x = float(p3_x - p2_x)
    s2_y = float(p3_y - p2_y)
    outcome = 0

    s = float (-s1_y * (p0_x - p2_x) + s1_x * (p0_y - p2_y)) / (-s2_x * s1_y + s1_x * s2_y)
    t = float ( s2_x * (p0_y - p2_y) - s2_y * (p0_x - p2_x)) / (-s2_x * s1_y + s1_x * s2_y)

    if (s >= 0 and s <= 1 and t >= 0 and t <= 1):
        outcome = 1

    return outcome

#basically feed line segment and the three lines that form the triangle separately to line_intersect_test to see if they intersect
def triangle_intersection_test(vecX1, vecY1, vecX2, vecY2, triX1, triY1, triX2, triY2,triX3, triY3):

    side_1_test = line_intersection_test(vecX1, vecY1, vecX2, vecY2, triX1, triY1, triX2, triY2)
    side_2_test = line_intersection_test(vecX1, vecY1, vecX2, vecY2, triX2, triY2, triX3, triY3)
    side_3_test = line_intersection_test(vecX1, vecY1, vecX2, vecY2, triX1, triY1, triX3, triY3)

    result = side_1_test + side_2_test + side_3_test

    if result > 0:
    outcome = "motion detected"
    else:
    outcome = "motion not detected"

    return outcome

`

推荐阅读