Войти
ПрограммированиеФорумГрафика

Быстрый алгоритм нахождения дырок между полигонами (4 стр)

Advanced: Тема повышенной сложности или важная.

Страницы: 1 2 3 4 5 Следующая »
#45
10:19, 21 фев. 2019

grea
> Одна точка может лежать хоть внутри двух, хоть в трех других полигонах. Может
> получиться ложная четность
с самопересечениями - да. а без них - каким образом? каждый полигон можно рассматривать отдельно - если мы пересекли его один раз значит мы внутри, если два - снаружи, если нечетное число раз - внутри, если четное - снаружи. Ну да, когда мы луч проходит через точку пересечения полигонов ее надо считать за две.

Aslan
Просто все эти собираемые трапеции надо хранить, а не сразу добавлять к площади. Если в конце скана область не замкнулась - выкидываем ее.


#46
10:33, 21 фев. 2019

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

#47
10:35, 21 фев. 2019

kipar
> не потребуется. В том и крутизна идеи. Берем луч проходящий через вершины,
> находим все его пересечения с отрезками, дальше зная наклон отрезков можем
> понять, когда соседние точки пересекутся, если какое-то пересечение будет
> раньше следующей вершины - рассматриваем его.
не получится. Пересечения тоже надо брать. Иначе математика усложняется в разы.
Вот пример. Как определить размер пустоты между полигонами рассмотрев только лучи через узлы?
Снимок | Быстрый алгоритм нахождения дырок между полигонами

#48
(Правка: 10:50) 10:43, 21 фев. 2019

Dmitrrr
первый и второй луч пройдут через рыжие углы.
Следующий луч пройдет через синий угол. на нем у нас будет 4 пересечения - сначала с рыжим контуром, потом два (совмещенные в одной точке) с синим, потом одно с рыжим. В этой точке (как и в прошлых) мы смотрим на наклон отрезков и по их наклону видим, что синий отрезок пересечется с рыжим раньше следующего "планового" луча (который должен был пройти через синий угол). Поэтому мы рассматриваем луч в точке пересечения. В этой точке мы опять видим что намечается пересечение синего отрезка с рыжим раньше "планового" луча и поэтому опять рассматриваем луч.
---

эээ, извини, я по вертикали лучи пускал, а у тебя по горизонтали линии.
По горизонтали будет так:
пускаем второй луч, он перекся с рыжим отрезком, потом с синим, потом с вырожденным в линию синим (проще, наверное, будет рассмотреть его как два узла), потом с рыжим потом с синим.
Если, для простоты, забьем на вырожденный, то будет
Р1 С1 Р2 С2.
по наклону отрезков мы понимаем, что Р1 пересечется с С1 нескоро, С1 пересечется с Р2 до наступления следующего "планового луча", Р2 не пересечется с С2 (пересечение выше). Следовательно, проводим дополнительный луч в точке пересечения С1 с Р2. Ну и аналогично со вторым пересечением.

grea
> Можно обсудить. Интересно выработать универсальный алгоритм
В крайнем случае можно сканировать с двух сторон - с одной стороны помечаем трапеции как внешние, потом идя с другой стороны эти внешние не учитываем.

#49
10:45, 21 фев. 2019

kipar
Всегда найдется хитрый диагональный контрпример

#50
(Правка: 10:57) 10:53, 21 фев. 2019

kipar
> мы смотрим на наклон отрезков и по их наклону видим, что синий отрезок
> пересечется с рыжим раньше следующего "планового" луча (который должен был
> пройти через синий угол). Поэтому мы рассматриваем луч в точке пересечения.
Это всё даёт весьма много операций.

А представь себе, что было бы проведено ещё 2 луча через точки пересечения полигонов.
Тогда хватило бы банальной площади треугольника через длину основания и высоту:
- найти длину пустоты по лучу
- умножить на расстояние между соседними лучами и на 1/2.

#51
11:00, 21 фев. 2019

Dmitrrr
для н точек пересечения будет н-1 проверок, укладываемся в квадратичную скорость. Да и вообще точек на луче будет скорее О(числа полигонов) а не О(отрезков).
а вот искать все точки пересечения и потом сортировать их вполне может получится медленнее.

#52
11:17, 21 фев. 2019

kipar
> вполне может получится медленнее
Вполне допускаю. На глазок тут очень тяжело оценивать.
Возвращаемся к

Dmitrrr
> Алгоритмов можно придумать много, но все они весьма сложные и значит не
> быстрые. Без тестов не понять какой быстрее. А сложность их такая, что код
> можно неделю писать. Не лень?

#53
(Правка: 11:26) 11:25, 21 фев. 2019

Нет, kipar, всё же ты не прав. Нужны всё же лучи через пересечения.
Вот при такой ситуации фиг придумаешь алгоритм, который сумеет разглядеть по лучам дырки (и тем более определить их площадь).
Снимок2 | Быстрый алгоритм нахождения дырок между полигонами

#54
12:38, 21 фев. 2019

Dmitrrr
> Вот при такой ситуации фиг придумаешь алгоритм, который сумеет разглядеть по
> лучам дырки (и тем более определить их площадь).
Не, ну можно запоминать все ребра, которые участвуют в рассмотрении участка картинки между соседники горизонтальными линиями, и для этих ребер отдельно брать все пересечения, да. Тоже не так просто.
Ну либо бсп, которое как бы автоматом все пересечения переберёт. Выбирай.

#55
(Правка: 12:49) 12:43, 21 фев. 2019

Dmitrrr
не вижу в нем проблемы. проводим второй плановый луч.
Безымянный | Быстрый алгоритм нахождения дырок между полигонами
он пересекает рыжий, синий, два рыжих, рыжий, два синих, синий отрезки.
проверяем пересечение соседей, первыми пересекутся вот здесь:
Безымянный | Быстрый алгоритм нахождения дырок между полигонами
соответственно проводим там луч и ищем следующее пересечение.
Безымянный | Быстрый алгоритм нахождения дырок между полигонами
Следующее пересечение будет
Безымянный | Быстрый алгоритм нахождения дырок между полигонами

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

#56
13:13, 21 фев. 2019

Dmitrrr
Изображение
Можно пускать лучи через пересечения и детектить их. Потом через вершины. Так находить множества точек.

#57
13:17, 21 фев. 2019

Вот сейчас на основе ваших подсказок кажется оптимально будет так, но есть вопросы:
1. Найти все точки пересечения, добавить их в полигоны
2. Разбить полигоны на выпуклые (не обязательно до треугольников... быстрее вроде же будет)
3. Проверить, что все полигоны имеют обход по часовой стрелке (при самопересечении может поменяться направление у куска).
4. Цикл по всем граням всех полигонов - если грань - не внутри какого либо полигона, добавить в список
5. Интегрируем все трапециями в произвольном порядке без сортировок

Вопрос: как выкинуть из списка пункта 4 грани внешнего контура?

Алгоритм получения внешнего контура может оказаться не менее сложным
Хотя в моей задаче можно задать параллелограмм, который почти всегда попадает внутрь внешней границы, а дырки ищутся внутри него. Так что это вопрос не такой существенный....

Но еще более важный вопрос - грань может соединить две дырки, при этом проходить внутри другого полигона. Как быстро отсеивать такие случаи? Реально уже кажется что BSP может быть хорошим решением

#58
(Правка: 13:27) 13:21, 21 фев. 2019

kipar
> проводим второй плановый луч.
kipar
> Следующее пересечение будет
Если продолжишь рассуждать, то придёшь к выводу, что необходимо рассмотреть все лучи через все точки пересечений. Иначе всегда будет риск что-то упустить.

lookid
> Можно пускать лучи через пересечения и детектить их.
О чём я и говорю.

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

grea
внешний контур можно задать точно так же как и любой другой полигон, но проследить за знаками.
Ещё можно просто сделать его границей подсчётов.
Тут зависит от того выползают полигоны за твой контур, или нет. Упираются в него или нет.
grea
> грань может соединить две дырки, при этом проходить внутри другого полигона.
Нарисуй. Не вижу в этом проблем, если верно понял.

#59
(Правка: 13:29) 13:28, 21 фев. 2019

Dmitrrr
> Если продолжишь рассуждать, то придёшь к выводу, что необходимо рассмотреть все
> лучи через все точки пересечений. Иначе всегда будет риск что-то упустить.
разумеется надо провести лучи через все точки пересечений. Вот только если эти точки пересечения искать заранее, добавлять к списку вершин и потом сортировать - это и алгоритм усложняет и памяти вдвое больше съест. А так мы их можем по ходу сканирования находить, уже в нужном порядке.

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумГрафика