Внутренние точки контура на криволинейной поверхности

[disednet]

slavav в сообщении #1285463 писал(а):

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

Тут все равно стоит вопрос с начальным выбором того первого полигона, с которого начнется закраска, может быть 4 случая:

1) белый полигон окажется внутри контура, черный снаружи - удача, задача решена

2) белый полигон окажется снаружи контура, черный внутри - удача, задача решена

3) белый полигон окажется внутри контура и черный внутри - мы закрасим две области внутри и поделим ее на псевдо внутреннею и псевдо наружную

3) белый полигон окажется снаружи контура и черный снаружи - мы закрасим две области снаружи и поделим ее на псевдо внутреннею и псевдо наружную

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

Возможен вот такой способ решения в данной ситуации

На рисунке для наглядности полигоны представлены треугольниками. Мы относительно сегмента контура (красным цветом) определяем точки полигонов(к которому принадлежит данный сегмент) левые и правые. Левые точки красим зеленым, правые - синим. Далее ищем полигоны (соседние тому, что содержит данный сегмент контура), которые содержат точки одного цвета, например, левые и не содержат правые. Да, сами испытываемые полигоны не должны содержать сегментов контура.

[slavav]

Случай 3) невозможен: после закраски белым все полигоны внутри контура уже белые.
Второй случай 3) тоже невозможен: после закраски белым все полигоны снаружи контура уже белые.

[disednet]

slavav в сообщении #1285660 писал(а):

Случай 3) невозможен: после закраски белым все полигоны внутри контура уже белые.
Второй случай 3) тоже невозможен: после закраски белым все полигоны снаружи контура уже белые.

Это я поторопился с неправильной интерпретацией вашего решения. У себя в задаче всегда крашу одновременно, и останавливаюсь когда достигну границ контура, а потом оцениваю количественную разницу (того цвета, что меньше тот и внутри). Это связано с тем, что количество полигонов может быть значительным ($10^6$), а контур может быть маленьким(хотя самих контуров может быть много), и задача становится вычислительно сложной, если запускать полную закраску для каждого контура.

[slavav]

Без полной закраски как вы сравните "белую" и "чёрную" площади? Без просмотра все полигонов это невозможно. Или меняйте способ определения "внутренности" контура или смиритесь.

[disednet]

slavav
Всю площадь сравнивать не нужно, т.к. полигоны имеют приблизительно одинаковую площадь: достаточно сравнить их количество, когда один цвет закрасит все свободные полигоны до ограничивающего контура.
Начальные точки для закраски определяю так:

disednet в сообщении #1285616 писал(а):

На рисунке для наглядности полигоны представлены треугольниками. Мы относительно сегмента контура (красным цветом) определяем точки полигонов(к которому принадлежит данный сегмент) левые и правые. Левые точки красим зеленым, правые - синим. Далее ищем полигоны (соседние тому, что содержит данный сегмент контура), которые содержат точки одного цвета, например, левые и не содержат правые. Да, сами испытываемые полигоны не должны содержать сегментов контура.

[slavav]

Вычислить площадь или количество полигонов - одинаковые по сложности задачи.

Я так и не понял зачем вам правые и левые точки. Что вы выигрываете?

[disednet]

slavav в сообщении #1285719 писал(а):

Я так и не понял зачем вам правые и левые точки. Что вы выигрываете?

В этом случае до закраски я уже имею две точки, лежащие по разные стороны замкнутого контура. Далее начинаю закраску (одновременно) в этих двух точках, закраска производится итерационно и на каждом шаге количество найденных белых и черных полигонов может отличаться. Когда же, на каком-то шаге, не остается незакрашенных полигонов, например, белыми закрасили $10$ полигонов и свободных больше нет - осуществляем сравнение черных и белых полигонов. При этом, понятное дело, черных может быть $11$ и $100$, но все равно меньше общего количества полигонов (которых может быть и $10^6$).

Т.е. ответ на ваш вопрос: выигрываю вычислительное время, в ущерб простоте.