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?

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

1 Answer 1

Reset to default
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:

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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