寻找多边形和水平线之间的交点。

Question

我有一个多边形和一个给定的点。我需要找到多边形上与给定点相同 Y 坐标的点。请看附件: 给定点是红色点，蓝色点是我要找的点(与给定点具有相同的 Y)。

目前，我知道通过检查给定点 Y 值是否在该部分内来解决它。找到包含的部分后，我只需运行简单方程即可找到交点。但是！我希望找到更好、更简单的方法来解决它，也许有现成的公式呢？

谢谢！

- Roy K

---

您需要找到多边形与通过给定点的水平线之间的交集吗？我理解得对吗？ - kraskevich

@user2040251 是的。我需要找到交点。 - Roy K

@Michelle，这是我知道如何做的事情。我想知道是否有更明智的公式来完成它。 - Roy K

@Michelle 谢谢，我重新写了我的问题。 - Roy K

如果你有很多这些查询需要回答，并且多边形是凸的，你可以进行一些预处理来加快速度。找到它的最高点和最低点（实际上它们可以是水平线），然后找到从顶部到底部的两个边序列 - 一个在左侧，一个在右侧。对于这两个边序列中的每一个，顶点按y坐标排序，因此当你需要找到给定y坐标的交点时，你可以二分搜索每个列表（O(log n)时间），而不是搜索每条边（O(n)时间）。 - j_random_hacker

Answer 1

这里有一个解决方案，它使用O(n log n)的预处理时间和每个查询的O((log n)^2 + cnt)时间，其中cnt是交点的数量。它适用于任何多边形。

1）预处理：将每个线段存储为一对(low_y, high_y)。按low_y排序。现在可以构建一个二维线段树，其中第一维是low_y，第二维是high_y。如果正确地执行（可以为每个线段树节点保留一个已排序的vector，其中包含那些且仅包含这些与该特定节点相对应的high_y值），则它可以占用O(n log n)空间和时间。

2）查询：可以这样重新表述：找到所有满足low_y <= query_y <= high_y条件的线段（即，对）。要查找所有这样的线段，可以遍历线段树，并将范围[min(low_y), query_y]分解为至多O(log n)个节点的并集（这里只考虑第一维）。对于固定的节点，可以在已排序的high_yvector上应用二分搜索，以仅提取满足low_y <= query_y <= high_y条件的那些线段（第一个不等式是正确的，因为遍历树的方式，所以我们只需要检查high_y）。在这里，由于线段树的性质，我们有O(log n)个节点，并且二分搜索需要O(log n)时间。因此，这一步具有O((log n)^2)的时间复杂度。找到最小的high_y后，很明显，vector的尾部（从该位置到结尾）包含那些与查询线相交的线段，因此可以简单地迭代它们并找到交点。这一步需要O(cnt)时间，因为只有当线段与线相交时才会检查线段（cnt - 线和多边形之间的总交点数）。因此，整个查询的时间复杂度为O((log n)^2 + cnt)。

3）实际上，这里至少有两种特殊情况：
i)交点是两个相邻多边形部分的公共点，
ii)水平部分，
因此应根据所需输出仔细处理它们（例如，可以完全忽略水平边缘或假定整个边缘是交点）。

- kraskevich

---

每个段落都具有二维性质。无法统一low_y和high_y。或者，至少我没有看到正确地将它们统一的方法。 - kraskevich

我们并不关心x坐标 - 对于多边形中的每条边，我们可以将其y范围（一对y坐标）作为线段存储在线段树中，而x坐标则存储在另外两个字段中（即线段树不关心的字段）。 - j_random_hacker

对于一维线段树，需要为每个节点维护一个边缘列表或向量（因为可能有多条边覆盖具体的y）。在最坏情况下（如果所有边缘都很长并覆盖几乎整个范围），它需要O(n^2)的空间。 - kraskevich

不，每个部分（这里是多边形边缘的每个垂直延伸）将在段树中恰好出现1个节点。 （我在这里有一个解释在哪里，但它是错误的 - 我相信维基百科的文章：）在这里，它的x坐标可以存储在同一位置（并由段树函数视为黑盒子）。 - j_random_hacker

它如何处理像这样的输入：(1, 2)，(1, 3)，...，(1, n)（我指的是仅 y 坐标）？至少有 n/2 个线段包含在至少 n/2 个基本线段中（或者我理解错了吗？）。 - kraskevich

Answer 2

我假设预处理是允许的。

首先将多边形分解为单调链：依次考虑所有边并将所有朝同一方向（上或下）的边链接起来。您可以忽略水平边。

最多会有两个链（凸多边形始终为两个），如果你真的很不幸，最坏情况下会有N-1或N个链（取决于N的奇偶性）。平均约为四个。

请注意，链中的顶点按递增或递减的Y排序（“免费”排序）。

现在对于给定的测试点，通过二分法在Y上定位它，例如在Yi和Yi+1之间。然后交点由X = Xi + (Y - Yi).(Xi+1 - Xi) / (Yi+1 - Yi)给出。

此过程将需要O(N)的预处理时间，并且最坏情况下需要O(N)的存储空间；查询时间将为O(K.LgL)，其中K是链的数量，LgL是链长度的平均对数。

这不是最优的，也不是各向同性的，但它编程起来相当简单，开销很小。

- user1196549

---

如果 N 很小（比如说 < 10），使用“暴力破解”方法。没有什么能够超越它。 - user1196549