Недавно добавленные исходники

•  TDictionary Custom Sort  3 225

•  Fast Watermark Sources  2 990

•  3D Designer  4 750

•  Sik Screen Capture  3 259

•  Patch Maker  3 467

•  Айболит (remote control)  3 528

•  ListBox Drag & Drop  2 904

•  Доска для игры Реверси  80 774

•  Графические эффекты  3 843

•  Рисование по маске  3 171

•  Перетаскивание изображений  2 544

•  Canvas Drawing  2 672

•  Рисование Луны  2 500

•  Поворот изображения  2 092

•  Рисование стержней  2 119

•  Paint on Shape  1 524

•  Генератор кроссвордов  2 183

•  Головоломка Paletto  1 730

•  Теорема Монжа об окружностях  2 158

•  Пазл Numbrix  1 649

 

 

Архив исходников

   
  Базы данных
  Графика & Мультимедиа
  Сети & Интернет
  Система
  Разное
   

Ссылки и Баннеры ...

 

Delphi Sources

Delphi Sources

 




 

ИСХОДНИК ПРОГРАММЫ

 

. : Circle Covering Points : .

 

Delphi - Как нарисовать на листе бумаги несколько точек и обвести их как можно меньшим кругом

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

Наиболее цитируемый алгоритм решения данной проблемы был предложен профессорами Эльзингой и Хирном, которые в 1972 году опубликовали геометрический алгоритм решения этой проблемы и доказали его правильность.

Алгоритм

  • Выберите любые две точки: Pi и Pj.
  • Постройте круг, центр которого находится в середине линии, соединяющей Pi и Pj, и которая проходит через Pi и Pj. Если этот круг содержит все точки, то центр круга является оптимальным X. В противном случае выберите точку Pk вне круга.
  • Если треугольник, определяемый параметрами Pi, Pj и Pk, является прямоугольным или тупым, переименуйте две точки напротив прямого или тупого угла в Pi и Pj и переходите к шагу 2. В противном случае эти три точки определяют острый треугольник. Постройте круг, проходящий через три точки (центр - это пересечение серединных перпендикуляров двух сторон треугольника). Если круг содержит все точки, остановитесь, иначе перейдите к шагу 4.
  • Выберите точку Pl, не входящую в круг, и пусть Q будет точкой среди {Pi, Pj, Pk}, которая находится на наибольшем расстоянии от Pl. Увеличьте диаметр (от центра круга) через точку Q до линии, разделяющей плоскость на две полуплоскости. Пусть точка R будет точкой среди {Pi, Pj, Pk}, которая находится в полуплоскости напротив Pl. С точками Q, R и Pl перейдите к шагу 3.

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

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

Просмотры: 740
Дата: 06.07.2021, Автор: Gary Darby
Скачивания: 5
Написать сообщение:

 

Скачать (12 Кб)     Регистрация >>


 

Похожие исходники


Circle Project

Circle 3 Points

Circle Word Wrap

Compare Algo Circles

 

 

© 2004-2024 "DS"

Соглашение пользователя / Реклама / Карта сайта             Created by BrokenByte Software