Tag: algorithms

Entries for tag "algorithms", ordered from most recent. Entry count: 68.

Pages: 1 ... 7 8 9

# Poisson Disc Generator

Mon
23
Apr 2007

Poisson Disc is one of the best methods for determining places from which to sample some data, next to Grid, Random or Jittered methods. It prevents aliasing thanks to random distribution while preserving minimum distance between sample positions not to focus too many samples in a particular region. Unfortunately, an algorithm for generating such samples is slow and we don't know how many points we will manage to generate with specified minimum distance.

That's why I thought it would be useful to have an array of many numbers, each defining new Poisson Disc sample in the way that the more first samples you take, you still have a correct Poisson Disc samples but with more points and smaller minimum distance. I've coded a small console application for generating such arrays of 1D, 2D or 3D points in 0..1 range. I've also generated ready 1000-element arrays. Here you can find the details: PoissonDiscGenerator.

I've called it "Progressive Poisson Disc", described it in my master thesis [PDF, pl], used in my The Final Quest engine [pl] and also integrated into Math module of my CommonLib library.

Update 2023-11: As my colleague pointed out, taking only a small number of first samples (e.g. 16) from the array I generated doesn't make a good uniform distribution across the surface, so for that, I recommend to use some other method (e.g. samples from a grid + random jitter) or make your own implementation of this idea of "progressive Poisson Disc".

Comments | #productions #math #algorithms Share

# Szybkie, heurystyczne przeszukiwanie dysku

Thu
01
Mar 2007

Na stronie portalu CodeGuru.pl poświęconemu programowaniu w technologii .NET ukazał się mój nowy, drobny artykuł zatytułowany Szybkie, heurystyczne przeszukiwanie dysku. Opisałem w nim algorytm, który przeszukując katalogi dysku twardego użytkownika pozwala odnaleźć potrzebny plik w czasie wielokrotnie krótszym, niż podczas tradycyjnego, rekurencyjnego przeszukiwania dysków dzięki zastosowaniu prostej heurystyki i wiedzy o konkretnym problemie.

Comments | #productions #teaching #.net #algorithms Share

# XDS - eXtensible Data Stream

Mon
05
Feb 2007

Nie tylko ja podejmuję próby zastąpienia języka XML czymś lepszym, pozbawionym choć części z jego licznych wad. W moim XNL2 zrezygnowałem ze znaczników i związanego z nimi samoopisu na rzecz prostoty i zwięzłości. XNL2 w moich własnych zastosowaniach sprawdza się doskonale, ale po latach jego używania dochodzę do wniosku, że jeszcze lepiej zastąpiłby go zwykły tokenizer C/C++, być może razem z preprocesorem. Kiedyś sobie taki napiszę.

Podobnego zadania, ale od trochę innej strony, podjął się niejaki Mark T. Price. Zaprojektował on format XDS - eXtensible Data Stream, który jest binarny (tym samym szybki i zwięzły), a zarazem elastyczny. Czy użyteczny? - to zależy od zastosowania, ale warto chyba przejrzeć jego specyfikację.

Comments | #algorithms Share

# Kademlia

Sun
19
Nov 2006

Myślę, że nie tylko pasjonatów algorytmiki czy programowania równoległego i rozproszonego, ale i zwykłych użytkowników może zainteresować - jako ciekawostka - czym jest Kademlia. Ten sprytny wynalazek to rozproszona tablica haszująca, która wykorzystywana jest m.in. w sieciach P2P do całkowicie zdecentralizowanego wyszukiwania źródeł i można ją spotkać pod postacią sieci Kad w eMule czy mechanizmu DHT w klientach BitTorrenta.

Comments | #algorithms Share

Pages: 1 ... 7 8 9