Just as another regular work day, I memo down some new things along the task I am facing. Recently I have been crazy about the Voronoi diagram. Although as bad as I wanted to implement the sweepline algorithm, I found the best practice might be patient and learn thing little by little. Also, I am kinds into “Study with me” series on youtube. I feel clam with someone’s company alongside.
var ghobjs = new List(); var selectedLayer = RhinoDoc.ActiveDoc.Layers.FindName(layerName); var layers = new List(){selectedLayer}; if(subLayer) { foreach(var layer in RhinoDoc.ActiveDoc.Layers) if(layer.IsChildOf(selectedLayer)) layers.Add(layer); } B = layers; foreach(var layer in layers) { var rhobjs = doc.Objects.FindByLayer(layer); foreach (var rhObj in rhobjs) ghobjs.Add(rhObj.Geometry); } A = ghobjs;
add a site event in the event queue for each site while the event queue is not empty pop the top event if the event is a site event insert a new arc in the beachline check for new circle events else create a vertex in the diagram remove the shrunk arc from the beachline delete invalidated events check for new circle events
An edge in a Voronoi diagram is shared by two adjacent cells. In the DCEL data structure, we splite these edfes in two half-edges, one for each cell, and they are linked by the twin pointer.
Moreover, a hald-edge has an origin vertex and a desrination vertex. The incidenetFace field points to the face to which the half-edge belongs to.
Finally, in DCEL, cells are implemented as a circular doubly linked list of half-edges where adjacent half-edges are linked together. Thus the prev and next fields points to the previous and next half-edges in the cell.
Finally, the Face class represents a cell and it just contains a pointer to its site and another to one of its half-edges. It does not matter which half-edge it is because a cell is a closed polygon. Thus we can access to all of its hald-edges by traversing the circular linked list.
The standard way to implement the event queue is to use a priority queue.
During the processing of site and circle events we may need to remove circle events from the queue because they are not valid anymore.
But most of the standard implementations of priority queues do not allow to remove an element which is not the top one. In particular that is the case for std::priority_queue.
There are two ways to tackle this problem.
The first and simplest one is to add a valid flag to true initially. Then instead of removing the circle event from the queue, we just set its flag to false. Finially, when we process the events in the main loop, if the valid flag of an event equals to false, we simply discard it and process the next one.
The second method which I adopted is not to use std::priority_queue. Instead, I implemented my own priority queue which supports removal of any element it contains. The implementation of such a queue is pretty straightforward. I choose this method because I find it makes the code for the algorithm clearer.
Beachline
If not implemented correctly there is no guarantee that the algorithm will run in O(log(n)). The key to reach this time complecity is to use a self-balancing tree.
In my implementation the beachline is still a tree, but all nodes represent an arc.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
structArc{ enum classColor{RED, BLACK};
// Hierarchy Arc* parent; Arc* left; Arc* right;
// Diagram VoronoiDiagram::Site* site; VoronoiDiagram::HalfEdge* leftHalfEdge; VoronoiDiagram::HalfEdge* rightHalfEdge; Event* event; // Optimizations Arc* prev; Arc* next; // Only for balancing Color color; };
In Fortune’s algorithm we have no key, we only know that we want to insert an arc before or after another in the beachline. To do that, I create methods insertBefore and insertAfter:
A priority queue is an Abstract Data Type(ADT) that operates similar to a normal queue excpet that each element has a certain priority. The priority of the elements in priority queue determin the order in which elements are removed from the PQ.
NOTE: Priority queues only supports comparable data.
What is a Heap?
A heap is a tree based DS that satifies the heap invariant(also called heap property): If A is a parent node of B then A is ordered with repect to B for all nodes A, B in the heap.
Max Heap
Min Heap
Heaps must be trees.
When and where is a PQ used?
Used in certain implementaitons of Dijkstra’s shortest Path algorithm.
Anytime you need the dynamically fetch the next best or next worst element
Used in Huffman coding (which is often used for lossless data compression).
Best First Search(BFS) algorithms such as A* use PQs to continuously grab the next most promising node
Fill the event queue with site events for each input site. While the event queue still has items in it: If the next event on the queue is a site event: Add the new site to the beachline Otherwise it must be an edge-intersection event: Remove the squeezed cell from the beachline Cleanup any remaining intermediate state
Voronoi Diagram - Computataional Geometry
Fortune’s Sweep
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
VoronoiDiagram(P are in R2) Q : new PriorityQueue(P) // site events sortes by y-coord. T : new BalancedBinarySearchTree() // sweep status(B) D : new DCEL() // to-be Vor(P)
while not Q.empty() do p <- Q.ExtractMax() if p site event then HandleSiteEvent(p) else a <- arc on B that will disappear HandleCircleEvent(a)
treat remaining int. nodes of T(unbnd. edges of Vor(P)) return D
Handling Events
HandleSiteEvent(point p)
Search in T for the arc a vertically above p. If a has pointer to circle event in Q, delete this event.
Split a into a0 and a2. Let a1 be the new arc of p
Add Vor-edges <q, p> and <p, q> to DECL
Check <., a0, a1> and <a1, a2, .> for circle events.
Hey, it’s been a while since the last time I updated my blog. I spent some time learnig html, css and javascript. Though I am still in a very beginner state, I feel like I would like to learn some interesting code I randomly found. Try to breakdown to see what I can learn from them.
The article is about implementing Voronoi-Diagram in Javascript. The resource can be found here.
I found this recently hosted AEC hackathon video. To be honest, this will be the first hackathon I knew in AEC industy was held.Just want to memo down some interesting ideas from each project. Oh also, I heard the Glodfinger was the big winner of this event. I would like to dive deep into there source code in near future, and I might write some other posts for that topic.
Sunday Programme
Pollution Solution
People from A to B, might consider not only the distance, but also the air quality as well.
Find alternative routes where pollution levels are significantly lower
Algorithm taking the Google pollution data into account.
Recently, I found myself tend to absorb some general knowledge in tech-field at late night. I got company with Lofi music from Spotify. This post tend to note down some benefits for programmer switch to Linux instead of other OS, for say Windows or MacOS.
I’ve had this rough ideas about those great programmers tend to work in pure text, command line enviroment a lot, not saying they don’t want to use GUI, it’s just faster if both hands can stick on their keyboard and get everything done.
LinuxOS is open source, meaning anyone who want to can look at the source code. Although this might mean anyone who want to attack the other’s machine can find the system flaw easily, it turns out become harder to hack in. Because Linux is a famous OS, thousands of other programmers run the code on their local machine,and they don’t want someone can get a way hack in, they patched the flaws once found it.
Improve programming workflow
For example, if you want to install something:
The scenario in a linux machine will be
1
sudo apt-get install whatever-you-want-to
However, if you are in a MacOS or Windows.
you might need a package manager
Or find the correct link on the correct webpage
click several button while installing
might need to restart your machine
As a developer, we constantly install things and linux make this procedure less pain.
No rebooting
Linux can update the entire whole Operating System without any reboot. This is neither possible on MacOS nor Windows. This no-rebooting thing is one of the reason why linux is choosed for running most of the servers.
Many Linux servers on the Internet have been running for years without failure or even being restarted.
Powerful Programming Tools pre-installed
GREP
wget
_corn
Task automation
Linux lend itself very well for automation. one-liner means short little scripts that you write to automate a task.
Performace
Linux is not neccessary faster than other OS, but it is very lightweight for an OS.
I went a long long walk today, approximately 21km and took me 6.7 hours. The weather today was just so great. Recently, I noticed that if the article I posted only has the techicial contents, that might be a bit boring. The whole keep posting thing is for me to be motivated, so I decided that I need to write down some thoughts ahead or behind the article, to make it more human.
What’s my thoughts about YAML before learning it.
I have had much knowledge about yaml before I tried to post on github Page. I am currently using the hexo framework, organizing my blogs, and inside the folder, there’s one .yaml file owns a lot of settings we can play around.
I could put whatever font I want. It might work on my machine, but I have no guarantees that same font will exist or be installed on your machine or the average person’s machine.
One option that we have is to actually include a font. As part of our document, we can include a font file so you can buy a font, you can download them.
