Как я могу определить, находится ли 2D точка внутри многоугольника?

Question

Я пытаюсь создать быструю 2D точку внутри алгоритма многоугольника для использования при тестировании попаданий (например, Polygon.contains(p:Point)). Буду признателен за эффективные методы.

Answer 1

Вот точка в тесте полигонов в C, которая не использует приведение лучей. И он может работать для перекрывающихся областей (самопересечения), см. Аргумент use_holes.

/* math lib (defined below) */
static float dot_v2v2(const float a[2], const float b[2]);
static float angle_signed_v2v2(const float v1[2], const float v2[2]);
static void copy_v2_v2(float r[2], const float a[2]);

/* intersection function */
bool isect_point_poly_v2(const float pt[2], const float verts[][2], const unsigned int nr,
                         const bool use_holes)
{
    /* we do the angle rule, define that all added angles should be about zero or (2 * PI) */
    float angletot = 0.0;
    float fp1[2], fp2[2];
    unsigned int i;
    const float *p1, *p2;

    p1 = verts[nr - 1];

    /* first vector */
    fp1[0] = p1[0] - pt[0];
    fp1[1] = p1[1] - pt[1];

    for (i = 0; i < nr; i++) {
        p2 = verts[i];

        /* second vector */
        fp2[0] = p2[0] - pt[0];
        fp2[1] = p2[1] - pt[1];

        /* dot and angle and cross */
        angletot += angle_signed_v2v2(fp1, fp2);

        /* circulate */
        copy_v2_v2(fp1, fp2);
        p1 = p2;
    }

    angletot = fabsf(angletot);
    if (use_holes) {
        const float nested = floorf((angletot / (float)(M_PI * 2.0)) + 0.00001f);
        angletot -= nested * (float)(M_PI * 2.0);
        return (angletot > 4.0f) != ((int)nested % 2);
    }
    else {
        return (angletot > 4.0f);
    }
}

/* math lib */

static float dot_v2v2(const float a[2], const float b[2])
{
    return a[0] * b[0] + a[1] * b[1];
}

static float angle_signed_v2v2(const float v1[2], const float v2[2])
{
    const float perp_dot = (v1[1] * v2[0]) - (v1[0] * v2[1]);
    return atan2f(perp_dot, dot_v2v2(v1, v2));
}

static void copy_v2_v2(float r[2], const float a[2])
{
    r[0] = a[0];
    r[1] = a[1];
}

Примечание: это один из менее оптимальных методов, так как он включает в себя много вызовов atan2f, но он может быть интересен разработчикам, читающим эту ветку (в моих тестах он примерно в 23 раза медленнее, чем при использовании метода пересечения линии ).

Answer 2

Это работает только для выпуклых фигур, но Minkowski Portal Refinement и GJK также являются отличными вариантами для тестирования, если точка находится в многоугольнике. Вы используете вычитание Минковского, чтобы вычесть точку из многоугольника, затем запустите эти алгоритмы, чтобы увидеть, содержит ли многоугольник начало координат.

Кроме того, интересно, что вы можете описать свои фигуры немного более неявно, используя вспомогательные функции, которые принимают вектор направления в качестве входного сигнала и выплевывают самую дальнюю точку вдоль этого вектора. Это позволяет вам описать любую выпуклую форму .. изогнутую, сделанную из многоугольников или смешанную. Вы также можете выполнить операции, чтобы объединить результаты простых вспомогательных функций для создания более сложных фигур.

Дополнительная информация: http://xenocollide.snethen.com/mpr2d.html

Также в гемах по программированию игр 7 рассказывается, как это сделать в 3d (: