Python: find a method to calculate the "inner centroid" (X,Y) of a polygon

Question

I have a polygon (converted in a Shapely object). My goal is calculate the "inner centroid" (also known as "point on surface")(return x,y values) and the "centroid" (return x,y values) following the figure example: ``` from shapely.geometry import Polygon ref_polygon = Polygon(points) # get the x and y coordinate of the centroid ref_polygon.centroid.wkt 'POINT (558768.9293489187300000 6361851.0362532493000000)' ``` my question is some programmer has already developed a function in Python to calculate the inner centroid or know some module to do this. Thanks in advance the points (vertex of the polygon) used are: ``` points = [(560036.4495758876, 6362071.890493258), (560036.4495758876, 6362070.890493258), (560036.9495758876, 6362070.890493258), (560036.9495758876, 6362070.390493258), (560037.4495758876, 6362070.390493258), (560037.4495758876, 6362064.890493258), (560036.4495758876, 6362064.890493258), (560036.4495758876, 6362063.390493258), (560035.4495758876, 6362063.390493258), (5600…

Accepted Answer

The term "inner centroid" isn't a well-defined term in computational geometry, but it seems clear from your post that you want to compute a point that is well inside the polygon (with some margin between it and nearby edges), and which is reasonably near to the true centroid.

Here are a couple of ideas you might try:

Algorithm A

Generate all the internal diagonals of the polygon.

For each internal diagonal, consider the midpoint, and give it a score based on how far it is from the nearest edge and how close it is to the centroid.

Choose the midpoint with the highest score.

An internal diagonal of a polygon is a line joining two non-adjacent vertices that lies entirely with the polygon. The set of m internal diagonals of a polygon with n verticies can be generated in O(m + n log log n) using a rather complex algorithm due to Hershberger, or in O(n2) using more straightforward algorithms.

Algorithm B

Triangulate the polygon.

For each triangle in the triangulation, consider the centroid (or maybe the incenter?) of the triangle, and give it a score based on how far it is from the nearest edge and how close it is to the centroid of the polygon.

Choose the triangle center with the highest score.

A simple polygon with n vertices can be triangulated in O(n) using an algorithm based on decomposition into monotone polygons due to Chazelle, or in O(n2) using simpler approaches like "ear clipping".

Python: find a method to calculate the "inner centroid" (X,Y) of a polygon

Solution

Problem