0

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

2
  • Если многоугольник выпуклый - да хотя бы среднее арифметическое координат вершин... Если многоугольник может быть произвольный, то сложнее, но можно тупо найти его внутренний треугольник и выбрать точку внутри него...
    – gecube
    24 дек 2013 в 22:55
  • Многоугольник может быть любым
    – Error
    24 дек 2013 в 23:09

4 ответа 4

4
  1. Найдём два различных минимальных значения координаты y вершин многоугольника и обозначим их y' и y".
  2. Возьмём прямую y = (y" + y')/2
  3. Найдём все точки пересечения этой прямой с многоугольником
  4. Найдём два минимальных значения координаты x для точек пересечения. Обозначим их x' и x"
  5. Тогда точка с координатами (x" + x')/2 , (y" + y')/2 будет являться внутренней точкой многоугольника
4
  • Круто, только по-моему везде - надо заменить на +. Ну и тогда условия < станут не нужны.
    – dzhioev
    25 дек 2013 в 14:35
  • Хмм... - да я миллион случаев найду когда это не выполняется...
    – Barmaley
    25 дек 2013 в 20:30
  • Продемонстрируйте хотя бы один :)
    – Error
    25 дек 2013 в 21:39
  • @Error я не учел замечение @dzhioev (уже поправил ваш ответ) - с учетом этого все верно - это будет внутренней точкой
    – Barmaley
    26 дек 2013 в 5:45
3
  1. Задаться неким delta - ну скажем как 1/100 от длины самой короткой стороны многоугольника
  2. Взять любую сторону (лучше всего самую длинную)
  3. Взять середину этой стороны и отложить перпендикулярно к ней отрезок длиной delta - в обе стороны от нее. Либо одна либо вторая точка на конце этого отрезка будет гарантированно лежать внутри многоугольника
  4. Если не получается - берем следующую сторону и повторяем шаг №3
  5. Ну если и тут не получается, то берем delta и делим на 10 и повторяем шаги 2-4
0

Есть пример на Turbo Pascal с использованием метода трассировки луча Проверка на принадлежность точки многоугольнику

2
  • Вот только мне не проверка нужна, а именно получить точку (любую), которая лежит внутри многоугольника
    – Error
    24 дек 2013 в 22:19
  • Триангулировать многоугольник -> выбрать произвольный треугольник -> выбрать произвольную точку на выбранном треугольнике. 24 дек 2013 в 23:30
0

Алгоритмы заливки, http://algolist.manual.ru/graphics/fill.php - все точки заливки будут внутри многоугольника, берите первую.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.