Nano Hash - криптовалюты, майнинг, программирование

Сортировка точек многоугольника

У меня есть выпуклый многоугольник ABCDE... (у него может быть любое количество точек). Мне нужно отсортировать все его вершины, чтобы ни одно из ребер не пересекалось.
пример:

A _____ B
  \   /
   \ /
    X
   / \
  /___\
C       D

Этот многоугольник в порядке ABCD имеет пересекающиеся ребра. однако в порядке ABDC:

A _____ B
  |   |
  |   |
  |   |
  |   |
  |___|
C       D

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

Как я могу это сделать?

algorithm geometry computational-geometry
10.09.2011

Ответы:


1

Предполагая, что все ваши точки находятся на выпуклой оболочке вашего многоугольника, вы можете использовать следующее:

  1. Выберите две крайние точки с минимальным и максимальным значением X (назовите их Xmin и Xmax) и нарисуйте линию между ними. Если у вас есть несколько точек с одинаковым значением X на крайних точках, выберите Xmin с минимальным значением Y и Xmax с максимальным значением Y.
  2. Разделить список точек на два подсписка, где все точки ниже линии, соединяющей Xmin и Xmax, находятся в одном списке, а все точки выше этой линии — в другом. . Включите Xmin в первый список и Xmax во второй.
  3. Отсортируйте первый список в порядке возрастания значения X. Если у вас есть несколько точек с одинаковым значением X, отсортируйте их по возрастанию значения Y. Это должно происходить только для точек с той же компонентой X, что и Xmax, поскольку многоугольник выпуклый.
  4. Отсортируйте второй список в порядке убывания значения X. Опять же, сортируйте по убыванию значения Y в случае нескольких точек с одинаковым значением X (что должно происходить только для точек с компонентом X Xmin.
  5. Добавьте два списка вместе (неважно, какой из них будет первым).
10.09.2011
  • К вашему сведению: абсолютно нет необходимости использовать обратные триггерные функции для радиальной сортировки точек. Вы можете просто отсортировать на основе фактического значения (y - y0)/(x-x0). Это ядро ​​сканирования Грэма 10.09.2011
  • @Foo Bah: Спасибо, что указали на это. Из вашего ответа ничего не было ясно. Кстати, вы понизили ответ? Если да, то почему вы его отредактировали? 10.09.2011
  • Я отредактировал его, потому что хотел отменить свой отрицательный голос, а потом забыл это сделать. Я удалил его сейчас. 10.09.2011

    • 2

    выберите две точки на многоугольнике. середина линии будет находиться внутри этого многоугольника. Пусть эта точка будет М.

    Затем отсортируйте точки на основе угла, основанного на M (вдоль оси X), нарушая вырождение на основе расстояния от M. Повторение в этом порядке гарантирует, что никакие два ребра не будут пересекаться.

    10.09.2011
  • великолепная идея! 21.07.2017
    • Новые материалы
    Кластеризация: более глубокий взгляд
    Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
    Как написать эффективное резюме
    Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
    Частный метод Python: улучшение инкапсуляции и безопасности
    Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
    Как я автоматизирую тестирование с помощью Jest
    Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
    Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
    Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
    Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
    В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
    Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
    В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..