Проверьте, является ли полигон самопересекающимся

У меня есть объект System.Windows.Shapes.Polygon, макет которого полностью определяется серией точек. Мне нужно определить, является ли этот многоугольник самопересекающимся; т. е. если любая из сторон многоугольника пересекается с любой другой стороной в точке, которая не является вершиной. Есть ли простой / быстрый способ вычислить это?

Источник

3 ответа

Решение

  • Легкий, медленный, малый объем памяти: сравните каждый сегмент со всеми остальными и проверьте наличие пересечений. Сложность O (n2).

  • Немного быстрее, средний объем памяти (измененная версия выше): сохраняйте ребра в пространственных "сегментах", затем выполняйте описанный выше алгоритм для каждого сегмента. Сложность O (n2 / m) для m ведер (при условии равномерного распределения).

  • Быстрый и большой объем памяти: используйте пространственную хеш-функцию, чтобы разбить края на сегменты. Проверьте на столкновения. Сложность O (n).

  • Быстрый и низкий объем памяти: используйте алгоритм строчной развертки, такой как описанный здесь (или здесь). Сложность O(n log n)

Последний мой любимый, так как у него хорошая скорость - баланс памяти, особенно алгоритм Бентли-Оттмана. Реализация тоже не слишком сложна.

Источник

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

/**
 * Checks if any two sides of a polygon cross-over.
 * If so, returns that Point.
 * 
 * The polygon is determined by the ordered sequence
 * of Points P 
 * 
 * If not returns null
 * 
 * @param V vertices of the Polygon
 * 
 * @return
 */
public static Point verify(Point[] V)
{
    if (V == null)
    {
        return null;
    }

    int len = V.length;

    /*
     * No cross-over if len < 4
     */
    if (len < 4)
    {
        return null;
    }

    System.out.printf("\nChecking %d Sided Polygon\n\n", len);

    for (int i = 0; i < len-1; i++)
    {
        for (int j = i+2; j < len; j++)
        {
            /*
             * Eliminate combinations already checked
             * or not valid
             */

            if ((i == 0) && ( j == (len-1)))
            {
                continue;
            }

            System.out.printf("\nChecking if Side %3d cuts Side %3d: ", i, j);

            boolean cut = Line2D.linesIntersect(
                    V[i].X,
                    V[i].Y,
                    V[i+1].X,
                    V[i+1].Y,
                    V[j].X,
                    V[j].Y,
                    V[(j+1) % len].X,
                    V[(j+1) % len].Y);

            if (cut)
            {
                System.out.printf("\nSide %3d CUTS Side %3d. Returning\n", i, j);
                return ( ... some point or the point of intersection....)
            }
            else
            {
                System.out.printf("NO\n");
            }
        }
    }

    return null;
}
Источник

Проверьте, пересекается ли какая-либо пара несмежных отрезков.

Источник

Ради полноты я добавлю еще один алгоритм к этому обсуждению.

Предполагая, что читатель знает об ограничивающих прямоугольниках, выровненных по оси (если нет, то Google). Очень эффективно быстро найти пары ребер, у которых есть конфликты AABB, с использованием "алгоритма очистки и сокращения". (погугли это). Затем на этих парах вызываются процедуры пересечения.

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

Источник
Другие вопросы по тегам