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

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

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

Страницы: 1 2 3 4 5
#60
13:37, 21 фев. 2019

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


#61
13:58, 21 фев. 2019

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

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

#62
15:33, 21 фев. 2019

ИзображениеИзображение

Вот, смотрите, четыре полигона, две дырки. Точки A и B являются граничными к дыркам, как для квадрата так и для ромба. Как определить, что грань AB не является гранью дырки?

#63
15:47, 21 фев. 2019

kipar
> не сортируем, ищем минимальное.
Добавляем их в двоичную кучу по Y, в которой у нас точки лежат.
И обновления там локальные, т. е. затрагивают только соседние точки на луче, O(1).
В общем, один-в-один как в алгоритме Форчуна.

#64
17:37, 21 фев. 2019

grea
На самом построить деле внешнюю и внутренние границы легко
На каждой итерации алгоритма имеем набор неперекрытых отрезков, объединяем их в связные списки вершин через общие вершины, для связ списка храним (голова, хвост), объединение - const время, в итоге все контуры замнутся  (голова=хвост), из них внешний - содержащий одну гарантированно внешнюю вершину, например с min X, остальные - контуры дырок

#65
20:10, 21 фев. 2019

grea
> Как определить, что грань AB не является гранью дырки?
А как она может уйти от этого определения?
При методе лучами через неё пройдёт луч.
При методе периметра и слева и справа от неё есть точки внутри полигонов.

Этот рисунок другую проблему показал. Если мы идёт горизонтальными лучами, то нарисованные дырки могут избежать обнаружения, если стороны розового квадрата строго параллельны лучам.

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

Тема в архиве.