Computational Geometry

Mark de Berg

Mentioned 6

This introduction to computational geometry focuses on algorithms. Motivation is provided from the application areas as all techniques are related to particular applications in robotics, graphics, CAD/CAM, and geographic information systems. Modern insights in computational geometry are used to provide solutions that are both efficient and easy to understand and implement.

More on Amazon.com

Mentioned in questions and answers.

What are the easy algorithms to implement Voronoi diagram?

I couldn't find any algorithm specially in pseudo form. Please share some links of Voronoi diagram algorithm, tutorial etc.

An easy algorithm to compute the Delaunay triangulation of a point set is flipping edges. Since a Delaunay triangulation is the dual graph of a Voronoi diagram, you can construct the diagram from the triangulation in linear time.

Unfortunately, the worst case running time of the flipping approach is O(n^2). Better algorithms such as Fortune's line sweep exist, which take O(n log n) time. This is somewhat tricky to implement though. If you're lazy (as I am), I would suggest looking for an existing implementation of a Delaunay triangulation, use it, and then compute the dual graph.

In general, a good book on the topic is Computational Geometry by de Berg et al.

I want to solve geometry problems in online programming contests. But whenever I read them, I just find too difficult. Please suggest some books and resources which I can study computational geometry.

And of course there's Computational Geometry - An Introduction, by Preparata and Shamos. I own it, and recommend it for an introduction to the principles. Not really a dictionary of code, though.

I recommend two books (among others):

Is there a trivial, or at least moderately straight-forward way to generate territory maps (e.g. Risk)?

I have looked in the past and the best I could find were vague references to Voronoi diagrams. An example of a Voronoi diagram is this:

here.

These hold promise, but I guess i haven't seen any straight-forward ways of rendering these, let alone holding them in some form of data structure to treat each territory as an object.

Another approach that holds promise is flood fill, but again I'm unsure on the best way to start with this approach.

Any advice would be much appreciated.

The best reference I've seen on them is Computational Geometry: Algorithms and Applications, which covers Voronoi diagrams, Delaunay triangulations (similar to Voronoi diagrams and each can be converted into the other), and other similar data structures.

They talk about all the data structures you need but they don't give you the code necessary to implement it (which may be a good exercise). In terms of code, an Amazon search shows the book Computational Geometry in C, which presumably comes with the code (although since you're stuck in C, you'd mind as well get the other one and implement it in whatever language you want). I also don't have any experience with this book, only the first.

Sorry to have only books to recommend! The only decent online resource I've seen on them are the two Wikipedia articles, which doesn't really tell you implementation details. This link may be helpful though.

We have a list of x,y pairs. Every pair represents a point on a 2D space. I want to find the closest point from this list, to a specific point xq,yq. What is the best performance-critical algorithm for this problem? Lisp of points is not going to change; which means I do not need to perform insertion and deletion. I want just to find the nearest neighbor of a target xq,yq point in this set.

Edit 1: Thanks to all! As Stephan202 has guessed correctly, I want to do this repeatedly; like a function. An the list is not necessarily sorted (In fact I do not understand how can it be sorted? Like a table with a primary key of 2 columns a and y? If that helps then I will sort it).

I will construct the data structure based on the list one time, and then I will use this generated data structure in the function (if this process itself is relevant).

Thank you Jacob; It seems that KD-Tree data structure is a good candidate for being the answer (And I feel it is. I will update when I get some relevant results).

Edit 2: I have found that, this problem is named "nearest neighbor"!

Edit 3: First title was "In Search of an Algorithm (for Spatial-Querying and Spatial-Indexing) (Nearest Neighbor)"; I have chose a new title: "Best Performance-Critical Algorithm for Solving Nearest Neighbor". Since I do not want to perform insertion and deletion operation on my initial data and I want just the nearest one from them to a new point (which is not going to be inserted), I chose to (currently) working on KD-Trees. Thanks to all!

If the query point (xq, yq) varies and the list doesn't, you need to calculate the Voronoi diagram of the list of points. This will give you a set of polygons or "cells" (some of which are infinite); each polygon corresponds to a point from the original list, called the "site" of that cell. Any point which lies entirely inside of one polygon is closer to the site of that polygon than it is to the other sites on the original list. Any point on a boundary between two polygons lies equally distant from each site.

Once you've gotten that far, you need an easy way to figure out which polygon you're in. This is known as the point location problem.

A really, really good book for this kind of thing is Computational Geometry: Algorithms and Applications. They discuss both the Voronoi diagram calculation and the trapezoidal slab method of point location in detail.

If you don't want to do the code yourself, and you shouldn't, then try to get a library like CGAL that will do most of the work for you. This probably applies to the KD-tree answer as well, but I don't specifically know.

One of the more interesting things I've run into lately is the art and science of laying out chip floorplan and determining packaging for the silicon. I would like to read some materials on the subject for the "Interested Software Guy".

Does anyone have any recommendations (Website or book, so long as it is a good quality)?

This is a result of my search on the subject as I was curious about your question and this is where I would start myself. Sorry I am not a specialist on the subject but hope it can kick-start you!

Seems floorplan optimization is a matter of combinatorial optimization.

As a developer, you'll want to tackle the theory behind it and most likely some proven algorithms. You might then be interested by books such as:

It's a bit more difficult to get links on this subject, but if you're a member of IEEE Xplore, you might want to look at this paper and other similar ones.

Finally, on the floorplan wikipedia entry, you'll notice this on sliceable floorplans that might give you your best starting point:

Sliceable floorplans have been used in a number of early EDA tools for a number of reasons. Sliceable floorplans may be conveniently represented by binary trees which correspond to the order of slicing. What is more important, a number of NP-hard problems with floorplans have polynomial time algorithms when restricted to sliceable floorplans

Good luck!

I have thousand of objects in my app. I wanna make objects visible only at the scene that I see, and make objects invisible out of scene. I wrote a code but it's working laggy. Here is my code :

for(var i:int = 0; i<container.numChildren; i++){
    var obj:MovieClip = container.getChildAt(i) as MovieClip;
    rectScene.x = -container.x + 25; // position things...
    rectScene.y = -container.y + 25;
    if(rectScene.intersects(new Rectangle(obj.x-40,obj.y-43,obj.width,obj.height))){
        obj.visible = true;
    }else{
        obj.visible = false;
    }
}

Example Image : http://i.stack.imgur.com/GjUG8.png

It's laggy to check all of thousands objects everytime I drag the scene. How can I solve this ?

Thanks a lot !

I would create a Sprite per Scene and add the belonging Object to them. So the display list could look like this:

+root
+-+scene1
  +obj1
  +obj2
    .
    .
  +objN
+-+scene2

and so on. This way you just need to toggle the current scenes' visibility. But as I see, you are sorting the objects based on intersection with a »scene rect« and that is costly process if you have that many Objects to check. If you cannot add a data structure to associate Objects to Scenes, than you can try to cache the result and run the search only if something changes…

Last but not least you could implement an improved searching algorithm based on space partition, so that you decrease the number of intersection test as much as possible. But that depends on strongly on your application, if everything is moving a lot and you need to update the partition tree very often, that might not be an improvement.

EDIT

One possible algorithm for an efficient lookup of the objects in an area could be orthogonal range searching. An explanation would go too far here and is not the subject of the question.

A book including a nice description is this and a result of a quick and dirty googling is here.

The algorithm is based in a binary tree which contains the coordinates of the objects. If the objects do not move that is perfect for your application, because then the tree just needs to be initialized once and following range queries are quite fast. To be exact, their speed depends on the size of the area to query. So the improvement will be bigger, the smaller the size of the queried area is compared to the size of the overall world.

Good luck!

EDIT #2

I once had a similar thing to handle, that was one dimensional (x-axis only), but as far as I know, it should not be too complicated to make this work in two dimensions (Got that from the book, linked above). You can have a look at the question here.