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

Тема "Геометрия" поистине безгранична… вот еще одна задачка…

  1. Формулировка задания: прямая пересекает максимальное количество окружностей
  2. Критерий пересечения окружности и прямой
  3. Перебор множеств точек
  4. Визуальное представление на Координатной плоскости
  5. Случайная генерация множест точек и окружностей
  6. Исходный код на C#

С визуальным представлением на координатной плоскости


Формулировка задания: прямая пересекает максимальное количество окружностей


На плоскости заданы множества точек A и множество окружностей B.
Найти две различные точки из A такие, чтобы проходящая через них прямая пересекалась с максимальным количеством окружностей из B.

Формулировка задания: прямая пересекает максимальное количество окружностей
Рис.1        Формулировка задания: прямая пересекает максимальное количество окружностей

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



Критерий пересечения окружности и прямой


В цикле перебираем множество точек «А» и по каждым двум точкам находим уравнение прямой.
Затем, во вложенном цикле, определяем кратчайшее расстояние (перпендикуляр) до этой прямой от каждого центра окружности множества «В» и сравниваем с ее радиусом.

Критерий пересечения окружности и прямой
Рис.2        Критерий пересечения окружности и прямой

И становится понятно, пересекает прямая окружность или нет.
Если перпендикуляр больше радиуса, то пересечения нет.



Перебор множеств точек


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



Визуальное представление на Координатной плоскости


Координатная плоскость (из школькой программы) и координатная плоскость формы Windows (c её параметрами left, top в пикселях) отличаются друг от друга, но математическими преобразованиями всегда можно связать любые две координатные системы отсчета.

Т.е. необходимо решить подзадачу: из имеющихся координат точки (любой) в системе_1, получить координаты этой же точки в системе_2.

В программном коде это решение представлено. Тестируйте…



Случайная генерация множест точек и окружностей


Чтобы не утруждать пользователя вводом координат точек и параметров окружностей - множество точек «А» и окружностей «B» генерируются случайным образом.

//------------------------------
siz1 = (int)numericUpDown1.Value; siz2 = (int)numericUpDown2.Value; //размеры массивов для точек и окружностей
arrPoints = new Point[siz1]; //cоздается массив нужного размера для хранения точек
arrCircles = new geoCircle[siz2];//cоздается массив нужного размера для хранения объектов "окружность"
Random rnd = new Random();
//заполнить массивы точек и окружностей
//------------------------------




Исходный код на C#


Данный код написан на Visual Studio 2012, но для всех старших версий проблем с открытием быть не должно.

В крайнем случае, свяжемся и все проблемы решим…

скачать ехе-файл для тестирования


Условия получения готового кода?    Показать?


Эта же задача в «консольном» варианте здесь...Прямая, пересекающая максимум Окружностей console приложение C++

Другие примеры на тему «Математические методы компьютерной 2D 3D графики»

Другие примеры на языках «C»,«C++»,«C#»





Если у Вас остались вопросы, то задать их Вы можете, нажав на эту кнопочку ...




Если на этой странице не нашлось того, что Вы так искали...

         Не расстраивайтесь, не все потеряно... Смело щелкайте...
исходный код на заказ. orenstudent.ru Автоматизация документов MS Office. orenstudent.ru исходный код на заказ. orenstudent.ru Помогите найти и устранить ошибку в исходном коде программы. orenstudent.ru Skype-консультирование по программированию
Скайп-консультации

Акция !!!
исходный код комментарии цена минимальная


Не попадайтесь на удочку мошенников-кидал...
Сайт помощи студентам по программированию и информатике

Program code