ការណែនាំអន្តរកម្មចំពោះ quadtrees

ហេតុអ្វី Quadtrees សំខាន់ជាងអ្នកគិត

រាល់ពេលដែលអ្នកបង្រួមដើម្បីពង្រីកនៅលើផែនទីឌីជីថល សាកសួរភោជនីយដ្ឋានដែលនៅជិតៗ ឬមើលកម្មវិធីតាមដានកងនាវាក្នុងពេលជាក់ស្តែង ធ្វើបច្ចុប្បន្នភាពរូបតំណាងរថយន្តរាប់សិបដោយគ្មានកម្មវិធីរុករករបស់អ្នកឈប់ដំណើរការ វាមានឱកាសល្អដែល quadtree កំពុងធ្វើការលើកយ៉ាងខ្លាំងនៅពីក្រោយឆាក។ Quadtrees គឺជារចនាសម្ព័ន្ធទិន្នន័យដ៏ប្រណិតមួយ ដែលមនុស្សភាគច្រើនមិនដែលលឺអំពី ប៉ុន្តែពួកវាផ្តល់ថាមពលយ៉ាងស្ងៀមស្ងាត់នូវប្រព័ន្ធសំខាន់ៗមួយចំនួននៅក្នុងកម្មវិធីទំនើប - ពីការរកឃើញការប៉ះទង្គិចគ្នានៃវីដេអូហ្គេម រហូតដល់ប្រព័ន្ធព័ត៌មានភូមិសាស្រ្តដែលដំណើរការសំណួររាប់លានក្នុងមួយវិនាទី។ ការយល់ដឹងពីរបៀបដែលពួកគេធ្វើការមិនត្រឹមតែធ្វើឱ្យអ្នកក្លាយជាអ្នកអភិវឌ្ឍន៍កាន់តែប្រសើរឡើងប៉ុណ្ណោះទេ។ វាផ្លាស់ប្តូរជាមូលដ្ឋានអំពីរបៀបដែលអ្នកគិតអំពីការរៀបចំ និងការស្វែងរកតាមរយៈទិន្នន័យលំហ។ មិនថាអ្នកកំពុងបង្កើតវេទិកាដឹកជញ្ជូន ផ្ទាំងគ្រប់គ្រងទិន្នន័យផ្អែកលើទីតាំង ឬគ្រាន់តែព្យាយាមបង្ហាញចំណុចទិន្នន័យ 50,000 នៅលើផ្ទាំងក្រណាត់ដោយមិនធ្វើឱ្យកម្មវិធីរុករកតាមអ៊ីនធឺណិតគាំងនោះ quadtrees ផ្តល់នូវដំណោះស្រាយដែលមានលក្ខណៈវិចារណញាណ និងមានប្រសិទ្ធភាពគួរឱ្យកត់សម្គាល់។

តើ Quadtree ជាអ្វី?

quadtree គឺជារចនាសម្ព័ន្ធទិន្នន័យដើមឈើ ដែលគ្រប់ថ្នាំងខាងក្នុងមានកូនបួនយ៉ាងពិតប្រាកដ ដែលនីមួយៗតំណាងឱ្យ quadrant មួយនៃចន្លោះពីរវិមាត្រ។ ស្រមៃថាយកតំបន់ការ៉េមួយ ហើយបែងចែកវាជាបួនការ៉េស្មើគ្នា - ភាគពាយព្យ ឦសាន និរតី និងអាគ្នេយ៍។ ការ៉េនីមួយៗអាចបែងចែកជាបួនការ៉េបន្ថែមទៀត ហើយបន្តបន្ទាប់ទៀត រហូតដល់អ្នកឈានដល់លក្ខខណ្ឌឈប់។ លក្ខខណ្ឌ​បញ្ឈប់​នោះ​ជា​ធម្មតា​ទាំង​ជម្រៅ​អតិបរមា ឬ​កម្រិត​សម្រាប់​ចំនួន​ទិន្នន័យ​ដែល​ថ្នាំង​មួយ​អាច​រក្សា​បាន​មុន​ពេល​វា​ត្រូវ​បំបែក។

ភាពស្រស់ស្អាតនៃវិធីសាស្រ្តនេះស្ថិតនៅក្នុងលក្ខណៈប្រែប្រួលរបស់វា។ តំបន់ដែលក្រាស់ជាមួយនឹងចំណុចទិន្នន័យត្រូវបានបែងចែកទៅជាកោសិកាល្អិតល្អន់ និងល្អិតល្អន់ ខណៈដែលតំបន់តូចៗនៅតែជាតំបន់ធំ និងមិនមានការបែងចែក។ បួនជ្រុងដែលរក្សាទុកទីតាំងនៃហាងកាហ្វេ 10,000 នៅទូទាំងប្រទេសនឹងបង្កើតផ្នែករងយ៉ាងលម្អិតនៅលើ Manhattan ដែលជាកន្លែងអាចមានហាងចំនួន 300 ក្នុងរយៈពេលពីរបីគីឡូម៉ែត្រការ៉េ ខណៈដែលរក្សាតំបន់ជនបទ Wyoming ដ៏ធំទូលាយជាថ្នាំងតែមួយដែលមិនបំបែកដែលមានសូន្យឬមួយចំណុច។ ការដោះស្រាយការសម្របខ្លួននេះ គឺជាអ្វីដែលធ្វើឱ្យ quadtrees មានថាមពលខ្លាំងបើប្រៀបធៀបទៅនឹងក្រឡាចត្រង្គរាបស្មើ ដែលនឹងខ្ជះខ្ជាយអង្គចងចាំយ៉ាងច្រើននៅលើក្រឡាទទេ។

គំនិតនេះត្រូវបានពិពណ៌នាជាលើកដំបូងដោយ Raphael Finkel និង J.L. Bentley ក្នុងឆ្នាំ 1974 ហើយចាប់តាំងពីពេលនោះមក វាបានបែងចែកទៅជាវ៉ារ្យ៉ង់ជាច្រើន៖ point quadtrees រក្សាទុកគូកូអរដោនេនីមួយៗ quadtrees តំបន់ តំណាងឱ្យតំបន់លំហ (មានប្រយោជន៍សម្រាប់ការបង្ហាប់រូបភាព) និងបន្ទាត់កោង។ បំរែបំរួលនីមួយៗធ្វើឱ្យប្រសើរសម្រាប់ករណីប្រើប្រាស់ផ្សេងៗគ្នា ប៉ុន្តែគោលការណ៍បែងចែករងដែលកើតឡើងដដែលៗនៅតែដូចគ្នាចំពោះពួកវាទាំងអស់។

របៀបដែលការបញ្ចូល និងការសួរដំណើរការ

ដើម្បីបញ្ចូលចំណុចទៅក្នុង quadtree អ្នកចាប់ផ្តើមពីថ្នាំងឫស ហើយកំណត់ថាតើមួយណាក្នុងចំណោមបួនជ្រុងដែលចំណុចធ្លាក់ចូលទៅក្នុង។ បន្ទាប់​មក អ្នក​បញ្ចូល​ទៅក្នុង​ថ្នាំង​កូន​របស់ quadrant ហើយ​ធ្វើ​ដំណើរ​ការ​ម្តងទៀត។ ប្រសិនបើអ្នកឈានដល់ថ្នាំងស្លឹកដែលមិនលើសពីសមត្ថភាពរបស់វា (ជាធម្មតាកំណត់ទៅ 1 ឬ 4 ពិន្ទុ) អ្នកគ្រាន់តែរក្សាទុកចំណុចនៅទីនោះ។ ប្រសិនបើស្លឹកមានលទ្ធភាពរួចហើយ វាបំបែកជាបួនកូន ចែកចាយឡើងវិញនូវចំណុចដែលមានស្រាប់ក្នុងចំនោមពួកវា ហើយបន្ទាប់មកបញ្ចូលចំណុចថ្មីទៅក្នុងកូនដែលសមស្រប។ ដំណើរការនេះជាធម្មតាបញ្ចប់នៅក្នុងពេលវេលា O(log n) សម្រាប់ការចែកចាយដែលមានតុល្យភាព ទោះបីជាសេណារីយ៉ូករណីអាក្រក់បំផុតដែលមានទិន្នន័យជាក្រុមខ្លាំងអាចបន្ថយដំណើរការក៏ដោយ។

ការសាកសួរតាមជួរ — ការស្វែងរកចំណុចទាំងអស់នៅក្នុងតំបន់ចតុកោណកែងដែលបានផ្តល់ឱ្យ — គឺជាកន្លែងដែលដើមឈើបួនជ្រុងភ្លឺច្បាស់។ ជំនួសឱ្យការពិនិត្យមើលរាល់ចំណុចនីមួយៗក្នុងសំណុំទិន្នន័យរបស់អ្នក (ប្រតិបត្តិការ O(n)) អ្នកចាប់ផ្តើមពីឫស ហើយសួរសំណួរសាមញ្ញមួយនៅថ្នាំងនីមួយៗ៖ តើព្រំដែនរបស់ថ្នាំងនេះប្រសព្វជាមួយចតុកោណកែងស្វែងរករបស់ខ្ញុំទេ? បើមិនដូច្នេះទេ អ្នកកាត់ចេញនូវមែកធាងរងទាំងមូល ដែលអាចលុបបំបាត់រាប់ពាន់ពិន្ទុពីការពិចារណាក្នុងការប្រៀបធៀបតែមួយ។ ប្រសិនបើមានចំនុចប្រសព្វ អ្នកនិយាយឡើងវិញទៅក្នុងកុមារដែលពាក់ព័ន្ធ។ ចំណុចដែលបានរកឃើញនៅក្នុងថ្នាំងស្លឹកដែលធ្លាក់ក្នុងចតុកោណកែងស្វែងរកត្រូវបានបន្ថែមទៅក្នុងសំណុំលទ្ធផល។

ពិចារណាឧទាហរណ៍ជាក់ស្តែង៖ អ្នកមានសំណុំទិន្នន័យនៃទីតាំងអតិថិជន 100,000 ហើយត្រូវស្វែងរកអ្នកគ្រប់គ្នាក្នុងរង្វង់ 5 គីឡូម៉ែត្រនៃការបើកហាងថ្មី។ វិធីសាស្រ្ត brute-force ទាមទារការគណនាចម្ងាយ 100,000 ។ quadtree ដែលត្រូវបានសាងសង់យ៉ាងល្អអាចកាត់បន្ថយវាមកត្រឹម 200-500 ការត្រួតពិនិត្យដោយលុបបំបាត់តំបន់ភូមិសាស្ត្រទាំងមូលយ៉ាងឆាប់រហ័សដែលមិនត្រួតលើគ្នាជាមួយតំបន់ស្វែងរករបស់អ្នក។ នោះ​ជា​ការ​ធ្វើ​ឱ្យ​ប្រសើរ​ឡើង​នៃ​ការ​អនុវត្ត 200x ឬ​ច្រើន​ជាង​នេះ — ភាព​ខុស​គ្នា​រវាង​សំណួរ​ដែល​ចំណាយ​ពេល 800 មិល្លីវិនាទី និង​ការ​យក 4 មិល្លីវិនាទី។

កម្មវិធីពិភពពិតដែលដំណើរការលើ Quadtrees

កម្មវិធីរបស់ quadtrees លាតសន្ធឹងលើសពីវិទ្យាសាស្ត្រកុំព្យូទ័រ។ ពួកវាជាមូលដ្ឋានសម្រាប់ប្រព័ន្ធដែលមនុស្សរាប់ពាន់លាននាក់ប្រើប្រាស់ប្រចាំថ្ងៃ ជារឿយៗដោយមិនដឹងខ្លួន។

• ការគូសផែនទី និងការរុករក៖ សេវាកម្មដូចជា Google Maps និង Mapbox ប្រើប្រាស់ប្រព័ន្ធក្រឡាក្បឿងដូចបួនជ្រុង ដើម្បីបម្រើរូបភាពផែនទី។ កម្រិតពង្រីកនីមួយៗបែងចែកក្រឡាទៅជាកូនបួន ដែលនេះជាមូលហេតុដែលកូអរដោនេនៃក្រឡាផែនទីធ្វើតាមលំនាំ z/x/y ដែលឆ្លុះបញ្ចាំងពីអាសយដ្ឋាន quadtree ។ នៅពេលអ្នកពង្រីកចូលទៅក្នុងប្លុកទីក្រុង មានតែក្រឡាដែលមានគុណភាពបង្ហាញខ្ពស់ដែលពាក់ព័ន្ធប៉ុណ្ណោះដែលផ្ទុក — ពិភពលោកដែលនៅសល់នឹងរក្សាគុណភាពបង្ហាញមិនច្បាស់។
• ការរកឃើញការប៉ះទង្គិចនៅក្នុងហ្គេម៖ ម៉ាស៊ីនហ្គេមប្រើ quadtrees (និងសមភាគី 3D របស់ពួកគេ octrees) ដើម្បីរកឃើញយ៉ាងមានប្រសិទ្ធភាពនៅពេលដែលវត្ថុបុកគ្នា។ ជំនួសឱ្យការសាកល្បងវត្ថុនីមួយៗ — សុបិន្តអាក្រក់ O(n²) ជាមួយនឹងធាតុ 1,000 នៅលើអេក្រង់ — ម៉ាស៊ីនពិនិត្យតែវត្ថុដែលចែករំលែកក្រឡា quadtree ដូចគ្នា ដោយកាត់បន្ថយការត្រួតពិនិត្យទៅជាលេខដែលអាចគ្រប់គ្រងបាន។
• ការបង្ហាប់រូបភាព៖ តំបន់ quadtrees អាចបង្ហាប់រូបភាពដោយបញ្ចូលភីកសែលជាប់គ្នាដែលចែករំលែកពណ៌ស្រដៀងគ្នាទៅជាប្លុកធំជាង។ នេះ​ជា​មូលដ្ឋាន​នៃ​ក្បួន​ដោះស្រាយ​ការ​បង្ហាប់​ជាក់លាក់​ដែល​សម្រេច​បាន​សមាមាត្រ​បង្ហាប់ 10:1 ខណៈ​ដែល​រក្សា​បាន​នូវ​ភាព​ស្មោះត្រង់​ដែល​មើល​ឃើញ​នៅ​ក្នុង​ផ្នែក​ដែល​មាន​ភាព​លម្អិត​ទាប។
• ការគ្រប់គ្រងកងនាវាចរ និងការដឹកជញ្ជូន៖ ក្រុមហ៊ុនដឹកជញ្ជូនប្រើប្រាស់សន្ទស្សន៍ទំហំដើម្បីផ្គូផ្គងអ្នកបើកបរជាមួយនឹងការបញ្ជាទិញនៅក្បែរនោះក្នុងពេលជាក់ស្តែង។ quadtree អនុញ្ញាតឱ្យប្រព័ន្ធបញ្ជូនភ្លាមៗឆ្លើយសំណួរ "តើអ្នកបើកបរ 5 នាក់ណាដែលនៅជិតបំផុតនឹងទីតាំងទទួលនេះ?" នៅទូទាំងកងនាវារាប់ពាន់គ្រឿងដែលធ្វើបច្ចុប្បន្នភាពទីតាំង GPS របស់ពួកគេរៀងរាល់ពីរបីវិនាទី។
• ការវិភាគភូមិសាស្ត្រ៖ វេទិកាដែលប្រមូលផ្តុំទិន្នន័យអាជីវកម្មផ្អែកលើទីតាំង — ផែនទីដង់ស៊ីតេអតិថិជន ការបង្កើនតំបន់លក់ ការវិភាគទីតាំងហាង — ពឹងផ្អែកលើរចនាសម្ព័ន្ធទិន្នន័យទំហំដើម្បីធ្វើឱ្យសំណួរទាំងនេះមានអន្តរកម្មជាជាងដំណើរការជាបាច់។

ការយល់ដឹងសំខាន់នៅពីក្រោយ quadtrees គឺថា សំណួរទំហំភាគច្រើន មិនចាំបាច់ពិនិត្យមើលទិន្នន័យភាគច្រើននោះទេ។ តាមរយៈការរៀបចំលំហតាមឋានានុក្រម អ្នកបំប្លែងការស្វែងរកដោយកម្លាំង brute-force ទៅជាការឆ្លងកាត់គោលដៅ — បង្វែរវិនាទីទៅជាមិល្លីវិនាទី និងធ្វើឱ្យអន្តរកម្មតាមពេលវេលាជាក់ស្តែងអាចធ្វើទៅបាន ទោះបីជាមានសំណុំទិន្នន័យដ៏ធំក៏ដោយ។

ការកសាង Quadtree ពីកោស

ការអនុវត្ត quadtree មូលដ្ឋានគឺអាចទាក់ទងបានគួរឱ្យភ្ញាក់ផ្អើល សូម្បីតែសម្រាប់អ្នកអភិវឌ្ឍន៍កម្រិតមធ្យមក៏ដោយ។ រចនាសម្ព័ន្ធស្នូលត្រូវការសមាសធាតុមួយចំនួនប៉ុណ្ណោះ៖ ព្រំដែន (ផ្ទៃចតុកោណដែលថ្នាំងគ្របដណ្តប់), សមត្ថភាព (ពិន្ទុអតិបរមាមុនពេលបំបែក), ចំណុចអារេ និងសេចក្តីយោងទៅថ្នាំងកូនបួន (ដំបូងឡើយចាត់ទុកជាមោឃៈ)។ មុខងារបញ្ចូលទាំងមូលអាចត្រូវបានសរសេរនៅក្រោម 30 ជួរនៃកូដជាភាសាភាគច្រើន។

ប្រតិបត្តិការបំបែកបង្កើតថ្នាំងកូនថ្មីចំនួនបួន ដែលនីមួយៗគ្របដណ្ដប់លើបួនជ្រុងនៃព្រំដែនរបស់មេ។ សម្រាប់មាតាបិតាដែលមានព្រំដែន (x, y, ទទឹង, កម្ពស់) កូនភាគឦសានទទួលបាន (x + ទទឹង/2, y, ទទឹង/2, កម្ពស់/2) ភាគពាយ័ព្យទទួលបាន (x, y, ទទឹង/2, កម្ពស់/2) ហើយដូច្នេះនៅលើ។ បនា្ទាប់ពីពុះរួចចំនុចដែលមានស្រាប់ត្រូវបានចែកចាយឡើងវិញទៅក្នុងកូនដែលសមស្រប។ កំហុសទូទៅមួយគឺការភ្លេចសម្អាតអារេពិន្ទុរបស់មេបន្ទាប់ពីការចែកចាយឡើងវិញ ដែលនាំឱ្យលទ្ធផលស្ទួនអំឡុងពេលសំណួរ។

សម្រាប់ការប្រើប្រាស់ផលិតកម្ម ការបង្កើនប្រសិទ្ធភាពជាច្រើនមានសារៈសំខាន់។ ការកំណត់សមត្ថភាពថ្នាំងដល់ 4-8 ពិន្ទុជាធម្មតាដំណើរការលើសពីសមត្ថភាព 1 ព្រោះវាកាត់បន្ថយជម្រៅដើមឈើ និងផ្នែកលើសនៃវត្ថុថ្នាំង។ ការបន្ថែម ដែនកំណត់ជម្រៅអតិបរមា (ជាធម្មតា 8-12 កម្រិត) ការពារករណីរោគសាស្ត្រ ដែលចំណុចជាច្រើនចែករំលែកកូអរដោនេដូចគ្នាពីការបង្កើតដើមឈើជ្រៅគ្មានកំណត់។ ហើយសម្រាប់សំណុំទិន្នន័យថាមវន្តដែលចំណុចផ្លាស់ទី — ដូចជាការតាមដានយានយន្ត — អ្នកនឹងចង់បានយន្តការដកចេញ ឬយុទ្ធសាស្ត្រដើម្បីសាងសង់ដើមឈើឡើងវិញជាទៀងទាត់ ដោយសារដើមឈើបួនជ្រុងមិនមានតុល្យភាពដោយខ្លួនឯងដូចដើមឈើក្រហម-ខ្មៅធ្វើ។

បួនជ្រុងនៅក្នុងវេទិកាពាណិជ្ជកម្ម និងការវិភាគ

វេទិកាធុរកិច្ចទំនើបកាន់តែដោះស្រាយជាមួយទិន្នន័យលំហ មិនថាជាទីតាំងអតិថិជន តំបន់ចែកចាយ ទឹកដីលក់ ឬការតាមដានទ្រព្យសកម្មនោះទេ។ បញ្ហា​ប្រឈម​មិន​មែន​គ្រាន់​តែ​ជា​ការ​រក្សា​ទុក​ទិន្នន័យ​នេះ​ប៉ុណ្ណោះ​ទេ វា​កំពុង​ធ្វើ​ឱ្យ​វា​អាច​សួរ​បាន​ក្នុង​ពេល​វេលា​ពិត​ប្រាកដ​ក្នុង​ទំហំ។ នៅពេលដែលអាជីវកម្មដែលកំពុងដំណើរការនៅទូទាំង 50 ទីក្រុងត្រូវការមើលឃើញពីដង់ស៊ីតេអតិថិជន អ្នកបើកបរដឹកជញ្ជូនផ្លូវ ឬវិភាគប្រតិបត្តិការលក់ក្នុងតំបន់ យុទ្ធសាស្ត្រកំណត់ទំហំមូលដ្ឋានកំណត់ថាតើផ្ទាំងគ្រប់គ្រងផ្ទុកក្នុងរយៈពេល 200 មីលីវិនាទី ឬ 20 វិនាទី។

នេះគឺជាវេទិកាហេតុផលមួយដូចជា Mewayz — ដែលរួមបញ្ចូលម៉ូឌុល 207 ដែលលាតសន្ធឹង CRM វិក្កយបត្រ ការគ្រប់គ្រងកងនាវា ការកក់ និងការវិភាគទៅក្នុងប្រព័ន្ធប្រតិបត្តិការអាជីវកម្មតែមួយ — ទទួលបានអត្ថប្រយោជន៍ពីការគ្រប់គ្រងទិន្នន័យប្រកបដោយប្រសិទ្ធភាពនៅក្រោមក្រណាត់។ នៅពេលដែលម៉ូឌុលគ្រប់គ្រងកងនាវាត្រូវការបង្ហាញយានជំនិះសកម្មចំនួន 500 នៅលើផែនទី ឬនៅពេលដែលម៉ូឌុល CRM មើលឃើញទីតាំងអ្នកប្រើប្រាស់ 138,000+ សម្រាប់ការធ្វើផែនការទឹកដី វិធីសាស្ត្រឆោតល្ងង់មិនធ្វើមាត្រដ្ឋានទេ។ រចនាសម្ព័ន្ធលិបិក្រមទំហំដូចជា quadtrees (ឬសមមូលមូលដ្ឋានទិន្នន័យរបស់ពួកគេ ដូចជា PostGIS R-trees និង MySQL spatial indexes) ធ្វើឱ្យវាមានលទ្ធភាពក្នុងការផ្តល់ជូននូវលក្ខណៈពិសេសទាំងនេះដោយមិនទាមទារផ្នែករឹងកម្រិតសហគ្រាស។

សម្រាប់អាជីវកម្មដែលវាយតម្លៃលើវេទិកា ការយកតាមខ្លួនគឺមានប្រយោជន៍៖ ឧបករណ៍ដែលគ្រប់គ្រងទីតាំង និងទិន្នន័យទំហំបានល្អ មិនមែនគ្រាន់តែប្រើក្បួនដោះស្រាយដ៏ប្រណិតសម្រាប់ជាប្រយោជន៍របស់វាប៉ុណ្ណោះទេ។ ពួកគេកំពុងធ្វើឱ្យមានភាពខុសគ្នារវាងប្រព័ន្ធកក់ដែលអាចបង្ហាញអ្នកផ្តល់សេវាដែលមានភ្លាមៗក្នុងចម្ងាយ 10 គីឡូម៉ែត្រ និងមួយដែលត្រូវចំណាយពេល 8 វិនាទីដើម្បីផ្ទុកលទ្ធផលដូចគ្នា។ ការអនុវត្តនៅកម្រិតនេះបកប្រែដោយផ្ទាល់ទៅជាបទពិសោធន៍អ្នកប្រើប្រាស់ ហើយចុងក្រោយគឺចំណូល។

Quadtrees ធៀបនឹងរចនាសម្ព័ន្ធទិន្នន័យ Spatial ផ្សេងទៀត

Quadtrees មិន​មែន​ជា​ជម្រើស​តែ​មួយ​គត់​សម្រាប់​ការ​ធ្វើ​លិបិក្រម​លំហ​ទេ ហើយ​ការ​យល់​ពី​ជម្រើស​ជួយ​អ្នក​ជ្រើសរើស​ឧបករណ៍​ត្រឹមត្រូវ។ R-trees ដែលត្រូវបានប្រើយ៉ាងទូលំទូលាយនៅក្នុងមូលដ្ឋានទិន្នន័យដូចជា PostGIS និងម៉ូឌុល R*Tree របស់ SQLite រៀបចំទិន្នន័យទៅជាចតុកោណកែងអប្បបរមា និងដោះស្រាយសំណួរជួរ និងការស្វែងរកអ្នកជិតខាងយ៉ាងមានប្រសិទ្ធភាព។ ជាទូទៅពួកវាដំណើរការជាង quadtrees សម្រាប់ការផ្ទុកនៅលើថាស ព្រោះវាកាត់បន្ថយប្រតិបត្តិការ I/O អប្បបរមា ដែលជាមូលហេតុដែលមូលដ្ឋានទិន្នន័យ spatial ភាគច្រើនប្រើវ៉ារ្យ៉ង់ R-tree ខាងក្នុងជាជាង quadtrees។

K-d tree ចន្លោះ​ភាគ​ដោយ​ប្រើ​ការ​បំបែក​តម្រឹម​អ័ក្ស​ឆ្លាស់​គ្នា (ដំបូង​ដោយ x, បន្ទាប់​មក​ដោយ y, បន្ទាប់​មក x ម្ដង​ទៀត) និង​ល្អ​បំផុត​សម្រាប់​ការ​ស្វែងរក​ជិត​បំផុត​ក្នុង​ទំហំ​មធ្យម។ ពួកវាមានទំនោរនឹងដំណើរការជាង quadtrees នៅពេលដែលវិមាត្រមានកម្រិតទាប ហើយសំណុំទិន្នន័យមានលក្ខណៈឋិតិវន្ត ប៉ុន្តែពួកវាពិបាកធ្វើបច្ចុប្បន្នភាពថាមវន្តជាង។ Geohashes ប្រើវិធីសាស្រ្តផ្សេងគ្នាទាំងស្រុង ដោយបំប្លែងរយៈទទឹង និងរយៈបណ្តោយទៅជាខ្សែអក្សរតែមួយ ដែលបុព្វបទដែលបានចែករំលែកបង្ហាញពីភាពជិតគ្នានៃលំហ - ធ្វើឱ្យពួកវាល្អសម្រាប់ការបង្កើតលិបិក្រមមូលដ្ឋានទិន្នន័យ និងឃ្លាំងសម្ងាត់ ប៉ុន្តែមានភាពបត់បែនតិចសម្រាប់សំណួរជួរតាមអំពើចិត្ត។

Quadtrees កាន់កាប់របស់ពួកគេផ្ទាល់នៅក្នុងសេណារីយ៉ូដែលលេងនឹងភាពខ្លាំងរបស់ពួកគេ៖ ការធ្វើលិបិក្រមទំហំនៅក្នុងអង្គចងចាំ សំណុំទិន្នន័យថាមវន្តជាមួយនឹងការបញ្ចូល និងការលុបញឹកញាប់ កម្មវិធីមើលឃើញដែលរចនាសម្ព័ន្ធក្រឡាចត្រង្គឋានានុក្រមធ្វើផែនទីតាមធម្មជាតិដើម្បីពង្រីកកម្រិត និងស្ថានភាពដែលភាពសាមញ្ញនៃការអនុវត្តមានបញ្ហា។ សម្រាប់កម្មវិធីផ្នែកខាងមុខដែលបង្ហាញចំណុចទិន្នន័យ 10,000 នៅលើផ្ទាំងក្រណាត់ជាមួយការពង្រីក និងពង្រីក quadtree ដែលបានអនុវត្តក្នុង 100 បន្ទាត់នៃ JavaScript នឹងដំណើរការលើសពីដំណោះស្រាយដែលគាំទ្រដោយមូលដ្ឋានទិន្នន័យដោយគ្រាន់តែលុបបំបាត់ភាពយឺតនៃបណ្តាញ។

ការចាប់ផ្តើម៖ ជំហានបន្ទាប់ជាក់ស្តែង

ប្រសិនបើអ្នកចង់ធ្វើឱ្យការយល់ដឹងរបស់អ្នកកាន់តែស៊ីជម្រៅអំពី quadtrees លើសពីការអានអំពីពួកវា វិធីសាស្រ្តដ៏មានប្រសិទ្ធភាពបំផុតគឺការកសាងមួយដោយមើលឃើញ។ បង្កើតកម្មវិធីផ្ទាំងក្រណាត់សាមញ្ញមួយ ដែលការចុចបន្ថែមចំណុច និងមើលផ្នែករងនៃមែកធាងក្នុងពេលជាក់ស្តែង។ បន្ថែម​ចតុកោណ​សំណួរ​ជួរ​ដែល​អ្នក​អាច​អូស​ជុំវិញ និង​រំលេច​ចំណុច​ដែល​វា​រក​ឃើញ។ អន្តរកម្មលើដៃនេះបង្កើតវិចារណញាណដែលមិនមានចំនួននៃការអានអាចផ្គូផ្គងបាន — អ្នកនឹងឃើញភ្លាមៗថាហេតុអ្វីបានជាទិន្នន័យចង្កោមបង្កើតដើមឈើកាន់តែស៊ីជម្រៅ និងរបៀបដែលឥរិយាបថកាត់ចេញអំឡុងពេលសំណួរលុបបំបាត់ទំហំធំ។

សម្រាប់កម្មវិធីផលិតកម្ម សូមពិចារណាគោលការណ៍ណែនាំទាំងនេះ៖ ប្រសិនបើទិន្នន័យរបស់អ្នករស់នៅក្នុងមូលដ្ឋានទិន្នន័យ ប្រើការធ្វើលិបិក្រម spatial មូលដ្ឋានទិន្នន័យរបស់អ្នកផ្តល់ (PostGIS, MySQL Spatial, MongoDB 2dsphere indexes) ជាជាងការអនុវត្ត quadtrees នៅក្នុងកូដកម្មវិធី។ ប្រសិនបើអ្នកកំពុងធ្វើការមើលឃើញផ្នែកខាងម៉ាស៊ីនភ្ញៀវ ឬដំណើរការក្នុងអង្គចងចាំ បណ្ណាល័យដូចជា d3-quadtree សម្រាប់ JavaScript ឬ pyquadtree សម្រាប់ Python ផ្តល់ឱ្យអ្នកនូវការអនុវត្តសាកល្បង។ ហើយប្រសិនបើអ្នកកំពុងបង្កើតវេទិកាដែលគ្រប់គ្រងទិន្នន័យទីតាំងប្រភេទណាមួយ — ពីអាសយដ្ឋានរបស់អតិថិជនរហូតដល់ការបញ្ជូនទៅកាន់ការគ្រប់គ្រងទឹកដី — វិនិយោគពេលវេលាដើម្បីយល់ពីការបង្កើតលិបិក្រមលំហ ព្រោះវានឹងកំណត់ជាមូលដ្ឋាននូវអ្វីដែលកម្មវិធីរបស់អ្នកអាចធ្វើបានក្នុងទំហំ។

Quadtrees តំណាងឱ្យគោលការណ៍ទូលំទូលាយនៅក្នុងវិទ្យាសាស្ត្រកុំព្យូទ័រ៖ រចនាសម្ព័ន្ធដែលអ្នកជ្រើសរើសសម្រាប់ទិន្នន័យរបស់អ្នកកំណត់សំណួរដែលអ្នកអាចឆ្លើយប្រកបដោយប្រសិទ្ធភាព។ បញ្ជីសំប៉ែតនៃកូអរដោនេអាចឆ្លើយថា "ផ្តល់ឱ្យខ្ញុំនូវពិន្ទុទាំងអស់" ប៉ុន្តែ quadtree អាចឆ្លើយថា "ផ្តល់ឱ្យខ្ញុំនូវចំណុចទាំងអស់នៅជិតទីនេះ" — ហើយវាអាចធ្វើវាបានលឿនល្មមដើម្បីមានអារម្មណ៍ភ្លាមៗ។ នៅក្នុងពិភពលោកដែល 73% នៃទិន្នន័យអាជីវកម្មមានធាតុផ្សំជាលំហ យោងទៅតាមការប៉ាន់ស្មានរបស់ឧស្សាហកម្ម សមត្ថភាពនោះមិនគ្រាន់តែជាការសិក្សាប៉ុណ្ណោះទេ។ វាជាគុណសម្បត្តិប្រកួតប្រជែង។

សំណួរដែលគេសួរញឹកញាប់

អ្វី​ទៅ​ជា quadtree ហើយ​តើ​វា​ដំណើរការ​ដោយ​របៀប​ណា?

quadtree គឺជារចនាសម្ព័ន្ធទិន្នន័យផ្អែកលើមែកធាង ដែលបែងចែកចន្លោះពីរវិមាត្រឡើងវិញទៅជាបួនជ្រុងស្មើគ្នា។ ថ្នាំងនីមួយៗអាចផ្ទុកនូវចំនួនកំណត់នៃចំណុចទិន្នន័យ មុនពេលបំបែកទៅជាថ្នាំងកូនបួន។ ការបែងចែកតាមឋានានុក្រមនេះធ្វើឱ្យសំណួរតាមលំហ — ដូចជាការស្វែងរកចំណុចទាំងអស់នៅក្នុងតំបន់ដែលបានផ្តល់ឱ្យ — លឿនខ្លាំងណាស់ ដោយកាត់បន្ថយពេលវេលាស្វែងរកពីលីនេអ៊ែរទៅលោការីតនៅក្នុងសេណារីយ៉ូជាក់ស្តែងភាគច្រើន។

តើ quadtrees ប្រើជាទូទៅនៅឯណាក្នុងកម្មវិធីពិភពពិត?

Quadtrees ផ្តល់ថាមពលដល់ប្រព័ន្ធជាច្រើន រួមទាំងផែនទីឌីជីថលដែលមានមុខងារ pinch-to-zoom ផ្ទាំងគ្រប់គ្រងកងនាវាតាមពេលវេលាជាក់ស្តែង ម៉ាស៊ីនស្វែងរកការប៉ះទង្គិចគ្នានៃហ្គេមវីដេអូ និងប្រព័ន្ធព័ត៌មានភូមិសាស្រ្តដែលដំណើរការសំណួរទំហំរាប់លានក្នុងមួយវិនាទី។ កម្មវិធីណាមួយដែលត្រូវការស្វែងរក បញ្ចូល ឬគ្រប់គ្រងវត្ថុដែលចែកចាយពាសពេញលំហពីរវិមាត្រប្រកបដោយប្រសិទ្ធភាពអាចទទួលបានអត្ថប្រយោជន៍ពីការធ្វើលិបិក្រម quadtree ។

តើ quadtrees ប្រៀបធៀបទៅនឹងរចនាសម្ព័ន្ធទិន្នន័យលំហផ្សេងទៀតដោយរបៀបណា?

មិនដូចក្រឡាចត្រង្គសំប៉ែតទេ ដើមឈើ quadtrees សម្របខ្លួនទៅនឹងដង់ស៊ីតេទិន្នន័យ — តំបន់តូចៗនៅមានសភាពទ្រុឌទ្រោម ខណៈដែលតំបន់ដែលមានមនុស្សច្រើនបែងចែកបន្ថែមទៀត។ បើប្រៀបធៀបទៅនឹងដើមឈើ k-d, quadtrees គឺសាមញ្ញជាងក្នុងការអនុវត្ត និងសមស្របជាងសម្រាប់ទិន្នន័យ 2D ដែលចែកចាយស្មើៗគ្នា។ R-trees គ្រប់គ្រងតំបន់ត្រួតស៊ីគ្នាបានយ៉ាងប្រណិត ប៉ុន្តែ quadtrees ឈ្នះលើល្បឿនបញ្ចូល និងងាយស្រួលជាងក្នុងការស្របគ្នាសម្រាប់បន្ទុកការងារក្នុងពេលជាក់ស្តែង។

តើ quadtrees អាចជួយបង្កើនប្រសិទ្ធភាពប្រតិបត្តិការនៅក្នុងកម្មវិធីអាជីវកម្មបានទេ?

ពិតប្រាកដ។ ឧបករណ៍អាជីវកម្មណាមួយដែលគ្រប់គ្រងទិន្នន័យទីតាំង ការវិភាគលំហ ឬផ្ទាំងគ្រប់គ្រងអន្តរកម្មទទួលបានអត្ថប្រយោជន៍ពីការបង្កើនប្រសិទ្ធភាព quadtree ។ វេទិកាដូចជា Mewayz ដែលជាប្រព័ន្ធដំណើរការអាជីវកម្ម 207-module OS ចាប់ផ្តើមពី $19/mo ប្រើប្រាស់រចនាសម្ព័ន្ធទិន្នន័យប្រកបដោយប្រសិទ្ធភាពនៅពីក្រោយឆាក ដើម្បីផ្តល់នូវបទពិសោធន៍ឆ្លើយតបរហ័ស និងរហ័ស — ពីផែនទីទីតាំងហាង រហូតដល់ការវិភាគតាមពេលវេលាជាក់ស្តែងលើចំណុចទិន្នន័យរាប់ពាន់។