2

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:

Original polygon set

I would like to calculate a set of centerpoints that approximates the polygon when used in a NN lookup: Polygon set with center point approximations

Does anybody have a clue to achieve this (Python/postgis preferred)? And does anybody have a pointer to any algorithms that can achieve this?

  • 2
    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)? – MappaGnosis Jul 25 '13 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. – RickyA Jul 25 '13 at 14:43
  • Edited image to make this more clear. Blue poly on top can not be represented as a voronoi. – RickyA Jul 25 '13 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. – Uffe Kousgaard Jul 25 '13 at 15:08
  • Could you explain or link to what you mean by an "NN lookup"? – blah238 Jul 25 '13 at 21:10
2

I'm not sure of what problem you are trying to solve and the criteria defining these "center points", but one possible approach might be to compute the Straight skeleton of the polygon and then use the interior vertices of the skeleton as your "center points".

Straight skeleton

One such algorithm for simple polygons is described in:

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.