2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 10:40 


16/01/18
17
slavav в сообщении #1285463 писал(а):
Это не нужно. Возьмите любой полигон в котором нет контура. Выполните закраску белым. Закрасьте полигоны с контуром серым. Остальные полигоны закрасьте чёрным. Оцените соотношение белых и чёрных полигонов. Выберите, какой цвет внутри контура. Переходите к ранее изложенному алгоритму для точки.

Тут все равно стоит вопрос с начальным выбором того первого полигона, с которого начнется закраска, может быть 4 случая:
    1) белый полигон окажется внутри контура, черный снаружи - удача, задача решена
    2) белый полигон окажется снаружи контура, черный внутри - удача, задача решена
    3) белый полигон окажется внутри контура и черный внутри - мы закрасим две области внутри и поделим ее на псевдо внутреннею и псевдо наружную
    3) белый полигон окажется снаружи контура и черный снаружи - мы закрасим две области снаружи и поделим ее на псевдо внутреннею и псевдо наружную

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

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

 Профиль  
                  
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 12:51 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 14:59 


16/01/18
17
slavav в сообщении #1285660 писал(а):
Случай 3) невозможен: после закраски белым все полигоны внутри контура уже белые.
Второй случай 3) тоже невозможен: после закраски белым все полигоны снаружи контура уже белые.


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

 Профиль  
                  
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 15:57 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 16:09 


16/01/18
17
slavav
Всю площадь сравнивать не нужно, т.к. полигоны имеют приблизительно одинаковую площадь: достаточно сравнить их количество, когда один цвет закрасит все свободные полигоны до ограничивающего контура.
Начальные точки для закраски определяю так:
disednet в сообщении #1285616 писал(а):
На рисунке для наглядности полигоны представлены треугольниками. Мы относительно сегмента контура (красным цветом) определяем точки полигонов(к которому принадлежит данный сегмент) левые и правые. Левые точки красим зеленым, правые - синим. Далее ищем полигоны (соседние тому, что содержит данный сегмент контура), которые содержат точки одного цвета, например, левые и не содержат правые. Да, сами испытываемые полигоны не должны содержать сегментов контура.

 Профиль  
                  
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 16:16 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Внутренние точки контура на криволинейной поверхности
Сообщение19.01.2018, 16:32 


16/01/18
17
slavav в сообщении #1285719 писал(а):
Я так и не понял зачем вам правые и левые точки. Что вы выигрываете?

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 22 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group