Содержание
Дана точка на плоскости с координатами (х, у). Составить блок-схему алгоритма, который выдает сообщение "Да" если точка лежит внутри заштрихованной области, "Нет" – если точка лежит вне заштрихованной области, "На границе" – если точка лежит на границе заштрихованной области.
Заранее всем большое спасибо за помощь! 🙂
2. Уравнение прямой уже написано. Решением будет y>x и y Остальные ответы
гЕМША МБВПТБФПТОПК ТБВПФЩ СЧМСЕФУС РПМХЮЕОЙЕ РТБЛФЙЮЕУЛЙИ ОБЧЩЛПЧ Ч ТБВПФЕ У ХУМПЧОЩН ПРЕТБФПТПН Й ТБЪЧЕФЧМЕООЩНЙ БМЗПТЙФНБНЙ Ч СЪЩЛЕ C.
2. фЕНЩ ДМС РТЕДЧБТЙФЕМШОПК РТПТБВПФЛЙ
- МПЗЙЮЕУЛЙЕ ПРЕТБГЙЙ
- ХУМПЧОЩК ПРЕТБФПТ
3. ъБДБОЙС ДМС ЧЩРПМОЕОЙС
рПУФТПЙФШ РТПЗТБННХ, ЛПФПТБС ЧЧПДЙФ ЛППТДЙОБФЩ ФПЮЛЙ (x, y) Й ПРТЕДЕМСЕФ, РПРБДБЕФ МЙ ФПЮЛБ Ч ЪБЫФТЙИПЧБООХА ПВМБУФШ ОБ ТЙУХОЛЕ, ЛПФПТЩК УППФЧЕФУФЧХЕФ чБЫЕНХ ЧБТЙБОФХ. рПРБДБОЙЕ ОБ ЗТБОЙГХ ПВМБУФЙ УЮЙФБФШ РПРБДБОЙЕН Ч ПВМБУФШ.
В вычислительной геометрии известна задача об определении принадлежности точки многоугольнику. На плоскости даны многоугольник и точка. Требуется решить вопрос о принадлежности точки многоугольнику.
Многоугольник может быть как выпуклым, так и невыпуклым. Обычно предполагается, что многоугольник простой, т.е. без самопересечений, но задачу рассматривают и для не-простых многоугольников. В последнем случае разные способы определения принадлежности точки многоугольнику могут привести к разным результатам. Различают алгоритмы без предварительной обработки и алгоритмы с предварительной обработкой, в ходе которой создаются некоторые структуры данных, позволяющие в дальнейшем быстрее отвечать на множество запросов о принадлежности точек одному и тому же многоугольнику.
Алгоритм определяет точки границ многоугольника как точки, ему принадлежащие.
Содержание
Описание [ править ]
Для того чтобы все результаты вычислений в программе могли быть представлены целочисленными переменными (манипулирование данными целого типа повышает быстродействие программы и является естественным для приложений компьютерной графики), вычисления и сравнения площадей треугольников заменяются вычислениями и сравнениями их удвоенных площадей. Тем самым исключается погрешность округления при программной реализации всего алгоритма, в целом.
Аргументами функции, реализующей проверку принадлежности данной точки данному многоугольнику произвольного вида, являются
- указатель на массив пар целочисленных координат вершин многоугольника, а именно, на массив структур вида
- число вершин многоугольника;
- целочисленное значение координаты X заданной точки;
- целочисленное значение координаты Y заданной точки.
Функция возвращает 1, если точка принадлежит многоугольнику, иначе — 0.
Функция имеет следующий вид.
Очень быстрый алгоритм [ править ]
В основе алгоритма лежит идея подсчёта количества пересечений луча, исходящего из данной точки в направлении горизонтальной оси, со сторонами многоугольника. Если оно чётное, точка не принадлежит многоугольнику. В данном алгоритме луч направлен влево.
Замечание: Так как умножение быстрее деления, условие можно записать так:
Однако, стоит заметить, что данный алгоритм не эквивалентен предыдущему, поэтому его использование может привести к неправильным результатам.
Perl [ править ]
Delphi (Object Pascal) [ править ]
JavaScript [ править ]
Python 3 [ править ]
На Python программа несколько отличается от других языков в сторону компактности из-за особенностей адресации элементов массива. Не нужны дополнительные переменные. Не работает с многоугольниками вогнутого типа
Быстрый алгоритм для случая, когда луч пересекает одну или несколько вершин [ править ]
Функция Cross определяет, пересекает ли луч j-ое ребро многоугольника:
Фрагмент основной программы:
Если переменная count примет нечетное значение, то точка лежит внутри многоугольника. В противном случает точка лежит вне заданого многоугольника.
Замечание: В данной реализации алгоритма луч направлен вниз.
Загрузка...
