英文:
how to divide polygon into n equal area parts in python i need sub polygons coordinates
问题
这是一幅画有外多边形的图片,现在我想在Python中将其分割成多个具有相等面积的部分。
请给出建议和示例代码。
坐标为 = [(17.436838, 78.466061), (17.433808, 78.488205), (17.415792, 78.486832), (17.412598, 78.464001)]
我需要子多边形的坐标。
英文:
This is image which is draw outer polygon now I want to divide into multiple parts with equal area in python
please give suggestion and code sample
coordinate are = \[(17.436838, 78.466061), (17.433808, 78.488205), (17.415792, 78.486832), (17.412598, 78.464001)\]
I need sub polygon coordinates.
答案1
得分: 1
这是代码部分,我将不会翻译它。如果您有其他文本需要翻译,请提供并我将尽力帮助您。
英文:
Not the right forum, but interesting question for me.
Idea: Look for the centroid. It's place marks, where to you can cut in any direction and both parts have equal area sizes.
There are 2 interesting options: you can split it in triangles between the vertexes end the centroid. The other idea is to split it horicontally or vertically depending on expansion.
The following code shows both ideas with an your data and another example- polygons.
import matplotlib.pyplot as plt
import math
my_polygon = [(3,1),(9,1),(12,3),(14,5),(10,6),(5,7),(2,5),(0,2)]
your_polygon = [(17.436838, 78.466061), (17.433808, 78.488205), (17.415792, 78.486832), (17.412598, 78.464001)]
my_rect = [(0,0),(0,8),(2,8),(2,0)]
my_triangle = [(0,0),(0,1),(1,1)]
#my_polygon = [(x/15, y/10) for (x, y) in polygon]
(xm, ym, r, circle_points) = (6, 6, 5, 40)
my_circle = [(xm + math.sin(2*alpha*math.pi/circle_points)*r, ym + math.cos(2*alpha*math.pi/circle_points)*r) for alpha in range(circle_points)]
def calc_area(polygon):
"""
calculates the area of a polygon
https://en.wikipedia.org/wiki/Polygon#Simple_polygons
parameters
polygon - list of 2-dimensional points
returns
area
"""
result = 0
for i in range(len(polygon)):
p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
result += p0[0]*p1[1]-p1[0]*p0[1]
return result / 2
def calc_centroid(polygon):
"""
calculates the centroid of a polygon
#https://en.wikipedia.org/wiki/Centroid#Of_a_polygon
parameters
polygon - list of 2-dimensional points
returns
area
"""
xs, ys, a = 0, 0, calc_area(polygon)
for i in range(len(polygon)):
p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
xs += (p0[0]+p1[0])*(p0[0]*p1[1]-p1[0]*p0[1])
ys += (p0[1]+p1[1])*(p0[0]*p1[1]-p1[0]*p0[1])
return (xs/(6*a), ys/(6*a))
def split_triangles(polygon):
"""
splits the polygon into triangles between centroid and and a vertex
it only works for convex polygons
parameters
polygon - list of 2-dimensional points
returns
list of polygons (triangles)
"""
result = []
xs, ys = calc_centroid(polygon)
for i in range(len(polygon)):
p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
result.append((p0, p1, (xs,ys)))
return result
def split_ortho(polygon):
"""
splits the polygon orthogonal concerning centroid into two parts
if x- extension bigger than y- extension, then vertical split, otherwise horicontal
it only works for convex polygons
parameters
polygon - list of 2-dimensional points
returns
list of polygons
"""
ps = calc_centroid(polygon)
x = for p in polygon]
y =
for p in polygon]
parts = [[]]
split_index = 0 if (max(x)-min(x)) > (max(y)-min(y)) else 1
for i in range(len(polygon)):
p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
parts[len(parts)-1].append(p0)
if (p0[split_index] < ps[split_index] and ps[split_index] < p1[split_index]) or\
(p0[split_index] > ps[split_index] and ps[split_index] > p1[split_index]):
#Nenner kann bei konkaven Polygonen nicht 0 werden, denn dann müsste diese Kante senkrecht zum Schwerpunkt verlaufen
#if p0[split_index] < p1[split_index]:
if True:
BA, BX, BE = p0[split_index], ps[split_index], p1[split_index]
HA, HE = p0[(split_index+1) % 2], p1[(split_index+1) % 2]
HX = HA+(BX-BA)*(HE-HA)/(BE-BA)
psplit = [0,0]
psplit[split_index] = ps[split_index]
psplit[(split_index + 1) % 2] = HX
parts[len(parts)-1].append(tuple(psplit))
parts.append([tuple(psplit)])
return (parts[1], parts[2]+parts[0])
functions = {0:(split_triangles, 3), 1:(split_ortho, 5)}
areas = {0:my_polygon, 1:your_polygon, 2:my_circle, 3:my_triangle}
fig, ax = plt.subplots(nrows = 4, ncols = 4)
for key_area in areas:
polygon = areas[key_area]
for key_function in functions:
func, stepcount = functions[key_function]
parts = [polygon]
for i in range(stepcount):
new_parts = []
for j, p in enumerate(parts):
new_parts.extend(func(p))
parts = new_parts
if i==0:
for p in parts:
ax[key_function*2][key_area].add_patch(plt.Polygon(p, ec = "k"))
ax[key_function*2][key_area].autoscale()
for p in parts:
ax[key_function*2+1][key_area].add_patch(plt.Polygon(p, ec = "k"))
ax[key_function*2+1][key_area].autoscale()
plt.tight_layout()
plt.show()
To answer your last question: Of course you can easy adapt this code for a given number of "n". A simple way - so simple, that I don't like to do it - is to split the polygon (should be convex) beginning from one edge into polygons / triangles of the given size. The way: You calculate the area of the first three points. If this is smaller than total area divided by "n", you calculate the next triangle, until the sum is greater or equal than your wish. If it is greater, you can easy devide the opposite side that way. The first part is the end of your last polygon, the other is the beginning of the new one.
But there are many variations of this, you could start in one edge or in the center, in any other given point inside your shape - as you like.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论