javascript - 为什么此线段相交算法不起作用？

我试图计算两段的交点。每段应垂直或水平（0°、90°、180°、270°）如果两个线段都是垂直或水平的，我还需要计算交点。

function intersection(line1, line2) {
    var origin1x = Math.min(line1.getStartPosition().x, line1.getEndPosition().x);
    var origin1y = Math.min(line1.getStartPosition().y, line1.getEndPosition().y);
    var origin2x = Math.min(line2.getStartPosition().x, line2.getEndPosition().x);
    var origin2y = Math.min(line2.getStartPosition().y, line2.getEndPosition().y);

    var dx = origin2x - origin1x;
    var dy = origin2y - origin1y;

    if((line1.isHorizontal() && (dx < 0 || dx > line2.getLength())) || (!line1.isHorizontal() && (dy < 0 || dy > line1.getLength()))) {
        return null;
    }

    return {
        x: line1.isHorizontal() ? origin1x + dx : origin1x,
        y: !line2.isHorizontal() ? origin2y - dy : origin2y
    }
}

代码在某些情况下运行良好，但有时会失败。
例如：

line1 = ((0, 50), (0, 30)) // ((startX, startY), (endX, endY))
line2 = ((0, 0), (0, 30))
shouldBe = (0, 30)

谢谢您。

最佳答案

因为你的直线总是水平的或者垂直的，所以它们与轴对齐的边界框完全相等。因此，我们可以简单地使用包围盒求交算法，而不是使用直线求交算法，如以下伪代码：

# get the minimum and maximum x and y coordinates of each region
# (this part can be skipped if you know the coordinates are sorted already)
(xmin1, xmax1) = sort(region1.start.x, region1.end.x)
(ymin1, ymax1) = sort(region1.start.y, region1.end.y)
(xmin2, xmax2) = sort(region2.start.x, region2.end.x)
(ymin2, ymax2) = sort(region2.start.y, region2.end.y)

# get the maximum of the minimums and the minimum of the maximums
xmin = max(xmin1, xmin2), xmax = min(xmax1, xmax2)
ymin = max(ymin1, ymin2), ymax = min(ymax1, ymax2)

# check if there is any overlap
if xmin > xmax or ymin > ymax:
    raise error("the regions do not intersect")
else:
    return new region( start=(xmin, ymin), end=(xmax, ymax) )

请注意，此代码返回一个新的边界框，覆盖两个区域重叠的整个区域。即使对于水平/垂直线区域，如果这两条线具有相同的方向并且在一系列点上重叠，则此区域也可能包含多个点如果你只需要一个点，你可以选择重叠区域的中点。