Pytania otagowane jako computational-geometry

Pytania o algorytmiczne rozwiązywanie problemów geometrycznych lub inne algorytmy wykorzystujące geometrię.

6
Generowanie kombinacji z zestawu par bez powtarzania elementów
Mam zestaw par. Każda para ma taką postać (x, y), że x, y należą do liczb całkowitych z zakresu [0,n). Jeśli więc n wynosi 4, to mam następujące pary: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Mam już pary. Teraz muszę zbudować kombinację za pomocą n/2par, tak aby żadna liczba całkowita …
1
Jak spakować wielokąty wewnątrz innego wielokąta?
Zamówiłem kilka skórzanych prześcieradeł, z których chciałbym budować kuglarskie piłki, łącząc ze sobą krawędzie. Używam brył platońskich do kształtowania kulek. Mogę zeskanować skórzane prześcieradła i wygenerować wielokąt zbliżony do kształtu skórzanego prześcieradła (jak wiecie, jest to skóra zwierzęca i nie ma prostokątów). Chciałbym teraz zmaksymalizować rozmiar mojej żonglującej piłki. W …
2
Jak opracować algorytm do rozmieszczania (skalowalnych) okien na ekranie tak, aby zajmował jak najwięcej miejsca?
Chciałbym napisać prosty program, który akceptuje zestaw okien (szerokość + wysokość) oraz rozdzielczość ekranu i wyświetla układ tych okien na ekranie, aby okna zajmowały najwięcej miejsca. Dlatego można zmienić rozmiar okna, zachowując output size >= initial sizei proporcje. Tak więc dla okna chciałbym, aby algorytm zwrócił krotkę .( x , …
1
Czy istnieje algorytm O (n log n) dla uproszczenia linii 4D?
Algorytm Ramer Douglasa-Peucker dla linii Uproszczenie najgorszy czasem przebiegu. W przypadku odpowiednio rozmieszczonych losowych danych wejściowych oczekiwał złożoności środowiska wykonawczego O ( n log n ) . W 2D istnieją inne algorytmy o najgorszym przypadku złożoności środowiska wykonawczego O ( n log n ) , które obliczają dokładnie taki sam …
3
Linia oddziela dwa zestawy punktów
Czy istnieje sposób na stwierdzenie, czy dwa zestawy punktów można oddzielić linią? Mamy dwa zestawy punktów i jeśli istnieje linia, która oddziela i tak że wszystkie punkty i tylko po jednej stronie linii oraz wszystkie punkty i tylko po drugiej stronie.B A B A A B BAAABBBAAABBBAAAAAABBBBBB Najbardziej naiwnym algorytmem, …
3
Maksymalny krąg zamykający danego promienia
Próbuję znaleźć podejście do następującego problemu: Biorąc pod uwagę zestaw punktu i promień , znajdź punkt środkowy okręgu, tak aby okrąg zawierał maksymalną liczbę punktów ze zbioru. Czas działania powinien wynosić .SSSrrrO(n2)O(n2)O(n^2) Na początku wydawało się, że jest to coś podobnego do najmniejszego otaczającego problemu, które można łatwo rozwiązać w …
2
Wydajne algorytmy dla problemu widoczności pionowej
Myśląc o jednym problemie, zdałem sobie sprawę, że muszę stworzyć wydajny algorytm rozwiązujący następujące zadanie: Problem: otrzymujemy dwuwymiarowe kwadratowe pudełko o boku nnn którego boki są równoległe do osi. Możemy spojrzeć na to z góry. Istnieją jednak również mmm segmenty poziome. Każdy segment ma całkowitą współrzędną yyy ( 0≤y≤n0≤y≤n0 \le …
1
cięcia gilotynowe a cięcia ogólne
Problemy z cięciem to problemy, w których pewien duży obiekt powinien zostać pocięty na kilka małych obiektów. Na przykład, wyobraź sobie, że masz fabrykę, która współpracuje z dużymi arkuszami surowego szkła, o szerokości i długość L . Istnieje kilku nabywców, z których każdy chce nieograniczoną liczbę małych tafli szkła. Kupujący …
1
Brutalna siła złożoności algorytmu triangulacji Delaunaya
W książce „Geometria obliczeniowa: algorytmy i zastosowania” autorstwa Mark de Berg i wsp. Istnieje bardzo prosty algorytm brutalnej siły do ​​obliczania triangulacji Delaunaya. Algorytm wykorzystuje pojęcie niedozwolonych krawędzi - krawędzi, które mogą nie pojawić się w prawidłowej triangulacji Delaunaya i muszą zostać zastąpione innymi krawędziami. Na każdym kroku algorytm po …
2
Środowisko uruchomieniowe optymalnego algorytmu chciwości
|P|=n|P|=n|P| = nkkkkkknnnC={c1,c2,…,ck}C={c1,c2,…,ck}C = \{ c_1,c_2,\ldots,c_k\}kkkDcost(C)=maximinjD(pi,cj)cost(C)=maximinjD(pi,cj)\text{cost}(C) = \max_i \min_j D(p_i, c_j)DDDoznacza odległość euklidesową między punktem wejściowym a punktem środkowym . Każdy punkt przypisuje się do najbliższego centrum gromady grupującego wierzchołki w różnych skupisk.c j kpipip_icjcjc_jkkk Problem znany jest jako (dyskretny) problem klastrowania i jest to -hard. Można to pokazać z …
2
Czym jest ta struktura / koncepcja danych, w której wykres punktów definiuje podział na przestrzeń
Zetknąłem się z algorytmem rozwiązywania rzeczywistego problemu i pamiętam klasę, w której wziąłem udział, gdzie zrobiłem coś bardzo podobnego dla niektórych na zadanie domowe. Zasadniczo jest to wykres punktów, a linie są rysowane tak, aby były w równej odległości między dwoma punktami. Tworzy idealną przegrodę, w której linie wokół punktu …
1
Testowanie, czy czworościan leży w wielościanie
Mam czworościanu oraz graniastosłupa . jest tak ograniczony, że zawsze dzieli wszystkie swoje wierzchołki z . Chcę ustalić, czy leży wewnątrz .ttt t p tppptttpppttt ppp Chciałbym dodać jeden szczegół do problemu, w przypadku gdy może on przyczynić się do rozwiązania: jest czworościanem Delaunaya, a ściany są trójkątne i silnie …
2
Przecięcie okręgu z algorytmem linii przeciągnięcia
Niestety nadal nie jestem tak silny w zrozumieniu algorytmu linii przeciągania . Wszystkie artykuły i podręczniki na ten temat są już przeczytane, jednak ich zrozumienie jest wciąż bardzo odległe. Aby to wyjaśnić, próbuję rozwiązać jak najwięcej ćwiczeń. Ale naprawdę interesujące i ważne zadania wciąż stanowią dla mnie wyzwanie. Poniższe ćwiczenie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.