# Center point approximation of a polygon

I would like to get a center point approximation of a set of polygons so I can do a NN lookup to use for assignment instead of a point in polygon query.

Lets say I have this set of polygons: I would like to calculate a set of centerpoints that approximates the polygon when used in a NN lookup: Does anybody have a clue to achieve this (Python/postgis preferred)? And does anybody have a pointer to any algorithms that can achieve this?

• Why do some polygons have more than one "center point" and what are your criteria for deciding which should get more than one point (otherwise just use ogr's geometry.centroid() function)? Jul 25, 2013 at 14:40
• They can have multiple centers because these are not voronoi polygons but can have complex shapes. That is why the centroid is to much of an approximation. Jul 25, 2013 at 14:43
• Edited image to make this more clear. Blue poly on top can not be represented as a voronoi. Jul 25, 2013 at 14:48
• You want to approximate a point-in-polygon operation by a nearest point operation, by creating a number of points per polygon? I don't see how convex polygons in particular allows one point only for a certain level of accuracy (because you must accept some errors). It must also be related to the size of all polygons, how much space there is between them (if any) etc. Jul 25, 2013 at 15:08
• Could you explain or link to what you mean by an "NN lookup"? Jul 25, 2013 at 21:10 