Pytania oznaczone «computational-geometry»

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 nie była...

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...

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...

W związku z nadchodzącym okresem świątecznym postanowiłem zrobić gwiazdy cynamonu . To było zabawne (a wynik smaczny), ale mój wewnętrzny kujon skurczył się, gdy włożyłem pierwszą tacę gwiazd do pudełka i nie zmieściłyby się w jednej warstwie: Prawie! Czy istnieje sposób, w jaki mogliby pasować?...

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

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...

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...

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...

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ą...

|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...

Definicja : Wielokąt w płaszczyźnie jest nazywany monotonicznym w stosunku do linii prostej , jeśli każda linia prostopadła do przecina najwyżej dwa razy.L L PP.P.PL.L.LL.L.LP.P.P Biorąc pod uwagę wielokąt , czy można ustalić, czy istnieje jakaś linia tak że wielokąt jest monotoniczny względem...

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...

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...

Podczas umieszczania obiektów geometrycznych w kwadracie (lub oktawie) możesz umieszczać obiekty większe niż pojedynczy węzeł na kilka sposobów: Umieszczenie odniesienia do obiektu w każdym liściu, dla którego jest zawarty Umieszczenie odniesienia do obiektu w najgłębszym węźle, dla którego jest...

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,...

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...

Próbuję rozwiązać następujący problem z zasięgiem. Istnieje nadajników o zasięgu 1 km i odbiorników. Zdecyduj w że wszystkie odbiorniki są objęte dowolnym nadajnikiem. Wszystkie reveivers TRANSMITER i jest reprezentowany przez oraz współrzędnych.nnnnnnO(nlogn)O(nlog⁡n)O(n\log...

Załóżmy, że otrzymaliśmy dwie liczby i i że chcemy znaleźć dla l \ le i, \, j \ le r .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Naiwny algorytm sprawdza po prostu wszystkie możliwe pary; na przykład w rubinie mielibyśmy: def max_xor(l, r) max = 0 (l..r).each do |i|...

Istnieje popularny problem [1] [2] w informatyce, który polega na znalezieniu minimalnej liczby linii prostych pokrywających dany zestaw punktów w 2D. Mimo że zeskanowałem wiele artykułów, żaden z nich nie ma wyraźnej motywacji do rozwiązania problemu. Jaki jest pożytek z rozwiązania tego...

Biorąc pod uwagę ortogonalny wielokąt (wielokąt, którego boki są równoległe do osi), chcę znaleźć najmniejszy zestaw kwadratów wewnętrznie rozłącznych, których zjednoczenie jest równe wielobokowi. Znalazłem kilka odniesień do nieco innych problemów, takich jak: Pokrycie prostopadłego wielokąta...