Найти непокрытую кругами область, которая может быть в красном круге - Геометрия - Страница 2

@Excalibur921 · 17.01.2022, 14:54

Студворк — интернет-сервис помощи студентам

Для чего вообще этот центр? Требования к скорости работы так и нет. Это для игры? Для чего изначально?

@Igor3D · 17.01.2022, 15:07

Сообщение от mirekua

Это снова чего-то про попиксельный перебор ?

Понял, умолкаю

@mirekua · 17.01.2022, 15:16 **[ТС]**

Сообщение от Excalibur921

Это для игры? Для чего изначально?

Я кстати ответил выше на такие вопросы ) Нет это не игра

И про скорости работы писал с сравнениями Есть такая старая программа И она 15 минут на современном компьютере считает Видимо там попиксельный перебор)

Вообще эту задачу даже можно свести к поиску центроида для набора точек Центр тяжести набора точек можно найти по формулам
вроде (x 1 + x 2 + ... + x k ) / k

Но тут не все так просто с этой формулой

@Excalibur921 · 17.01.2022, 15:34

Сообщение от mirekua

Видимо там попиксельный перебор

Что там его перебирать? Алгоритм рисующий красный круг попиксельно проверяет до десятка уравнений на квадрат расстояния. Я думаю вопрос секунды для красного круга из 1000 пикселей диаметром и 10 рандом кругов.

Или наоборот набрасывать белые круги вообще через видеокарту на черный фон с маской красного круга.

Без такого тут будет адовы ветвления “если то” из аналитических формул.

Сообщение от mirekua

15 минут на современном компьютере считает Видимо там попиксельный перебор

Разрешение какое задаете? Может там пару млн. длинна стороны. Может интерпретируемый язык…может чтение пикселей из буфера на джаваскрипте.

@mirekua · 17.01.2022, 16:06 **[ТС]**

Можно получившийся из точек полигон разбить на треугольники и тогда искать общий центр тяжести

Но это много мороки

Сообщение от Excalibur921

Алгоритм рисующий красный круг

Рисовать ничего и не надо. Оно делает что-то вроде чертежей в масштабе

Красного круга на самом деле нет. Это я просто его нарисовал для наглядности. Оперировать надо областью которую он очерчивает

Это понятно, что ты предложил железное решение. Но эти задачи не железного уровня Да И язык высокого уровня

Поэтому таких вопросов как разрешение нет.

(x 1 + x 2 + ... + x k ) / k
Эта формула работает не точно Наиболее известных способов нахождения центра тяжести около 10 )

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

И это сложно. Тут решения для случая выпуклого многоугольника )

@Excalibur921 · 17.01.2022, 17:50

Сообщение от mirekua

Рисовать ничего и не надо.

Он и не рисует...это для наглядности работы. В памяти создается 2д массив и пробегае…надоело талдычить =)

Сообщение от mirekua

Оперировать надо областью которую он очерчивает

Ага…которая задается уравнением центра и радиусом и может быть учтена через аналитические формулки или аппроксимацию вашими любимыми пикселями чтобы не считать это 15 минут.

Сообщение от mirekua

Но эти задачи не железного уровня Да И язык высокого уровня

Понятия не имею что это вообще значит.

Сообщение от mirekua

Эта формула работает не точно

Это зависит от представления числа.

Ну берите аналитику …чего тогда.

@mirekua · 17.01.2022, 18:21 **[ТС]**

Сообщение от Excalibur921

Понятия не имею что это вообще значит.

бррр... ) Языки программирования высокого уровня. Не слышали ?)
В частности это значит, что такой язык не знает,что такое железо Но не только это...

В идеале язык самого высокого уровня должен понимать человеческую речь )

@Igor3D · 27.01.2022, 08:30

Вот еще неделька прошла, вторая пробегает... Можно увидеть аналитическое решение?

@mirekua · 29.01.2022, 16:03 **[ТС]**

Сообщение от Igor3D

Можно увидеть аналитическое решение

Оказалось что ))) гы-гы ) Решение можно забацать конкретно для моего случая

А вот универсальные формулы и решения поиска центроида не подойдут Потому-что они анализируют массив точек...

А то, что эти точки являются центрами кругов и надо учитывать радиусы и то как идет дуга ) этим решениям в общем до лампочки

Ну и поэтому они не подходят мне И я сочинил что-то свое

Но мое решение работает. И там еще такая штука, что если круги не окружают пустое пространство, а находятся например строго слева/справа от него ТО не надо искать центр в этом пространстве...

и т.д.

В общем вот Я себе решил )

Добавлено через 9 минут
Еще в сети постоянно попадается это решение "улучшенное" ) универсальное для поиска центра точек

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var pts = [...points];
  var first = pts[0], last = pts[pts.length-1];
   if (first.x != last.x || first.y != last.y) pts.push(first);
   var twicearea=0,
   x=0, y=0,
   nPts = pts.length,
   p1, p2, f;
   for ( var i=0, j=nPts-1 ; i<nPts ; j=i++ ) {
      p1 = {...pts[i]}; p2 = {...pts[j]};
      f = p1.x*p2.y - p2.x*p1.y;
      twicearea += f;          
      x += ( p1.x + p2.x ) * f;
      y += ( p1.y + p2.y ) * f;
   };
   f = twicearea * 3;
   return { 'x':x/f, 'y':y/f };

И оно конкретно вешает комп ) и не работает Я не стал разбираться почему Оно мне все равно не подходит

Но как универсальное в нем может быть что-то ценное )

@Igor3D · 30.01.2022, 09:03

Сообщение от mirekua

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

Никто и не говорил брать центры кругов, предлагалась (очевидная) аппроксимация непокрытой области множеством точек.

Возможно проблема в том что найти центр тяжести полученного массива точек оказывается не так уж просто. Он (вроде бы) не равен "среднему", но в чем разница и как его искать - хз, бегло глянув я не увидел чего-то простого

Сообщение от mirekua

И я сочинил что-то свое
Но мое решение работает. ...
В общем вот Я себе решил )

Так а где Ваше решение? Можно на него посмотреть?

Сообщение от mirekua

И оно конкретно вешает комп )

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

@mirekua · 30.01.2022, 14:26 **[ТС]**

Сообщение от Igor3D

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

Центр множества точек не будет центром непокрытой кругами области для которых эти точки являются центрами

Тут как ни крути!

Это просто себе представить на таком примере
х___х х
х х ____ х х х х х
х______ х__ х___ х х
х______ х___ х___ х___ х х х___ х

Тут Х это точки

Так вот геометрический центр тяжести или центроид не будет в пустой области

Добавлено через 5 минут

Сообщение от Igor3D

где Ваше решение? Можно на него посмотреть?

У меня это не один алгоритм, а набор

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

Исходя из примера тогда у нас получаются такие пары кругов для рассмотрения 8 и 17, 12 и 7, 10 и 17, 10 и 7, 11 и 7, 11 и 17

Ну а дальше оставшиеся пары разбирают другие алгоритмы

@Igor3D · 01.02.2022, 09:23

Сообщение от mirekua

Центр множества точек не будет центром непокрытой кругами области для которых эти точки являются центрами

"Знову за рибу грошi"

Ну причем тут центры кругов? Речь идет о точках которые остались после "вычитания" этих кругов. Для хорошей точности таких точек должно быть много, счет на миллионы.

Ну и дальше дело сводится к известной задаче, которая, однако, не так уж проста и очевидна. Викуся пишет

Однако такой простой формулы для геометрического центра не известно. Даже было показано, что не существует ни явной формулы[en], ни точного алгоритма, использующего только арифметические операции и операции извлечения корней. Таким образом, существуют только аппроксимации для решения данной задачи[16].

Сообщение от mirekua

У меня это не один алгоритм, а набор

Ну "велик" - дело благородное (сам заядлый велосипедист). Но как проверить что найденный Вами центр верен? Может использовать предложенную аппроксимацию хотя бы для проверки, это достаточно просто

Сообщение от mirekua

Ну а дальше оставшиеся пары разбирают другие алгоритмы

Часто отрицательная сторона велика = он не "закрывает вопрос". Типа, да, вроде работает, но вот появился новый вариант/расклад где нет. И опять приходится лезть и доделывать, и это становится источником постоянных забот.

Не спешите возражать, возможно Вы вспомните эти соображения когда поостынете

Ну а если асе сделали, и все работает - ну и слава богу

@mirekua · 01.02.2022, 16:17 **[ТС]**

Сообщение от Igor3D

как проверить что найденный Вами центр верен?

Это Вы все усложняете. Конечно задача на самом деле гораздо сложнее

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

И снова будет пролет со строго геометрическим центром

Тут без велосипеда никак. Потому-что все это надо для решения специфичных задач

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

Новые блоги и статьи Все статьи Все блоги /
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .	Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .	Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм anaschu 30.08.2026 Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .	Оттачиваю умение писать js программы. russiannick 30.08.2026 Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	17.01.2022, 14:54
	Для чего вообще этот центр? Требования к скорости работы так и нет. Это для игры? Для чего изначально? 0

@Igor3D 1980 / 836 / 115 Регистрация: 01.10.2012 Сообщений: 5,201 Записей в блоге: 2
	27.01.2022, 08:30
	Вот еще неделька прошла, вторая пробегает... Можно увидеть аналитическое решение? 0