渐近最优算法，计算一条线是否与凸多边形相交 [英] Asymptotically optimal algorithm to compute if a line intersects a convex polygon

问题描述

一种用于检测直线是​​否与凸多边形相交的O(n)算法在于检查多边形的任意边是否与直线相交，并检查相交的数量是否为奇数或偶数.

An O(n) algorithm to detect if a line intersects a convex polygon consists in checking if any edge of the polygon intersects the line, and look if the number of intersections is odd or even.

是否有一种渐近更快的算法，例如O(log n)一个?

Is there an asymptotically faster algorithm, e.g. an O(log n) one?

推荐答案

lhf的答案接近正确.这是应该解决他问题的版本.

lhf's answer is close to correct. Here is a version that should fix the problem with his.

让多边形具有逆时针顺序的顶点v0，v1，...，vn.让点x0和x1在直线上.

Let the polygon have vertices v0, v1, ..., vn in counterclockwise order. Let the points x0 and x1 be on the line.

注意两件事:首先，可以在恒定时间内完成两条线的交点(并确定其存在).其次，确定点是位于线的左侧还是右侧可以在固定时间内完成.

Note two things: First, finding the intersection of two lines (and determining its existence) can be done in constant time. Second, determining if a point is to the left or the right of a line can be done in constant time.

我们将遵循lhf的相同基本思想来获得O(log n)算法.基本情况是多边形具有2个或3个顶点的情况.这些都可以在固定时间内处理.

We will follow the same basic idea of lhf to get an O(log n) algorithm. The base cases are when the polygon has 2 or 3 vertices. These can both be handled in constant time.

确定线(v0，v(n/2))是否与线(x0，x1)相交.

Determine if the line (v0,v(n/2)) intersects the line (x0,x1).

情况1:它们不相交.

在这种情况下，我们感兴趣的线位于分割多边形的线的左侧或右侧，因此我们可以递归到多边形的那一半.具体来说，如果x0在(v0，v(n/2))的左侧，则右侧"half" {v0，v1，... v(n/2)}中的所有顶点都在同一侧(x0，x1)的值，因此我们知道多边形的一半"中没有交集.

In this case the line we are interested in is either to the left or the right of the line splitting the polygon, and so we can recurse into that half of the polygon. Specifically, if x0 is to the left of (v0,v(n/2)) then all the vertices in the right "half", {v0, v1, ... v(n/2)} are on the same side of (x0,x1) and so we know that there is no intersection in that "half" of the polygon.

情况2:它们确实相交.

这种情况有点棘手，但是我们仍然可以在恒定时间内将交点缩小到多边形的一半".有3个子案例:

This case is a little trickier, but we can still narrow down the intersection to one "half" of the polygon in constant time. There are 3 subcases:

情况2.1:交点在点v0和v(n/2)之间

我们完成了.线与多边形相交.

We are done. The line intersects the polygon.

情况2.2:交点更靠近v0(即，在v0一侧的多边形外部)

确定线(x0，x1)是否与线(v0，v1)相交.

Determine if the line (x0,x1) intersects with the line (v0,v1).

如果不这样做，那么我们完成了，这条线不会与多边形相交.

If it does not then we are done, the line does not intersect the polygon.

如果存在，请找到交点p.如果p在线(v0，v(n/2))的右边，则递归到多边形的右半部分{v0，v1，...，v(n/2)}，否则递归左边的一半" {v0，v(n/2)，... vn}.

If it does, find the intersection, p. If p is to the right of the line (v0, v(n/2)) then recurse into the right "half" of the polygon, {v0, v1, ..., v(n/2)}, otherwise recurse to the left "half" {v0, v(n/2), ... vn}.

在这种情况下，基本思想是多边形中的所有点都位于线(v0，v1)的一侧.如果(x0，x1)与(v0，v(n/2))相交的一侧偏离(v0，v1).我们知道在那一侧与多边形没有交点.

The basic idea in this case is that all points in the polygon are to one side of the line (v0, v1). If (x0, x1) is diverging away from (v0, v1) on one side of its intersection with (v0, v(n/2)). We know that on that side there can be no intersection with the polygon.

案例2.3:交点更接近v(n/2)

此案例的处理与案例2.2类似，但使用的是v(n/2)的适当邻居.

This case is handled similarly to Case 2.2 but using the appropriate neighbor of v(n/2).

我们完成了.对于每个级别，这都需要两个线相交，左右检查以及确定点在线上的位置.每次递归都将顶点数除以2(从技术上将它们除以至少4/3).这样我们得到了O(log n)的运行时.

We are done. For each level, this requires two line intersections, a left-right check, and determining where a point is on a line. Each recursion divides the number of vertices by 2 (technically divides them by at least 4/3). And so we get a runtime of O(log n).

这篇关于渐近最优算法，计算一条线是否与凸多边形相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！