Генериране на минимален набор от върхове от сплайн/крива

В моя проект представям геометрия с помощта на сплайни. За физика и изобразяване обработвам предварително сплайновете и ги конвертирам в линии, а по-късно и в полигони, като вземам проби от сплайновете на редовен интервал. Искам обаче да намаля броя на върховете/линиите, като игнорирам проби, които вече са достатъчно добре представени от линия.

Излизайки кратък при търсене, се чудех дали има някакви традиционни техники за преобразуване на крива в набор от върхове, като същевременно се намалява произтичащата грешка.

РЕДАКТИРАНЕ: За да поясня, резултатът, който искам да получа, е брой върхове/линейни сегменти, които най-добре представят сплайна с най-малкото количество върхове/линейни сегменти. Не съм сигурен как да дефинирам какво наистина означава „най-добро представяне на сплайна“, но целта е да направим възможно най-трудно разграничаването на разликата между сплайн и приближението.


algorithm computational-geometry spline polygon
person Jens Andersson    schedule 23.04.2014    source източник
comment
Традиционната техника, която познавах, беше за извършване на оптимизация, минимизираща максималното разстояние.   -  person Denys Séguret    schedule 23.04.2014
comment
Има ли някакви ограничения или допълнителни полезни свойства, които биха могли да бъдат от помощ? Например: ако точките могат да бъдат определени от някои функции x(t) и y(t), където t е индексът на върховете (така че първият връх ще бъде (x(0), y(0))), това ще ни даде още малко за работа.   -  person Conduit    schedule 23.04.2014
comment
@Nate, смущаващо ниските ми математически умения ме карат да избягвам да се опитвам да обясня проблема с тези термини, тъй като очаквам да обърка повече, отколкото да помогне. Въпреки това, ако сплайнът е s(0 -› 1) и вземам проби s(0.01), s(0.02), s(0.03), ..., s(1), за да получа xy[0], xy[1] , xy[2], ..., xy[100]. (В този случай xy е 2d връх, но не очаквам проблемът да е различен в 3d). След това искам да намеря набор от s(t0), s(t1), s(t2), ..., s(tn), откъдето линейна интерполация ще съответства на s(0 -› 1) до определена сума на грешка.   -  person Jens Andersson    schedule 23.04.2014

Отговори (2)


arrow_upward
4
arrow_downward

Може да се направи чрез рекурсивно прецизиране на част, която не е близо до сегмента между краищата на частта.

Ако имаме крива (сплайн) C:[0,1]->R^n. След това първото приближение е сегмент S между крайните точки на кривата [C(0), C(1)]. Вземете точка C(0.5) и проверете колко далеч е от сегмент S. Ако е далеч, трябва да го вземем в дискретизация, ако не, тогава S е добро приближение. Ако C(0.5) е далече, следващото приближение е полилиния [C(0), C(0.5), C(1)] и правим същата процедура с части [C(0), C(0.5)] и [C(0.5), C(1)].

Ако използвате полиномиален сплайн от порядък >= 3 (напр. кубичен сплайн), той може да има инфлексна точка(и). В този случай е възможно точката на кривата на половината да "падне" точно върху сегмента, но кривата наоколо да бъде далеч от сегмента. В такъв случай е добре да проверите още едно ниво на подчастите.

person Ante    schedule 23.04.2014
comment
Хм, това е наистина умно. Това е особено хубаво, тъй като не изисква от мен да взема проби от тон точки от кривата, които така или иначе биха били изхвърлени. - person Jens Andersson; 24.04.2014
comment
Това е просто и хубаво. Алгоритъмът е стандартен, но не можах да намеря описание. Знам, че съм чел за това в Уикипедия. - person Ante; 24.04.2014
comment
Ако можете да представите своя сплайн с помощта на криви на Безие (това е възможно от кубичен сплайн), тогава свойството на корпуса ви позволява да използвате подхода на рекурсивно подразделяне с абсолютна гаранция за приближението, дори при наличие на точки на инфлексия. - person Yves Daoust; 25.04.2014

arrow_upward
0
arrow_downward

Това се основава изцяло на собствената ми интуиция, така че не съм сигурен дали ИЗОБЩО съвпада с най-добрите практики. Имам диплома по математика, така че се надявам, че не е твърде далеч. Искам да отбележите, че включеното изчисление може да изпревари печалбите в производителността, предоставени от неизползването на толкова много върхове, ако сплайнът трябва да се преизчислява често.

Да кажем, че върховете са в масив като [v(0), v(1), v(2),..., v(n)], където всеки v(i) е нещо като (x, y). Чрез итерация по върховете, започващи от v(1) и завършващи при v(n-1), можем да сравним точка с нейните съседи, за да кажем дали да я отхвърлим или не. Обърнете внимание, че игнорираме v(0) и v(n) по две причини: (предполагам), че не искаме да премахнем нашите крайни точки, а също така v(0) и v(n) липсва съсед, от който бихме се нуждаели за да настроим нашето изчисление. Мога да се сетя за няколко възможности тук, които може да изискват изследване, но една по-специално изглежда (в главата ми) е най-добрият отговор...

Да разгледаме случая, в който решаваме дали да премахнем или не v(i) от масива на върховете. Можем да изследваме декартовото разстояние между v(i) и неговите съседи и да премахнем точката, ако и двете са под някаква прагова стойност T. Например, ако v(i-1) = (x1, y1) и v(i) = ( x2, y2) и v(i+1) = (x3, y3), тогава оценяваме sqrt((x2-x1)^2 + (y2-y1)^2))<T && sqrt((x3-x2)^2 + (y3-y2)^2))<T, като премахваме v(i), ако оценката върне true.

В 3+ измерения това ще стане по-сложно - изчислението ще бъде подобно, но ще ви е необходим метод за определяне на съседите на точка, тъй като те може да не лежат директно до изследваната точка в масива от върхове.

person Conduit    schedule 23.04.2014
comment
Благодаря за отговора Нейт. Въпреки че това би намалило броя на върховете, няма да успее да го направи по-често, когато кривата е добре представена от линейните сегменти - няма да запази върховете по време на по-кривите части на сплайна, за да запази визуалната прецизност там. - person Jens Andersson; 24.04.2014