Загалом, машинки повинні повертати.
Поки без жодних матриць, найпростіший спосіб: знаходимо центр, поміщаємо його в початок координат, повертаємо на потрібний кут і ставимо машинку на місце.
Як знайти описує багатокутник, мені підказали, поки знаходжу центр граничного чотирикутника xMin, yMin, xMax, yMax, а це зовсім не те: при повороті розміри змінюються, центр скаче.
Описану окружність не пропонувати! Якщо у нас за формою якийсь сектор, наприклад, то центр описаного кола може бути за межами багатокутника, причому, на будь-якій відстані від істинного центру (в існування якого я вірю).
Центр тяжкості теж не підходить: якщо в одному місці на кордоні багато точок, а в іншому 3-4, центр ваги поїде до деталізованому краю. (
(Не розумію, чому при додаванні тег "центр" капіталізує. Це не я, чесслово!)
Здається, я придумав. Тільки якось це все. неправильно.
При ініціалізації беремо кордону xMin, xMax, yMin, yMax. Це описує чотирикутник. Його середина - середнє. Прив'язуємо це чотирикутник до машинки і вертимо його разом з нею.
Його центр завжди можна знайти: це перетин діагоналей.
Придумав приблизний евристичний алгоритм з трудомісткістю O (n ^ 2), але це не має значення, адже фігурки можна обрахувати заздалегідь, а потім просто дивитися заздалегідь обчислений центр. Також центр можна шукати при конструюванні машинки, але це потім, набагато потім.
Опис: знаходимо перетин всіх діагоналей опуклого багатокутника - отримуємо ще один опуклий багатокутник всередині. (Мені здається, що він повинен бути опуклим.) 2-3 ітерації, і наблизимося до фактичного центру настільки, що цього буде достатньо.
Тільки от лихо: точок перетину виявилося занадто дохрена, доведеться спочатку для них побудувати описує багатокутник, потім знайти перетин діагоналей, знову побудувати, знову знайти. Евристичний лагорітм не самий продуктивний, та до того ж ще й заплутаний.
Гладко було на папері.
Приклад для 13 точок, а якщо їх більше, виходить повний пипец.
Центр тяжкості може стати в нагоді пізніше, коли різні агрегати на машинки навішувати бум.
- буфер обмена01.png
- буфер обмена02.png
Показати всі посилання цього об'єкта:
Ви також можете додати свою фірму в каталог IT-фірм. і публікувати статті, новини, вакансії і іншу інформацію від імені фірми.
Generation time: 0.738