@Артем Смирнов

Всем привет! Необходима помощь в решении задачи об определении принадлежности многоугольника многоугольнику. На плоскости даны 2 многоугольника, заданные набором своих вершин. Многоугольники могут быть как выпуклыми, так и не выпуклыми. Оба многоугольника простые, без самопересечений. Так вот каким образом можно определить принадлежит ли один другому. Пока единственное, что пришло на ум, это проверять каждую точку 2-ого многоугольника на принадлежность первому многоугольнику, и из их совокупности делать вывод о принадлежности всего многоугольника. Но не думаю, что это хорошее решение, если кто нибудь знает как оптимально решить эту задачу пожалуйста подскажите! И еще один вопрос , если все таки выбирать вариант с проверкой каждой точки, то какой из алгоритмов решении задачи об определении принадлежности точки многоугольнику вы бы предложили в таком случае! Заранее огромное спасибо!!

0

@Igor3D

Если площади всех треугольников одного знака - тестируемая точка внутри многоугольника, иначе снаружи. Каждый треугольник образуется тестируемой точкой + парой точек (отрезком) проверяемого. Знаковая площадь вычисляется как векторное произведение любых 2 сторон тр-ка (но с одинаковым порядком для всех тр-ков).

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

0

@Артем Смирнов

Igor3D, спасибо большое за ответ! Я писал что Многоугольники могут быть как выпуклыми, так и не выпуклыми. Для выпуклых многоугольников у меня алгоритм уже есть. Термином простой, я хотел подчеркнуть что многоугольник не многосвязный, то есть не содержит «многоугольных дыр», может быть термин не правильный. Хотя в итоге нельзя сказать точно про один из этих 2-ух многоугольников, он как раз может быть многосвязным, поэтому термин простой можно и вычеркнуть. Если уточнять терминологию для 2-ух фигур, то необходим вариант "внутри".

0

@Igor3D

Тогда надо делать odd-even. Из каждой проверяемой точки выбрасываете луч вдоль X или Y и считаете число пересечений со всеми отрезками др мн-ка. Если нечетное - точка внутри. Это работает для невыпуклых и неплохо оптимизируется, правда есть капризы с точностью (напр если луч совпадает с отрезком или пересекает точку)

0

@Qwertiy

Каждую точку - это как? Если каждую вершину, то неверно.

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

Насчёт оптимальности - не знаю. Предлагаю проверить факт отсутствия пересечения сторон разных многоугольников. Если пересечений нет, то проверить одну из точек, внутри она или снаружи.

1