Можно ли определить, используя только подмножество точек многоугольника, где находится внутренняя часть многоугольника?

Question

Я пытаюсь визуализировать подмножество многоугольника с большим количеством точек (n> 100 000).Я решил поместить точки многоугольников в двоичное дерево, чтобы я мог быстро найти только точки, расположенные в окне просмотра, и отобразить их.

Проблема, которую я пытаюсь выяснить здесь: если я получу только подмножество точек многоугольника, как я узнаю, где находится внутренняя часть многоугольника?т.е. область, которую я должен заполнить?Я приложил картинку ниже, чтобы объяснить мой вопрос:

Для изображения выше дано подмножество точек полного многоугольника (возвращенопосле обхода двоичного дерева).Могу ли я определить, какая сторона (A или B) находится внутри многоугольника, и заполнить соответствующим образом?

Если это невозможно, есть ли лучший способ для хранения или извлечения многоугольников длялучше найти интерьер многоугольника?

Answer 1

вам нужно разбить ваши полигоны на такие разделы:

1. выбрал внутреннюю точку C (Аква-центр)

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

   , тогда просто проверьте, находится ли он внутри многоугольника.Это, однако, должно быть сделано с медленным приближением (используя все точки многоугольника).К счастью, эта точка необходима для вычисления только один раз (при создании / загрузке / инициации многоугольника).

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

2. разделите полигон на секции

   , используя диагональные линии (серые линии) между выбранным центром и любой точкой многоугольника.Выберите точки, чтобы сечения имели примерно одинаковое количество точек, а сама диагональ не должна пересекать ребра многоугольника .Поэтому, если вы получили m точек и хотите n сечений, используйте каждую m-th точку в качестве диагонали ... и, если она пересекается, используйте соседнюю точку, пока она не будет правильной.

   Раздел также должен быть выполнентолько один раз на многоугольник.

3. быстрее внутри

   Теперь, чтобы определить, находится ли какая-либо точка (пурпурный) внутри, сначала проверьте, в каком сечении это делается. CW / CCW проверка между всеми диагоналями или использование atan2 (в этом случае каждый диагональный угол может быть предварительно рассчитан один раз для ускорения процесса), чтобы найти две диагонали, которые охватывают указанную точку:

   

   , поэтому найдите диагональ, которая является CW к точке и имеет минимальный угол ..., а также еще одну, которая является CCW.Если "центральная" точка равна C, а проверенная точка равна P, а диагональные точки равны D(i), тогда

   angle = acos(dot(P-C,D(i)-C)/(|P-C|*|D(i)-C|))
   

   и координата z cross(P-C,D(i)-C) сообщит вам, если диагональ / угол равен CWили CCW.Я думаю, вы можете игнорировать acos, поскольку нелинейный результат без него должен быть все еще монотонным, поэтому min,max будет по-прежнему корректным.

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

   Теперь, когда у вас есть 2 ближайших диагонали CW D(i) и CCW D(j), просто протестируйте многоугольник, построенный из C, и все точки междуD(i) и D(j).

   

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

PS это примечание для Пола

Алгоритм с использованием CW / CCW - работает только для выпуклыхполигоны на вогнутых есть ложные негативы, как на этом изображении:

Answer 2

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

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

Для иллюстрации:

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

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

Этот подход работает для многоугольников любой сложности, а также для фигур с несколькими (не связанными) контурами.

Случай края (извините за каламбур), который следует соблюдать при кодировании этогоup:

Если ваша проецируемая линия проходит непосредственно через вершину: эта вершина является частью двух ребер, так что же линия попадает первой?Это может иметь большое значение.Чтобы упростить эту ситуацию, вы должны только считать, что ребро пересекается, если y-позиция спроецированной линии строго меньше y-позиции самой высокой из двух вершин ребра.

Ниже показаны три точки, проекционные линии которых проходят через самую низкую вершину, среднюю точку и самую высокую вершину ребра («самое высокое» означает наибольшее значение y; направление ребра здесь неважно).Первые две линии пересекают край;третий - нет.

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

Answer 3

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

Даже если части вышеуказанного квадрата были закрыты, выЯ все еще смогу определить, где находится внутренняя часть многоугольника.Сама сортировка может быть выполнена в O(n), если точки еще не в нужном порядке (вполне вероятно).