Спосіб побудови ізоліній на областях довільної форми

Реферат: Спосіб побудови ізоліній на областях довільної форми вимірювання значення фізичної величини, будування рівномірної сітки, виділяння блока i запам'ятовування його координат, заповнення масиву точок сітки, знаходження першої точки ізолінії на сітці блока і відкидання відповідної точки з масиву, виключення з аналізу вже оброблених блоків. UA 74964 U (12) UA 74964 U UA 74964 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до області комп'ютерної графіки і може бути застосована для побудови ізоліній значень фізичних величин, заданих на областях довільної форми, переважно в картографії та аналізі даних. Відомий спосіб та система для побудови ізоліній, що використовує дані груп тривимірних точок (Патент Японії 2003317112 (А), клас G01B 21/20, опублікований 07.11.2003). Цей спосіб полягає в тому, що зчитують виміряні дані групи точок, середня лінія якої відповідає рівню ізолінії; потім з групи точок, що лежать на прямій лінії біля середньої точки, визначають саму цю пряму, і визначають середню точку згаданої прямої. З'єднавши визначені середні точки, отримують ізолінію. Недоліком такого способу є складність його реалізації та неефективність з точки зору обчислень. Крім того, отримана ізолінія складається з сегментів прямої (ламана лінія), що не відповідає вимогам застосування його, наприклад, в картографії. Відомий також спосіб генерації ізоліній в реальному часі (Міжнародний патент РСТ WO 2005/088557, клас G06T 17/00, опублікований 09.03.2005). Цей спосіб полягає в генерації ізоліній з рядків та стовпчиків даних за такими кроками: 1) з рядків та стовпчиків вибирають першу точку даних, що відповідає першому стану; 2) другу точку порівнюють з першим станом; 3) визначають, чи існує ізолінія; 4) перший стан змінюють на другий, якщо ізолінія існує; 5) якщо ізолінія існує, виводять відповідний фрагмент ізолінії; 6) виконують перехід на наступну точку; 7) кроки 2) - 7) повторюються для наступного рядка чи стовпчика. Безумовними перевагами способу є його швидкодія та низькі вимоги до апаратного забезпечення, на якому спосіб можна реалізувати. Недоліками способу є те, що його алгоритм орієнтовано на роботу тільки на областях прямокутної форми і те, що отримана ізолінія складається з сегментів прямої (ламана лінія), що не відповідає вимогам застосування його, наприклад, в картографії. Найближчим аналогом до способу, що заявляється, є спосіб, запропонований Томасом Пулліамом і реалізований у програмі NeXTcontour1.7 [1]. Спосіб полягає у виконанні таких дій: за допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати, на області, що має прямокутну форму, будують рівномірну сітку і, якщо розміри сітки великі, виділяють блок (врахувавши оброблені блоки) і запам'ятовують його координати і працюють з цим блоком, а інакше працюють з сіткою як з блоком, тобто заповнюють масив точок сітки, між якими відбувається перехід через заданий рівень, знаходять першу точку ізолінії на сітці блока і відкидають відповідну точку з масиву, знаходять наступну точку ізолінії і відкидають відповідну точку з масиву, а у випадку, коли точка - вже в масиві точок ізолінії, цю точку в масив точок ізолінії не додають, якщо вийшли на точку на границі прямокутної області, блока або в першу точку ізолінії, будують ізолінію, з'єднавши її точки відрізками прямих, виводять її на носій інформації або екран і, якщо залишились необроблені точки масиву, повторюють процедуру пошуку точок ізолінії, починаючи з першої, а якщо залишились необроблені точки сітки, повторюють весь процес з початку роботи з сіткою, виключивши з аналізу вже оброблені блоки. Суттєвими недоліками цього способу є те, що він забезпечує побудову ізоліній лише на прямокутних однозв'язних областях, а також не дає змоги будувати плавні лінії (отримана ізолінія є ламаною лінією), що не відповідає вимогам застосування способу, наприклад, в картографії. В основу корисної моделі поставлена задача вдосконалити відомий спосіб шляхом зміни алгоритму побудови таким чином, щоб забезпечити побудову ізоліній (ліній рівня) на областях довільної форми, в тому числі багатоконтурних, причому отримати як ізолінії, що є ламаними лініями, так і плавні криві ізоліній. Поставлена задача вирішується тим, що в способі побудови ізоліній на областях довільної форми, який полягає в тому, що за допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати, на області що має прямокутну форму, будують на ній рівномірну сітку і, якщо розміри сітки великі, виділяють блок (врахувавши оброблені блоки) і запам'ятовують його координати і працюють з цим блоком, а інакше працюють з сіткою як з блоком, тобто заповнюють масив точок сітки, між якими відбувається перехід через заданий рівень, знаходять першу точку ізолінії на сітці блока і відкидають відповідну точку з масиву, знаходять наступну точку ізолінії і відкидають відповідну точку з масиву, а у випадку, коли точка - вже є в масиві точок ізолінії, цю точку в масив точок ізолінії не додають, якщо вийшли на точку на границі прямокутної області, блока або в першу точку ізолінії, будують ізолінію, з'єднавши її 1 UA 74964 U 5 10 15 20 25 30 35 40 45 50 точки відрізками прямих, виводять її на носій інформації або екран і, якщо залишились необроблені точки масиву, повторюють процедуру пошуку точок ізолінії, починаючи з першої, а якщо залишились необроблені точки сітки, повторюють весь процес з початку роботи з сіткою, виключивши з аналізу вже оброблені блоки, згідно з корисною моделлю, за допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати, на області довільної форми, згадану область довільної форми доповнюють до прямокутної, будують на ній рівномірну прямокутну сітку, а всім точкам сітки, в яких не визначено дані вимірювань, приписують певне контрольне значення; а крім того, в процесі побудови ізоліній, якщо вийшли на точку на границі прямокутної області, точку, дані в якій рівні контрольному значенню, границю блока або в першу точку ізолінії, будують ізолінію, з'єднавши її точки відрізками прямих або ж за допомогою шматкової інтерполяції координат отриманих точок поліномами Ерміта (окремо по координаті х, окремо по координаті у), використавши визначені точки ізолінії як опорні точки поліномів, виводять її на носій інформації або екран. Технічний результат досягається за рахунок того, що за допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати на області довільної форми, згадану область довільної форми доповнюють до прямокутної, на ній будують рівномірну прямокутну сітку, а всім точкам сітки, в яких не визначено дані вимірювань, приписують певне контрольне значення, після чого проводять виділення блоків і, якщо вийшли на точку на границі прямокутної області, точку, дані в якій рівні контрольному значенню, границю блока або в першу точку ізолінії, будують ізолінію з'єднавши її точки відрізками прямих, або ж за допомогою шматкової інтерполяції координат отриманих точок поліномами Ерміта (окремо по координаті х, окремо по координаті у), використавши визначені точки ізолінії як опорні точки поліномів, і виводять її на носій інформації або екран. Це дає змогу врахувати при побудові те, що виміряні дані задано на області довільної форми, причому область може бути багатозв'язною. Крім того, отримані ізолінії можуть бути як ламаними, так і гладкими - при застосуванні інтерполяції. Даний спосіб реалізується шляхом виконання такої послідовності дій: За допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати, на області довільної форми. Відповідна процедура вимірювання та устаткування визначається природою фізичної величини. Потім згадану область довільної форми доповнюють до прямокутної, будують на ній рівномірну сітку, а всім точкам сітки, в яких не визначено дані вимірювань, приписують певне контрольне значення. Вибір такого значення повністю визначається природою фізичної величини; рекомендовано вибирати таке значення, яке фізична величина не набуває за будьяких умов її вимірювання (наприклад, для даних глибини або висоти можна взяти як контрольне значення «-1 м»). Якщо розміри сітки великі, виділяють блок (врахувавши оброблені блоки) і запам'ятовують його координати і працюють з цим блоком, а інакше працюють з сіткою як з блоком. Розміри оброблюваного блока повністю визначається розмірами та роздільною здатністю або обчислювальною потужністю застосованої для побудови ізоліній апаратури. Заповнюють масив точок сітки, між якими відбувається перехід через заданий рівень, знаходять першу точку ізолінії на сітці блока і відкидають відповідну точку з масиву. Знаходять наступну точку ізолінії і відкидають відповідну точку з масиву, а у випадку, коли точка - вже є в масиві точок ізолінії, цю точку в масив точок ізолінії не додають. Якщо вийшли на точку на границі прямокутної області, точку, дані в якій рівні контрольному значенню, границю блока або в першу точку ізолінії, будують ізолінію, з'єднавши її точки відрізками прямих або ж за допомогою шматкової інтерполяції координат отриманих точок поліномами Ерміта (окремо по координаті х, окремо по координаті у), використавши визначені точки ізолінії як опорні точки поліномів. Параметри Ермітових багаточленів визначають з формул Pi xi   ai, i  1..n  1 Pi' xi   ai' , i  1..n ; , (1) де рі(х) - і-й інтерполяційний багаточлен 3-го ступеня, що апроксимує функцію на інтервалі [хі; хі+1] (між опорними точками хі та хі+1), aі - значення інтерпольованої величини в і-й точці, n a' 55 кількість точок, i - оцінка похідної інтерпольованої величини в і-й точці. Після розв'язання системи рівнянь (1), лінійної відносно коефіцієнтів багаточленів Рі(х), всередині відповідних інтервалів проводять двовимірну інтерполяцію даних ізоліній. Інтерполяцію Ермітовими поліномами проводять окремо по координаті х, окремо по координаті у, після чого результуючу ізолінію з обчисленими координатами точок (х; у) виводять її на носій інформації або екран. 2 UA 74964 U 5 10 Якщо залишились необроблені точки масиву, повторюють процедуру пошуку точок ізолінії, починаючи з першої. Якщо залишились необроблені точки сітки, повторюють весь процес з початку роботи з сіткою, виключивши з аналізу вже оброблені блоки. Технічний результат використання корисної моделі полягає в тому, що запропонований спосіб дозволяє будувати ізолінії (лінії рівня) на областях довільної форми, в тому числі багатозв'язних, а не лише на прямокутних однозв'язних областях, а також отримати як ізолінії, що є ламаними лініями, так і плавні криві ізоліній. Джерела інформації: 1. Thomas Н. Pulliam. NeXTcontour 1.7 MS 202А-1 NASA Ames Research Center, Moffett Field, СА 94035. Режим доступу (вихідний код та документація): ftp://ftp.padua.org/pub/NeXT/misc/old/science/NeXTcontour_1.7.tar.gz ФОРМУЛА КОРИСНОЇ МОДЕЛІ 15 20 25 30 35 40 1. Спосіб побудови ізоліній на областях довільної форми, який полягає в тому, що за допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати, на області, що має прямокутну форму, будують на ній рівномірну сітку і, якщо розміри сітки великі, виділяють блок (врахувавши оброблені блоки) i запам'ятовують його координати і працюють з цим блоком, а інакше працюють з сіткою як з блоком, тобто заповнюють масив точок сітки, між якими відбувається перехід через заданий рівень, знаходять першу точку ізолінії на сітці блока і відкидають відповідну точку з масиву, знаходять наступну точку ізолінії і відкидають відповідну точку з масиву, а у випадку, коли точка вже є в масиві точок ізолінії, цю точку в масив точок ізолінії не додають, якщо вийшли на точку на границі прямокутної області, блока або в першу точку ізолінії, будують ізолінію, з'єднавши її точки відрізками прямих, виводять її на носій інформації або екран і, якщо залишились необроблені точки масиву, повторюють процедуру пошуку точок ізолінії, починаючи з першої, а якщо залишились необроблені точки сітки, повторюють весь процес з початку роботи з сіткою, виключивши з аналізу вже оброблені блоки, який відрізняється тим, що за допомогою відповідного устаткування вимірюють значення фізичної величини, ізолінії якої слід побудувати, на області довільної форми, згадану область довільної форми доповнюють до прямокутної, будують на ній рівномірну прямокутну сітку, а всім точкам сітки, в яких не визначено дані вимірювань, приписують певне контрольне значення; а крім того, в процесі побудови ізоліній, якщо вийшли на точку на границі прямокутної області, точку, дані в якій рівні контрольному значенню, границю блока або в першу точку ізолінії, будують ізолінію з'єднавши її точки відрізками прямих, виводять її на носій інформації або екран. 2. Спосіб за п. 1, який відрізняється тим, що ізолінію будують за допомогою шматкової інтерполяції координат отриманих точок поліномами Ерміта (окремо по координаті х, окремо по координаті у), використавши визначені точки ізолінії як опорні точки поліномів, і виводять її на носій інформації або екран. Комп’ютерна верстка І. Скворцова Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 3