CODEWITHSUNDEEP
pythonalgorithmcomputational-geometryvoronoioperations-research
user1071530
user1071530

Reputation: 113

Voronoi Tessellation in Python

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.

Upvotes: 7

Views: 12236

Answers (6)

Karim Bahgat
Karim Bahgat

Reputation: 3041

You did not say why you wanted to avoid Fortune's algorithm. I assume you meant that you just didn't want to implement it yourself, but it has already been implemented in a script by Bill Simons and Carston Farmer so computing the voronoi diagram shouldn't be difficult.

Building on their script I made it even easier to use and uploaded it to PyPi under the name Pytess. So you could use the pytess.voronoi() function based on the blue points as input, returning the original points with their computed voronoi polygons. Then you would have to assign each black point through point-in-polygon testing, which you could base on http://geospatialpython.com/2011/08/point-in-polygon-2-on-line.html.

enter image description here

Upvotes: 0

Malcolm Murdoch
Malcolm Murdoch

Reputation: 1085

I've just been looking for the same thing and found this:

https://github.com/Softbass/py_geo_voronoi

Upvotes: 2

Tim Gee
Tim Gee

Reputation: 1062

I think the spatial index answer by https://stackoverflow.com/users/1062447/wye-bee (A kd-tree for example) is the easiest solution to your problem.

Additionally, you did also ask is there an easier alternative to Fortune's algorithm and for that particular question I refer you to: Easiest algorithm of Voronoi diagram to implement?

Upvotes: 1

Joseph O'Rourke
Joseph O'Rourke

Reputation: 4406

Run this code in Mathematica. It's spectacular! (Yes, I know it is not Python, but ...)

pts3 = RandomReal[1, {50, 3}];
ListDensityPlot[pts3, 
    InterpolationOrder -> 0, ColorFunction -> "SouthwestColors", Mesh -> All]

          Voronoi Diagram

Upvotes: -1

user97370
user97370

Reputation:

There's not many points in your diagram. That suggests you can, for each demand node, just iterate through all the source nodes and find the nearest one.

Perhaps this:

def distance(a, b):
    return sum((xa - xb) ** 2 for (xa, xb) in zip(a, b))

def clusters(sources, demands):
    result = dict((source, []) for source in sources)
    for demand in demands:
        nearest = min(sources, key=lambda s: distance(s, demand))
        result[nearest].append(demand)
    return result

This code will give you a dictionary, mapping source nodes to a list of all demand nodes which are closer to that source node than any other.

This isn't particularly efficient, but it's very simple!

Upvotes: 1

wye.bee
wye.bee

Reputation: 716

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.

Upvotes: 9

Related Questions