用于检测线是否与凸多边形相交的O（n）算法在于检查多边形的任何边缘是否与线相交，并查看交叉点的数量是奇数还是偶数。
是否存在渐近更快的算法，例如一个O（log n）？
lhf的答案接近正确。这是一个应该解决他的问题的版本。
让多边形以逆时针顺序具有顶点v0，v1，...，vn。让点x0和x1在线上。
注意两件事：首先，找到两条线的交点（并确定它的存在）可以在恒定时间内完成。其次，确定一个点是否在一条线的左侧或右侧可以在恒定时间内完成。
我们将遵循lhf的相同基本思想来获得O（log n）算法。基本情况是多边形有2或3个顶点。这些都可以在恒定的时间内处理。
确定线（v0，v（n / 2））是否与线（x0，x1）相交。
案例1：它们不相交。
在这种情况下，我们感兴趣的线要么是分割多边形的线的左边还是右边，所以我们可以递归到多边形的那一半。具体来说，如果x0在（v0，v（n / 2））的左边，那么右半部分中的所有顶点，{v0，v1，... v（n / 2）}都在同一侧（x0，x1）因此我们知道多边形的“半”中没有交点。
案例2：他们相交。
这种情况有点棘手，但我们仍然可以在恒定时间内将交点缩小到多边形的一半。有3个子类：
情况2.1：交点位于点v0和v（n / 2）之间
我们完了。该线与多边形相交。
情况2.2：交点更接近v0（即在v0侧的多边形外）
确定线（x0，x1）是否与线（v0，v1）相交。
如果没有，那么我们就完成了，线不与多边形相交。
如果是，请找到交叉点，p。如果p在行的右边（v0，v（n / 2）），则递归到多边形的右半部分{v0，v1，...，v（n / 2）}，否则递归向左“半”{v0，v（n / 2），... vn}。
在这种情况下的基本思想是多边形中的所有点都在线的一侧（v0，v1）。如果（x0，x1）在与（v0，v（n / 2））的交叉点的一侧偏离（v0，v1）。我们知道在那一侧不能与多边形相交。
案例2.3：交叉点更靠近v（n / 2）
这种情况与案例2.2类似，但使用v（n / 2）的适当邻居。
我们完了。对于每个级别，这需要两个线交叉点，左右检查，以及确定点在一条线上的位置。每次递归将顶点数除以2（技术上将它们除以至少4/3）。因此我们获得了O（log n）的运行时。
我认为this article给出了明确的O（log n）解决方案。找到垂直于给定线的方向的极值。
边界框可能有用。
回想一下，仿射空间的凸部是其所有包络超平面的交点：你可以通过仅考虑包络超平面的一个子集的交点来得到你的多边形的近似值（读取“边界凸多边形”），测试您的线与此近似值的交点，并在必要时进行细化。
如果您期望交叉路口数量较少，所有这些都会更好。
您只需找到位于线左侧的点A和位于右侧的另一个点。剩下的问题是如何快速找到这些要点。
从凸多边形中随机取两个点A和B.
如果这两个最远的点位于线的不同侧，则线与poligon相交，否则不相交 顺便说一下，你也可以在O（log n）中找到实际的交叉点。