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

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

задан 11 Ноя '15 17:15

@Ni55aN: я так понимаю, это ровно тот же вопрос, что и предыдущий -- как по точке определить, находится ли она вне или внутри многоугольника. Для выпуклого случая проверка может быть осуществлена проще, а для невыпуклого это не работает, и там предлагалось выпускать луч и подсчитывать чётность числа точек пересечения со сторонами.

Надо заметить, что если контур многоугольника имеет сложную "лабиринтообразную" форму, то по рисунку зрительно очень трудно понять, где находится заданная точка: вне или внутри контура. Мы тогда бы сами считали по тому же принципу, через чётность.

(11 Ноя '15 17:24) falcao

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

(11 Ноя '15 17:44) Ni55aN

кроме способа с выпусканием луча нет ничего? Это оказалось слишком ресурсоемко

(11 Ноя '15 17:46) Ni55aN

@Ni55aN: я думаю, если оказалось, что с выпусканием луча считать долго, то надо модифицировать сам этот способ. Внутри него есть много разных возможностей, и надо найти подходящую. Скорее всего, эти вещи уже многократно реализованы. Вроде бы @knop давал ссылку на литературу.

(12 Ноя '15 9:32) falcao

@falcao, вот что получилось http://jsfiddle.net/j8x4w4xL/10/

(12 Ноя '15 20:52) Ni55aN

@Ni55aN: а зачем Вы дали мне эту ссылку? Я никогда не читаю программные коды -- это для меня примерно как китайские иероглифы :)

(12 Ноя '15 22:12) falcao

@falcao, показать результат) Для ответа это не годится, но может интересующимся будет полезно

(13 Ноя '15 22:50) Ni55aN

@Ni55aN: можно тогда было словами изложить суть алгоритма. Форум всё-таки не по программированию.

(13 Ноя '15 23:21) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×239
×51

задан
11 Ноя '15 17:15

показан
540 раз

обновлен
13 Ноя '15 23:21

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru