Pitteway триангуляциясы - Pitteway triangulation - Wikipedia

Сол жақта: Питтвей триангуляциясы. Кез-келген ішкі Delaunay жиегі (қара) сәйкес екі Вороной шетінен өтеді (сызылған көк), бірақ дөңес корпустың шеттері олардың қосарларын кесіп өтпейді. Оң жақта: Питтвей триангуляциясы болып табылмайтын Delaunay триангуляциясы; қызыл ішкі интерьер Делунай жиегі сәйкес келетін қызыл түсті Вороной шетінен өтпейді, ал жоғарғы үшбұрыштың кейбір нүктелері төменгі шыңға жақын көршісі ретінде ие.

Жылы есептеу геометриясы, а Pitteway триангуляциясы Бұл нүктелік триангуляция онда жақын көрші кез келген нүкте б үшбұрыш ішінде үшбұрыштың төбелерінің бірі бар б.Әрине, бұл а Delaunay триангуляциясы онда әр ішкі шеті өзінің қиылысқан жерінен өтеді қосарланған Вороной диаграммасы шеті. Питтвей триангуляциялары 1973 жылы оларды зерттеген Майкл Питтвюйдің есімімен аталады. Питтвей триангуляциясын барлық нүктелер қолдай бермейді. Мұндай триангуляция болған кезде бұл ерекше жағдай Delaunay триангуляциясы, және бірігуінен тұрады Габриэль графигі және дөңес корпус.

Тарих

Питтвей триангуляциясы ұғымы енгізілген Pitteway (1973). Сондай-ақ қараңыз МакЛейн (1976), кім жазады «Оңтайлы бөлім, онда кез-келген үшбұрыштың кез-келген нүктесі үшін, ол нүкте, кем дегенде, кез-келген басқа деректер нүктесіне қарағанда осы үшбұрыштың төбелерінің біріне жақын орналасады». «Питтвей триангуляциясы» атауын берген Окабе және т.б. (2000).

Қарсы мысалдар

Алтын (1978) барлық нүктелер Питтювэй триангуляциясын қолдай бермейтіндігін көрсетеді. Мысалы, а-ның кез-келген триангуляциясы тұрақты бесбұрыш орталықтан тұрады тең бүйірлі үшбұрыш мұндай нүкте б үшбұрыштың бірінің ортаңғы нүктесінің жанында үшбұрыштың сыртында жақын көршісі болады.

Басқа геометриялық графиктермен байланыс

Pitteway триангуляциясы болған кезде, триангуляцияға дейінгі әр шеткі интерьердің ортаңғы нүктесінде ең жақын көршілер ретінде екі шеткі шеткі нүктелер болуы керек, өйткені кез-келген басқа көрші екі үшбұрыштың біріндегі жақын нүктелер үшін Pitteway қасиетін бұзуы мүмкін. Осылайша, диаметрі бойынша осындай шеңберге ие шеңбер төбелерден бос болуы керек, сондықтан Питтвей триангуляциясы Габриэль графигі бірге дөңес корпус нүкте жиынтығы. Керісінше, Габриэль графигі мен дөңес корпусы бірге триангуляция құрғанда, бұл Питтвей триангуляциясы.

Барлық Габриэль графигі және дөңес корпустың шеттері Delaunay триангуляциясы, болған кезде Питтвей триангуляциясы нүктелер үшін ерекше болып табылады жалпы позиция және Delaunay триангуляциясымен сәйкес келеді. Алайда, Питтвей триангуляциясы жоқ нүктелер жиынтығында Делоней триангуляциясы болады.

Питтвей триангуляциясында әр шеті pq немесе дөңес корпусқа жатады немесе шетін кесіп өтеді Вороной диаграммасы құрамына кіретін жасушаларды бөледі б және q. Кейбір сілтемелерде бұл қасиет Питтювей триангуляциясын анықтау үшін қолданылады, бұл Delaunay триангуляциясы, мұнда барлық ішкі Delaunay шеттері өздерінің қос Вороной шеттерін қиып өтеді. Алайда, Питтювей триангуляциясы қосарланған жерінен өтпейтін дөңес корпустың шеттерін қамтуы мүмкін.[1]

Ескертулер

  1. ^ Окабе және т.б. (2000); Добрин (2005).

Әдебиеттер тізімі

  • Добрин, Адам (2005), Вороной диаграммаларының қасиеттері мен вариацияларына шолу (PDF), Уитмен колледжі
  • Алтын, C. M. (1978), «Географиялық үшбұрышты элементтер құрылымын практикалық құру және қолдану» (PDF), Даттонда, Г. (ред.), Геоақпараттық жүйелерге арналған топологиялық мәліметтер құрылымы бойынша бірінші халықаралық ғылыми-зерттеу симпозиумы. Геоақпараттық жүйелер туралы Гарвард құжаттары, т. 5 - мәліметтер құрылымы: беттік және көп өлшемді., Бостон: компьютерлік графика және кеңістіктік талдау зертханасы, Гарвард университеті, 1–18 б..
  • McLain, D. H. (1976), «Кездейсоқ мәліметтерден екі өлшемді интерполяция.», Компьютерлік журнал, 19: 178–181, дои:10.1093 / comjnl / 19.2.178.
  • Окабе, Атсуюки; Етік, Барри Н .; Чиу, Сун Нок; Сугихара, Кокичи (2000), Кеңістіктегі тесселяциялар: Вороной диаграммаларының түсінігі мен қолданылуы, Вили.
  • Pitteway, M. L. V. (1973), «Академиялық ортадағы компьютерлік графиканы зерттеу», Datafair '73.