我需要一个快速算法检查，如果两个非无限线穿越。必须要快，因为它会在手机上运行了很多。

I need a fast algorithm for checking if two non-infinite lines are crossing. Have to be fast because it'll run on a cell phone a lot.

该算法也只需要返回是或否，它没有找出确切位置线交叉！

The algorithm do only have to return yes or no, it does not have to find out exactly where the lines cross!

我在这里看：How你发现，其中两条线段相交？ 但是，线程是一个丛林，人们一直在说，这就是答案但随后另外两个人说，这是因为这和 - 该错误不正确的。

I have looked here: How do you detect where two line segments intersect? But that thread is a jungle, people keep saying that "this is the answer" but then two other guys say that it is incorrect because of this-and-that bug.

请帮我找到一个很好的工作和算法这一点。

Please help me find a good and working algorithm for this.

只是要清楚：我需要你给一个函数... lineApointAx lineApointAy lineApointBx lineApointBy lineBpointAx lineBpointAy lineBpointBx lineBpointBy ...并返回true或false取决于或如果两线交叉不行。

Just to be clear: I need a function that you give... lineApointAx lineApointAy lineApointBx lineApointBy lineBpointAx lineBpointAy lineBpointBx lineBpointBy ...and that returns true or false depending on if the two lines cross or not.

编辑：

如果可能的话我会AP preciate，如果你们回答通俗地说，从一个程序员的角度，而不是一个数学家。换句话说：code将是很好的，而不是公式。我是一个不错的程序员，但我的数学技能缺乏，我不想从现在开始，我已经实现了一个错误，只是因为我读的公式不正确的发现一年。我希望我没有告诉你，只因为你是一个程序员，这并不意味着你是擅长数学过，呵呵。数学公式是从来没有明显的有人说不能做数学。

If at all possible I would appreciate it if you guys answered in layman's terms, from a programmers point of view and not a mathematician. In other words: code would be nice instead of formulas. I'm a decent programmer but my math skills are lacking and I would hate to discover a year from now that I have implemented a mistake just because I read a formula incorrectly. I hope I don't have to tell you that just because you're a programmer that doesn't mean that you're good at math too, hehe. A math formula is never obvious to someone that can't do much math.

推荐答案

有必要和足够的那一个部段的两端都在其他段的不同侧面，以及反之亦然。要确定哪一方的一个点上，只需要一个跨产品，看看它是否是正面或负面的：

It is necessary and sufficient that the two ends of one segment are on different sides of the other segment, and vise-versa. To determine which side a point is on, just take a cross-product and see whether it's positive or negative:

（B X - A X ）（P 是 - B 是） - （B 是 - A 是）（P X - B X ）

(Bx - Ax)(Py - By) - (By - Ay)(Px - Bx)

编辑： 拼出来：假设你正在看的两条线段，[AB]和[CD]。段相交当且仅当（（A和B是[光盘]）和不同侧的（C和D都在[AB]）的不同侧）。

To spell it out: suppose you're looking at two line segments, [AB] and [CD]. The segments intersect if and only if ((A and B are of different sides of [CD]) and (C and D are on different sides of [AB])).

要看到两个点，P和Q是否，都在一个线段[EF]的不同侧，计算两个交叉乘积，一个用于P和一个用于问：

To see whether two points, P and Q, are on different sides of a line segment [EF], compute two cross products, one for P and one for Q:

（F X - 电子 X ）（P 是 - ˚F是） - （F 是 - 电子是）（P X - ˚F X ）

(Fx - Ex)(Py - Fy) - (Fy - Ey)(Px - Fx)

（F X - 电子 X ）（Q 是 - ˚F是） - （F 是 - 电子是）（Q X - ˚F X ）

(Fx - Ex)(Qy - Fy) - (Fy - Ey)(Qx - Fx)

如果结果具有相同的符号（正或两个负）然后忘记它，该点在同一侧，区段不相交。如果一个是正而另一个否定的，则点在相对侧

If the results have the same sign (both positive or both negative) then forget it, the points are on the same side, the segments do not intersect. If one is positive and the other negative, then the points are on opposite sides.