Является ли отрезок внутренней диагональю многоугольника

Дан многоугольник и индексы двух его вершин
Необходимо узнать, является ли отрезок, проведённый между этими вершинами, внутренней диагональю данного многоугольника

    Отрезок, соединяющий вершины многоугольника, является внутренней диагональю тогда и только тогда, когда он не пересекается ни с одной стороной многоугольника и все точки этого отрезка лежат внутри многоугольника.

Асимптотика O(n).

Листинг C++

double SAT (point a, point b, point c)
{
    return 0.5 * (a.x * b.y + b.x * c.y + c.x * a.y - a.y * b.x - b.y * c.x - c.y * a.x);
}

int sSAT (point a, point b, point c)
{
    double s = SAT (a, b, c);
    if (gr (s, 0)) return 1;
    if (ls (s, 0)) return - 1;
    return 0;
}

bool is_crossing (point a, point b, point c, point d)
{
    return sSAT (a, c, b) != sSAT (a, d, b) && sSAT (c, a, d) != sSAT (c, b, d);
}

bool is_diagonal (vector < point > & v, int i1, int i2)
{
    int i, j;
    int n = v.size ();

    if (i1 == (i2 + 1) % n || i2 == (i1 + 1) % n || i1 == i2) return 0;

    forn (i, n)
        if (i != i1 && i != i2 && i1 != (i + 1) % n && i2 != (i + 1) % n)
        {
            j = (i + 1) % n;

            if (is_crossing (v[i], v[j], v[i1], v[i2])) return 0;
        }

    return point_in_polygon (part_segment (v[i1], v[i2], 1, 1), v);
}

14:14
04.08.2009

По всем вопросам обращаться: rumterg@gmail.com