javascript - 如何确定两个段中的哪一个在 y 轴上最低？

Question

我有一个段列表，我需要在 y 轴上对它们进行排序。

现在我不知道是否真的有可能使用简单的解决方案，因为可以放置段的情况很多。

该图像说明了它，但基本上，如果两堵墙在 y 轴上相交，我想知道哪一个是两者之间最低的。 我尝试过考虑不同的位置，并根据其中一个点的大小来考虑它是如何工作的。但是，我觉得有太多的可能性，我很容易错过一些用例。是否有某种方法可以比较两个段并判断哪个段较低？也许用矢量计算？我没主意了。

我正在使用 JavaScript，它是带有自定义比较函数的 array.sort() 函数，但我的问题更多是几何/数学问题。

标签： javascriptsortingmathvectorgeometry

Answer 1

我假设这些段是按它们的 x 坐标在内部排序的。即，A1.x小于A2.x。B1和 也是如此B2。如果不是这种情况，您可以简单地交换两点。

首先，在 x 轴上找到两条线段重叠的区间：

xLo = max(A1.x, B1.x)
xHi = min(A2.x, B2.x) 

现在我们需要找到与 x 坐标对应的 y 坐标。对于不平行于 y 轴的线段，这非常简单：

y[A|B](x) = (x - [A|B]1.x) * ([A|B]2.y - [A|B]1.y) / ([A|B]2.x - [A|B]1.x)  + [A|B]1.y 

然后简单地检查

if yA[xLo] < yB[xLo] && yA[xHi] < yB[xHi]
    A is lower than B
else if yA[xLo] > yB[xLo] && yA[xHi] > yB[xHi]
    A is higher than B
else
    the segments intersect

对于平行于 y 轴的线段，检查需要稍有不同。如果两者是平行的并且具有相同的 x 坐标，只需检查 y 轴上的间隔是否重叠。如果只有一个线段平行，则将yA[x] < yB[x]检查替换为间隔检查（间隔完全低于或高于另一个 y 坐标）。