Эта проблема имеет много действительных решений. Один из них работает немного как ваше описание, но вместо того, чтобы разрезать полигоны в «случайных» местах, вы можете сделать это целенаправленно, чтобы минимизировать объем вычислений.
Вот основной алгоритм. Его входные данные состоят из любого направления развертки плоскости, многоугольника P ненулевой области, целевой области a между нулем и площадью многоугольника и неотрицательного порога t (в единицах площади). Его цель состоит в том, чтобы разделить P линией, перпендикулярной направлению развертки, на две части, одну справа от линии, а другую слева от линии, так что разница между правой областью и целевой областью a не равна больше чем т .
Пусть L - любая ориентированная линия, перпендикулярная направлению развертки. Определите f (L), чтобы быть областью P, найденной справа от L, минус a . В этих условиях задача состоит в том, чтобы найти ноль f . Поскольку f вряд ли будет дифференцируемым, но непрерывным, используйте либо метод деления пополам, секущий метод , либо - мой любимый - метод Брента . Все просто и гарантированно сходятся. Используйте t для допуска конвергенции для аргумента.
Вот и все. Давайте рассмотрим, что входит в кодирование этого. Поиск корня является рутинным - вы можете использовать для него общий кусок кода - поэтому работа ГИС сводится к кодированию f . Это требует
1. Splitting the polygon by a line.
2. Computing the area of the piece(s) to the right of the line.
Обе операции реализованы практически в любой векторной ГИС. Если нет, вы можете заменить линию очень большим прямоугольником, представляющим полуплоскость справа от линии. Шаг 1 становится
1'. Clip the polygon to the rectangle.
Это действительно базовая операция.
Чтобы начать поиск корня, вам нужно найти интервал, в котором ноль f гарантированно лежит. Это просто: спроецируйте огибающую многоугольника («ограничивающий прямоугольник») в направлении развертки линии. Проекция - это нужный вам интервал.
Этот вопрос имеет долгую историю. Я давно реализовал этот алгоритм для ArcView 3.x и много раз описывал его на старых форумах пользователей ESRI. Google
Сайт полигонов Huber Split: forums.esri.com
для обсуждений, ссылок на код, улучшений и вариаций (таких как разбиение многоугольников на части желаемых размеров, максимально компактных) и алгоритмов для растровых данных.
Вот как выглядят континентальные штаты США (в проекции равной площади) с затененной нижней третью каждого штата. Очевидно, направление развертки было вертикальным.