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

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

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)]


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

如何在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

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.

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

发表评论

匿名网友

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

确定