如何在Python中将多边形分割为n个相等面积的部分，我需要子多边形的坐标。

huangapple
go评论109阅读模式
英文:

how to divide polygon into n equal area parts in python i need sub polygons coordinates

问题

  1. 这是一幅画有外多边形的图片，现在我想在Python中将其分割成多个具有相等面积的部分。
  3. 请给出建议和示例代码。

坐标为 = [(17.436838, 78.466061), (17.433808, 78.488205), (17.415792, 78.486832), (17.412598, 78.464001)]

  2. 我需要子多边形的坐标。
英文:

如何在Python中将多边形分割为n个相等面积的部分，我需要子多边形的坐标。

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

  1. 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.

  1. import matplotlib.pyplot as plt
  2. import math
  4. my_polygon = [(3,1),(9,1),(12,3),(14,5),(10,6),(5,7),(2,5),(0,2)]
  5. your_polygon = [(17.436838, 78.466061), (17.433808, 78.488205), (17.415792, 78.486832), (17.412598, 78.464001)]
  6. my_rect = [(0,0),(0,8),(2,8),(2,0)]
  7. my_triangle = [(0,0),(0,1),(1,1)]
  8. #my_polygon = [(x/15, y/10) for (x, y) in polygon]
  10. (xm, ym, r, circle_points) = (6, 6, 5, 40)
  11. 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)]
  13. def calc_area(polygon):
  14.     """
  15.     calculates the area of a polygon
  17.     https://en.wikipedia.org/wiki/Polygon#Simple_polygons
  19.     parameters
  20.         polygon - list of 2-dimensional points
  22.     returns
  23.         area
  24.     """
  25.     result = 0
  26.     for i in range(len(polygon)):
  27.         p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
  28.         result += p0[0]*p1[1]-p1[0]*p0[1]
  29.     return result / 2
  31. def calc_centroid(polygon):
  32.     """
  33.     calculates the centroid of a polygon
  34.     #https://en.wikipedia.org/wiki/Centroid#Of_a_polygon
  36.     parameters
  37.         polygon - list of 2-dimensional points
  39.     returns
  40.         area
  42.     """
  43.     xs, ys, a = 0, 0, calc_area(polygon)
  44.     for i in range(len(polygon)):
  45.         p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
  46.         xs += (p0[0]+p1[0])*(p0[0]*p1[1]-p1[0]*p0[1])
  47.         ys += (p0[1]+p1[1])*(p0[0]*p1[1]-p1[0]*p0[1])
  48.     return (xs/(6*a), ys/(6*a))
  50. def split_triangles(polygon):
  51.     """
  52.     splits the polygon into triangles between centroid and and a vertex
  53.     it only works for convex polygons
  55.     parameters
  56.         polygon - list of 2-dimensional points
  58.     returns
  59.         list of polygons (triangles)
  61.     """
  62.     result = []
  63.     xs, ys = calc_centroid(polygon)
  64.     for i in range(len(polygon)):
  65.         p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
  66.         result.append((p0, p1, (xs,ys)))
  67.     return result
  69. def split_ortho(polygon):
  70.     """
  71.     splits the polygon orthogonal concerning centroid into two parts
  72.     if x- extension bigger than y- extension, then vertical split, otherwise horicontal
  74.     it only works for convex polygons
  76.     parameters
  77.         polygon - list of 2-dimensional points
  79.     returns
  80.         list of polygons
  82.     """
  83.     ps = calc_centroid(polygon)
  84.     x = 
     for p in polygon]
  85.     y = 
     for p in polygon]
  86.     parts = [[]]
  88.     split_index = 0 if (max(x)-min(x)) > (max(y)-min(y)) else 1
  90.     for i in range(len(polygon)):
  91.         p0, p1 = polygon[i], polygon[(i+1) % len(polygon)]
  92.         parts[len(parts)-1].append(p0)
  93.         if (p0[split_index] < ps[split_index] and ps[split_index] < p1[split_index]) or\
  94.             (p0[split_index] > ps[split_index] and ps[split_index] > p1[split_index]):
  95.             #Nenner kann bei konkaven Polygonen nicht 0 werden, denn dann müsste diese Kante senkrecht zum Schwerpunkt verlaufen
  96.             #if p0[split_index] < p1[split_index]:
  97.             if True:
  98.                 BA, BX, BE = p0[split_index], ps[split_index], p1[split_index]
  99.                 HA, HE = p0[(split_index+1) % 2], p1[(split_index+1) % 2]
  100.                 HX = HA+(BX-BA)*(HE-HA)/(BE-BA)
  102.             psplit = [0,0]
  103.             psplit[split_index] = ps[split_index]
  104.             psplit[(split_index + 1) % 2] = HX
  105.             parts[len(parts)-1].append(tuple(psplit))
  106.             parts.append([tuple(psplit)])
  107.     return (parts[1], parts[2]+parts[0])
  109. functions = {0:(split_triangles, 3), 1:(split_ortho, 5)}
  110. areas = {0:my_polygon, 1:your_polygon, 2:my_circle, 3:my_triangle}
  111. fig, ax = plt.subplots(nrows = 4, ncols = 4)
  113. for key_area in areas:
  114.     polygon = areas[key_area]
  116.     for key_function in functions:
  117.         func, stepcount = functions[key_function]
  119.         parts = [polygon]
  120.         for i in range(stepcount):
  121.             new_parts = []
  122.             for j, p in enumerate(parts):
  123.                 new_parts.extend(func(p))
  124.             parts = new_parts
  126.             if i==0:
  127.                 for p in parts:
  128.                     ax[key_function*2][key_area].add_patch(plt.Polygon(p, ec = "k"))
  129.                     ax[key_function*2][key_area].autoscale()
  131.         for p in parts:
  132.             ax[key_function*2+1][key_area].add_patch(plt.Polygon(p, ec = "k"))
  133.             ax[key_function*2+1][key_area].autoscale()
  135. plt.tight_layout()
  136. 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.

huangapple
  • 本文由 发表于 2023年7月12日 22:40:23
  • 转载请务必保留本文链接：https://go.coder-hub.com/76671771.html
  • dictionary
  • gis
  • python
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定