如果线相交凸多边形优化算法 [英] optimal algorithm if line intersects convex polygon

问题描述

我想知道是否有更快的算法，然后为O（n），用于检测是否线路相交凸多边形。我知道这个算法，当您检查多边形的每个边缘，如果它与线相交，并期待，如果交叉点的数目是奇数还是偶数，我只是希望，如果存在一些更快，例如在O（log n）的复杂性。

I would like to know if there is faster algorithm then O(n) for detecting if line intersects a convex polygon. I know the algorithm when you check every edge of the polygon if it intersects with the line and look if the number of intersections is odd or even, I am just looking if there exists some faster for example in O (log n) complexity.

感谢

推荐答案

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）），然后在右一半，所有顶点{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是到线的右侧（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，V1）在其交叉​​点的一侧与发散远离（V0，V（N / 2））。我们知道，在那边有可与多边形没有交点。

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屋！