Voronoi Tessellation in Python

python algorithm computational-geometry voronoi operations-research
user1071530 picture user1071530 · Nov 29, 2011 · Viewed 10.4k times · Source

Node Assignment Problem

enter image description here

The problem I want to solve is to tessellate the map given with the Blue Nodes(Source Nodes) as given input points, Once I am able to do this I would like to see how many Black Nodes(Demand Nodes) fall within each cell and assign it to the Blue Node associated with that cell.

I would like to know if there is a easier way of doing this without using Fortune's Algorithm.I came across this function under Mahotas called Mahotas.segmentation.gvoronoi(image)source. But I am not sure if this will solve my problem.

Also please suggest me if there is a better way of doing this segmentation(other than Voronoi tessellation). I am not sure if clustering algorithms would be a good choice. I am a programming newbie.

Answer

wye.bee picture wye.bee · Nov 29, 2011

Here is an alternative approach to using Voronoi tessellation:

Build a k-d tree over the source nodes. Then for every demand node, use the k-d tree to find the nearest source node and increment a counter associated with that nearby source node.

The implementation of a k-d tree found at http://code.google.com/p/python-kdtree/ should be useful.

Related questions

Efficient way to find overlapping of N rectangles

I am trying to find an efficient solution for finding overlapping of n rectangles where rectangles are stored in two separate lists. We are looking for all rectangles in listA that overlap with rectangles in listB (and vice versa). Comparing …

Read More
Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More
How to generate all permutations of a list?

How do you generate all the permutations of a list in Python, independently of the type of elements in that list? For example: permutations([]) [] permutations([1]) [1] permutations([1, 2]) [1, 2] [2, 1] permutations([1, 2, 3]) [1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]

Read More