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 - все точки заливки будут внутри многоугольника, берите первую.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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