Разъяснение алгоритма упрощения полилиний Висвалингама-Уайатта

Я пытаюсь реализовать алгоритм упрощения полилинии. Оригинал статьи можно найти здесь: http://archive.is/Tzq2. Это кажется простым в концепции, но я не понимаю примерный алгоритм (я думаю, что он плохо сформулирован), предоставленный псевдокод, и надеялся, что кто-то может дать некоторое представление. Из статьи я понял, что основная идея состоит в том, чтобы

  1. рассчитать эффективную площадь (образованную треугольником между тремя последовательными точками на линии) для каждой точки и удалить те, площадь которых равна 0
  2. Начиная с наименьшей площади, сравнить площадь точки с порогом и, если площадь ниже этого порога, удалить ее из полилинии.
  3. Перейдите к двум соседним точкам и пересчитайте их площади по мере их изменения.
  4. Возвращайтесь к пункту 2, пока не будут удалены все области точек ниже порога.

Алгоритм следующий (дословно скопировано из статьи) :

  • Вычислить эффективную площадь каждой точки Удалить все точки с нулевой площадью и сохранить их в отдельном списке с этой площадью
  • ПОВТОРИТЬ
    • Найдите точку с наименьшей эффективной площадью и назовите ее текущей точкой. Если его расчетная площадь меньше, чем площадь последней удаляемой точки, вместо нее используется площадь последней. (Это гарантирует, что текущую точку нельзя удалить, не удаляя ранее исключенные точки.)
    • Удалить текущую точку из исходного списка и добавить ее в новый список вместе со связанной с ней областью, чтобы можно было фильтровать линию во время выполнения. .
    • Пересчитайте эффективную площадь двух соседних точек (см. рис. 1b).
  • ДО
    • Исходная линия состоит всего из 2 точек, а именно начальной и конечной точек.

Меня смущает предложение 'if' в первом шаге под 'REPEAT'... кто-нибудь может пояснить?

10
задан Igor Brejc 15 July 2014 в 12:07
поделиться