经典的三点定位算法错了吗？

Question

算法可以参考这里(http://algs4.cs.princeton.edu/91primitives/) and here (http://www.geeksforgeeks.org/orientation-3-ordered-points/),

尝试以下代码 p1 = {0, 0}、p2 = {4, 4}、p3 = {0, 3} 或 p1 = {0, 0}、p2 = {4, 4}， p3 = {0, 5}，我认为这两种情况都应该是顺时针的，但是算法输出是逆时针的。

// A C++ program to find orientation of three points
#include <iostream>
using namespace std;

struct Point
{
    int x, y;
};

// To find orientation of ordered triplet (p1, p2, p3).
// The function returns following values
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation(Point p1, Point p2, Point p3)
{
    // See 10th slides from following link for derivation
    // of the formula
    int val = (p2.y - p1.y) * (p3.x - p2.x) -
            (p2.x - p1.x) * (p3.y - p2.y);

    cout << val << endl;
    if (val == 0) return 0; // colinear

    return (val > 0)? 1: 2; // clock or counterclock wise
}

// Driver program to test above functions
int main()
{
    Point p1 = {0, 0}, p2 = {4, 4}, p3 = {0, 3};
    int o = orientation(p1, p2, p3);
    if (o==0)        cout << "Linear";
    else if (o == 1) cout << "Clockwise";
    else             cout << "CounterClockwise";
    return 0;
}

Answer 1

让我们绘制序列 (0, 0) -> (4, 4) -> (0, 3):

如你所见，是逆时针方向。这样代码就可以正常运行了，只是你判断失误了。

Answer 2

顺时针或逆时针取决于您的轴方向！

真正重要的是三角形测试给出对齐点的 0，一侧为正，另一侧为负。

只要做一个测试用例，你就会永远知道什么是正确的"signedness"。

经典的三点定位算法错了吗？

the classic algorithm to find orientation of three points is wrong?

c++

algorithm

geometry

computational-geometry