math - 与给定线段相交的线

Question

给定一些水平线段，我想找到一条与所有水平线段相交的垂直线。如果不存在这样的行，算法应该报告。此外，在多条垂直线的情况下，希望找到与所有水平线段的边界框中心距离最小的线。

我确信在组合几何中会有这种东西，但我找不到。谁能给我一些关于我们如何做到这一点的想法。

提前致谢。

Answer 1

我将遍历您的所有线段并找到以下值：

minxstart - smallest x value of all of the left end of your horizontal segments
maxxstart - largest x value of all of the left ends of your horizontal segments
minxend - smallest x value of the right end of your horizontal segments
maxxend - largest x value of the right end of your horizontal segments
miny - smallest y value of horizontal segments
maxy - largest y value of horizontal segments

如果 minxend < maxxstart 则不存在任何行，因为无法同时命中包含这些值的两行。

求边界框的 centerx：

centerx = (minxstart + maxxend) / 2

垂直线段的 x 值必须介于 maxxstart 和 minxend 之间。选择一个最接近 centerx 的值，称之为 newx。

您的垂直线段将从 (newx, ymin) 变为 (newx, ymax)。