Cluster polygons into equal parts in QGIS

Question

I have a large area divided into three parts. Each of these parts is divided into smaller parts. Each part contains an amount of biomass that can be cut and sold. The total amount of biomass in the entire territory is about 1,170,000 m3. This quantity should be realized in 10 years. Approximately 117,000 m3 (+/-1000m3) should be cut every year, which would amount to 1,170,000m3 of biomass in 10 years. I tried to do it with the "Attribute based clustering" Plugin, but I couldn't get nearly equal parts.

**

I don't need a clusters like in this picture, which I did with the K-Means algorithm.

**

Is it possible to do something like this using QGIS?

Download data= https://www.mediafire.com/file/7nz4vdsau6uk4vj/Layer_Poly.rar/file

These three parts make up the total area. It is important that an equal amount of biomass is cut through all three parts.As you can see in the picture, every year it is cut on the total territory, but each of these three parts should also approximately deliver the biomass of the year. — Frodo, Jan 10 '23 at 18:44
See this great answer: https://gis.stackexchange.com/a/354691/88814 — Babel, Jan 10 '23 at 21:42
@Kasper, attribute field is PJ (01,02,03) and field StrOdl. It is enough to make nessesary geomertry if you like. — Frodo, Jan 11 '23 at 06:15
@Babel, I know about dividing polygon, but that is not solution. — Frodo, Jan 11 '23 at 06:16
If it's too complicated, let's try clustering without PJs, or treat each PJ separately as a separate entity. — Frodo, Jan 11 '23 at 06:24
What you need looks like a variant of the Knapsack problem, you might want to investigate the related algorithms — Kasper, Jan 11 '23 at 07:22
@nagib You need to write a script that solves the knapsack problem. In your situation, you have 10 knapsacks (years) for each polygon. This may be useful: https://www.askpython.com/python/examples/knapsack-problem-dynamic-programming — Comrade Che, Jan 17 '23 at 05:36
@Comrade Che, In this example, there are three input factors. What would the input data be in my case? The final result should be like in the picture 2, an evenly distributed annual amount that needs to be cut off. — Frodo, Jan 17 '23 at 08:19
Let me explain again: it is known how much biomass I need to cut annually (about 117,000m3). This value should be spread evenly over the entire territory. Each polygon has an amount of biomass that needs to be cut, and in each polygon this value is different. In 10 years, the total value should be around 1,170,000m3. — Frodo, Jan 17 '23 at 08:33
@nagib Here is an example of how your problem can be converted to a knapsack problem: https://i.stack.imgur.com/XPQh1.png An additional constraint is that the items in the knapsack must be unique. — Comrade Che, Jan 17 '23 at 09:56
@nagib In your situation it does not matter which polygon you will "cut" in this knapsack (year and zone), so the value of each polygon will be 1, the weight will be equal to the biomass value. The capacity of the knapsack will be 39,000 cubic meters. — Comrade Che, Jan 17 '23 at 10:06
The capacity of the knapsack should be 117.000 cubic meters/ year. In your image 39.000 is annual for 30 years. In this case, we can forget the zones because they complicate things. 10 years is limit for cutting whole area. — Frodo, Jan 17 '23 at 12:46
@nagib: if I understand correctly, the total biomass for the zone 1 is : 609891 m³, lets say 610000 m³. As each zone don't have the same amount of biomass, you want to cut around 61000 m³ in the zone 1 each year ? — J. Monticolo, Jan 19 '23 at 11:40
It is desirable to cut evenly in each zone. In the entire territory, about 1,170,000 m3 should be cut in 10 years. We can ignore the zones and look at the total area and quantity if that suits you — Frodo, Jan 19 '23 at 12:29

Comrade Che · Accepted Answer · 2023-01-17T17:34:42.883

Since there is no need to count `values' in this knapsack problem, the algorithm can be simplified.

I wrote a script that generates random data and groups objects until their value (biomass) exceeds the limit value.

You can try this python script to solve your problem.

As a result of running the script, the following information is printed (in fact, this is a group of objects representing trees to be cut down in one of the years):

total biomass of the group,
the number of zone where the object is located,
object's biomass value,
object number (fid).

Python script:

import random
from pprint import pprint
from operator import itemgetter
def obj(fid, biomass, zone):
    return {'fid': fid,
            'biomass': biomass,
            'zone': zone,
            }
def generate_random_data(number_of_objects, number_of_zones=3, max_biomass=10000):
    list_of_objects = []
    for fid in range(1, number_of_objects + 1):
        object = obj(fid,
                     biomass=random.randint(1, max_biomass),
                     zone=random.randint(1, number_of_zones)
                     )
        list_of_objects.append(object)
sorted_list = sort(list_of_objects, attribute_name='biomass', descending_order=True)
return sorted_list



def select_zone(list_of_objs, zone):
    selection = []
    for object in list_of_objs:
        if object['zone'] == zone:
            selection.append(object)
if selection is not []:
    selection = sort(selection, attribute_name='biomass', descending_order=True)
return selection



def sort(list_of_objs, attribute_name, descending_order=True):
    newlist = sorted(list_of_objs, key=itemgetter(attribute_name), reverse=descending_order)
    return newlist
def fit_value(objects, value_limit=99999, value_name=''):
    fit_list = []
    current_value_sum = 0
    all_values_exceed_the_limit_value = True
for object in objects:
    if current_value_sum + object[value_name] &gt;= value_limit:
        continue
    else:
        all_values_exceed_the_limit_value = False
        current_value_sum += object[value_name]
        fit_list.append(object)

if all_values_exceed_the_limit_value:
    raise ValueError(f'All values exceed the `limit_value` = {value_limit}')

print(f'current {value_name} = {current_value_sum}')
return fit_list



def delete_fitted_dicts(list_of_objects, list_to_delete, value_name=''):
    for obj_to_del in list_to_delete:
        fid_to_del = obj_to_del[value_name]
        list_of_objects[:] = [d for d in list_of_objects if d[value_name] != fid_to_del]
return list_of_objects



if name == 'main':
    # ==================RANDOM DATA GENERATION===================
    number_of_objects = 100
    number_of_zones = 3
    max_biomass = 10000
    objects = generate_random_data(number_of_objects, number_of_zones, max_biomass)
    # ==================RANDOM DATA GENERATION===================
# ==================CUSTOM DATA ===================
# this is how you could insert your data =&gt; obj(fid, biomass, zone)
# here is your actual data set:
# number_of_zones = 3
# objects = [obj(1, 4568.73, 2),
#            obj(2, 5959.85, 1),
#            obj(3, 6004.28, 2),
#            obj(4, 3887.06, 3),
#            obj(5, 7210.49, 3),
#            obj(6, 3178.99, 1),
#            obj(7, 5737.37, 2),
#            obj(8, 3251, 3),
#            obj(9, 3792.48, 1),
#            obj(10, 3128.32, 2),
#            obj(11, 2569.45, 3),
#            obj(12, 4818.57, 3),
#            obj(13, 4933.24, 3),
#            obj(14, 4377.89, 1),
#            obj(15, 3586.87, 3),
#            obj(16, 5272.58, 1),
#            obj(17, 3932.83, 3),
#            obj(18, 4816.8, 1),
#            obj(19, 2022.41, 1),
#            obj(20, 3491.4, 1),
#            obj(21, 6305.08, 1),
#            obj(22, 7221.38, 1),
#            obj(23, 2118.55, 2),
#            obj(24, 6500.35, 2),
#            obj(25, 5780.51, 1),
#            obj(26, 4579.31, 1),
#            obj(27, 5377.13, 2),
#            obj(28, 3495.67, 2),
#            obj(29, 3641.83, 1),
#            obj(30, 4405.74, 3),
#            obj(31, 1664.51, 1),
#            obj(32, 8170.73, 1),
#            obj(33, 2709.9, 3),
#            obj(34, 5734.8, 3),
#            obj(35, 4350.5, 1),
#            obj(36, 2712.28, 1),
#            obj(37, 5485.65, 3),
#            obj(38, 4487.09, 2),
#            obj(39, 5280.2, 3),
#            obj(40, 3352.39, 2),
#            obj(41, 4244.35, 1),
#            obj(42, 3137.46, 3),
#            obj(43, 4758.65, 1),
#            obj(44, 3503.11, 1),
#            obj(45, 3709.33, 2),
#            obj(46, 3889.17, 1),
#            obj(47, 7674.81, 1),
#            obj(48, 3042.86, 3),
#            obj(49, 6627.39, 1),
#            obj(50, 6616.91, 2),
#            obj(51, 3805.52, 2),
#            obj(52, 5545.11, 1),
#            obj(53, 7545.63, 3),
#            obj(54, 1442.76, 1),
#            obj(55, 4682.22, 2),
#            obj(56, 2235.11, 1),
#            obj(57, 2452.55, 3),
#            obj(58, 4089.24, 2),
#            obj(59, 2133.16, 2),
#            obj(60, 5230.2, 1),
#            obj(61, 3177.18, 3),
#            obj(62, 4569.62, 1),
#            obj(63, 5180.02, 1),
#            obj(64, 3629.4, 2),
#            obj(65, 4558.03, 3),
#            obj(66, 2476.36, 1),
#            obj(67, 3253.91, 2),
#            obj(68, 4572.78, 2),
#            obj(69, 3024.16, 1),
#            obj(70, 8337.28, 2),
#            obj(71, 5398.66, 1),
#            obj(72, 3391.52, 3),
#            obj(73, 4250.79, 2),
#            obj(74, 3207.57, 1),
#            obj(75, 951.22, 2),
#            obj(76, 2995.62, 1),
#            obj(77, 4789.16, 1),
#            obj(78, 4711.58, 1),
#            obj(79, 5913.65, 1),
#            obj(80, 3554.45, 2),
#            obj(81, 3663.21, 1),
#            obj(82, 3137.59, 2),
#            obj(83, 2900.61, 1),
#            obj(84, 2178.32, 1),
#            obj(85, 3938.92, 2),
#            obj(86, 6326.92, 1),
#            obj(87, 3118.89, 1),
#            obj(88, 3303.01, 2),
#            obj(89, 2122.17, 2),
#            obj(90, 2739.13, 2),
#            obj(91, 3882.01, 1),
#            obj(92, 5262.04, 1),
#            obj(93, 4355.35, 1),
#            obj(94, 4789.2, 1),
#            obj(95, 7417.33, 2),
#            obj(96, 1629.01, 2),
#            obj(97, 1457.74, 3),
#            obj(98, 4825.11, 2),
#            obj(99, 3882, 1),
#            obj(100, 2533.29, 1),
#            obj(101, 4019.24, 2),
#            obj(102, 3195.59, 1),
#            obj(103, 4521.99, 1),
#            obj(104, 5849.2, 3),
#            obj(105, 970.06, 2),
#            obj(106, 4353.85, 1),
#            obj(107, 3149.02, 1),
#            obj(108, 4038.43, 1),
#            obj(109, 3743.02, 2),
#            obj(110, 6019.4, 3),
#            obj(111, 3923.15, 1),
#            obj(112, 3502.44, 1),
#            obj(113, 4411.54, 2),
#            obj(114, 3942.86, 2),
#            obj(115, 4805.02, 3),
#            obj(116, 4935.38, 2),
#            obj(117, 1176.4, 2),
#            obj(118, 2271.21, 3),
#            obj(119, 4333.29, 2),
#            obj(120, 4563.09, 1),
#            obj(121, 6616.9, 3),
#            obj(122, 4049.14, 3),
#            obj(123, 5319.86, 3),
#            obj(124, 1952.42, 1),
#            obj(125, 4622, 1),
#            obj(126, 5135.52, 3),
#            obj(127, 5698.16, 1),
#            obj(128, 3975.76, 1),
#            obj(129, 2882.61, 3),
#            obj(130, 231.27, 2),
#            obj(131, 2914.41, 1),
#            obj(132, 5161.81, 2),
#            obj(133, 3388.21, 1),
#            obj(134, 5578.51, 3),
#            obj(135, 3058.48, 1),
#            obj(136, 3334.45, 2),
#            obj(137, 3781.53, 3),
#            obj(138, 3277.44, 2),
#            obj(139, 6249.16, 1),
#            obj(140, 3126.63, 3),
#            obj(141, 5065.3, 3),
#            obj(142, 4316.86, 1),
#            obj(143, 3213.01, 1),
#            obj(144, 2877.12, 2),
#            obj(145, 6936.29, 2),
#            obj(146, 5939.02, 1),
#            obj(147, 12464.46, 1),
#            obj(148, 3126.78, 2),
#            obj(149, 4819.39, 1),
#            obj(150, 3003.13, 1),
#            obj(151, 3701.09, 2),
#            obj(152, 2091.06, 2),
#            obj(153, 5084.89, 1),
#            obj(154, 3520.45, 3),
#            obj(155, 2456.66, 1),
#            obj(156, 4704.91, 1),
#            obj(157, 4649.93, 1),
#            obj(158, 4335.06, 1),
#            obj(159, 2609.36, 3),
#            obj(160, 5644.71, 1),
#            obj(161, 4186.34, 1),
#            obj(162, 2796.21, 3),
#            obj(163, 5773.64, 1),
#            obj(164, 6598.26, 1),
#            obj(165, 4639.03, 3),
#            obj(166, 4870.77, 1),
#            obj(167, 6188.74, 1),
#            obj(168, 2227.86, 2),
#            obj(169, 1129.13, 2),
#            obj(170, 4238.59, 1),
#            obj(171, 5151, 1),
#            obj(172, 4021.11, 2),
#            obj(173, 4823.75, 1),
#            obj(174, 2112.74, 2),
#            obj(175, 7953.17, 1),
#            obj(176, 4455.02, 1),
#            obj(177, 4221.16, 2),
#            obj(178, 4493.82, 2),
#            obj(179, 6456.96, 3),
#            obj(180, 5221.3, 1),
#            obj(181, 4836.87, 1),
#            obj(182, 2850.26, 1),
#            obj(183, 5697.8, 1),
#            obj(184, 8260.25, 1),
#            obj(185, 3709.72, 3),
#            obj(186, 3051.32, 1),
#            obj(187, 4730.61, 2),
#            obj(188, 4600.65, 2),
#            obj(189, 3954.06, 1),
#            obj(190, 3438.66, 3),
#            obj(191, 3223.06, 2),
#            obj(192, 3233.1, 1),
#            obj(193, 3764.94, 3),
#            obj(194, 1814.03, 1),
#            obj(195, 4988.45, 1),
#            obj(196, 1221.38, 2),
#            obj(197, 6912.86, 1),
#            obj(198, 3495.35, 1),
#            obj(199, 3674.16, 2),
#            obj(200, 3792.86, 2),
#            obj(201, 5078.56, 1),
#            obj(202, 2392.04, 2),
#            obj(203, 6840.5, 3),
#            obj(204, 3544.63, 3),
#            obj(205, 3153.85, 3),
#            obj(206, 2168.46, 2),
#            obj(207, 3106.63, 1),
#            obj(208, 1195.05, 1),
#            obj(209, 6028.44, 1),
#            obj(210, 5080.29, 1),
#            obj(211, 3637.39, 1),
#            obj(212, 4057.92, 3),
#            obj(213, 5684.45, 3),
#            obj(214, 5214.37, 1),
#            obj(215, 3785.49, 2),
#            obj(216, 3484.84, 2),
#            obj(217, 4605.07, 1),
#            obj(218, 5267.93, 1),
#            obj(219, 4572.31, 1),
#            obj(220, 2182.78, 2),
#            obj(221, 3301.24, 1),
#            obj(222, 3607, 1),
#            obj(223, 3106.08, 2),
#            obj(224, 6482.06, 1),
#            obj(225, 4063.84, 3),
#            obj(226, 3830.53, 1),
#            obj(227, 5128.55, 2),
#            obj(228, 5545.94, 1),
#            obj(229, 7712.94, 1),
#            obj(230, 3781.4, 2),
#            obj(231, 3781.58, 1),
#            obj(232, 2772.92, 1),
#            obj(233, 2271.34, 2),
#            obj(234, 5274.99, 3),
#            obj(235, 3622.75, 2),
#            obj(236, 2662.29, 3),
#            obj(237, 1427.56, 2),
#            obj(238, 4122.37, 2),
#            obj(239, 7250.06, 3),
#            obj(240, 8384.83, 3),
#            obj(241, 5810.88, 1),
#            obj(242, 3216.67, 2),
#            obj(243, 3803.58, 2),
#            obj(244, 5624.74, 1),
#            obj(245, 3625.35, 3),
#            obj(246, 4477.89, 1),
#            obj(247, 2997.56, 1),
#            obj(248, 5782.62, 1),
#            obj(249, 4679.78, 1),
#            obj(250, 5001.85, 2),
#            obj(251, 1555.31, 2),
#            obj(252, 3501.55, 3),
#            obj(253, 4891.13, 2),
#            obj(254, 5092.02, 2),
#            obj(255, 670.04, 1),
#            obj(256, 3768.5, 1),
#            obj(257, 2866.15, 3),
#            obj(258, 4666.09, 2),
#            obj(259, 3794.69, 2),
#            obj(260, 5736.31, 1),
#            obj(261, 6154.04, 2),
#            obj(262, 3901.3, 1),
#            obj(263, 1980.81, 2),
#            obj(264, 3741.22, 2),
#            obj(265, 5445.76, 1),
#            obj(266, 3094.02, 2),
#            obj(267, 3679.9, 2),
#            obj(268, 5809.06, 1),
#            obj(269, 4166.33, 2),
#            obj(270, 4703.66, 1),
#            obj(271, 5071.97, 2),
#            obj(272, 5053.85, 1),
#            obj(273, 15601.81, 1),
#            obj(274, 3472.29, 1),
#            obj(275, 5594.45, 1),
#            ]
# ==================CUSTOM DATA ===================

print('ALL objects')
pprint(objects)
print()

for zone in range(1, number_of_zones + 1):
    print(f'zone={zone}')
    selection = select_zone(objects, zone)
    print('selection')
    pprint(selection)
    print()

    while selection:
        fitted_list = fit_value(selection, value_limit=39000, value_name='biomass')
        pprint(fitted_list)
        print()

        delete_fitted_dicts(selection, fitted_list, value_name='biomass')

Well, I'm not sure that's the result. Although I'm not good at Python programming, I was able to run it and get the result. I have some doubts:
Did you type Custom data manually? How did you get this combination? Why did you limit the number of objects to 100? (number_of_objects = 100 number_of_zones = 3 max_biomass = 10000) You have again divided the space into three zones quite evenly, but if we divide by zones, then each object already belongs to the zone that is written in the "PJ" field. — Frodo, Jan 17 '23 at 20:01
The result of this algorithm should be displayed on the map. You have put in a lot of effort and I am grateful, but I think this problem is much more complex. — Frodo, Jan 17 '23 at 20:01
Biomass cannot be a random value. This value is in the field "StrOdl". — Frodo, Jan 17 '23 at 21:02
This look like the answer to your question (the key part being the algorithm), you just need to adapt to your actual data & use the result to mark each fid with the group it belongs to to show it on the map — Kasper, Jan 19 '23 at 12:33

Comrade Che · Answer 2 · 2023-01-18T10:11:43.720

The manual (or interactive) way of solving this problem. You can use it since you wrote that zoning is not needed.

Steps:

Turn on the Statistics panel.
Enable Selected features only in the Statistics panel.
Select the layer and the field for which the statistics will be displayed (in your case it's the StrOdl column).
Open the attributes table of the layer you want to allocate by years (in your case Layer_Poly).
Sort the column in descending order by which the data will be grouped (in your case it is the column StrOdl).
Select the objects in the attributes table one by one (starting from the largest value) until their sum is close to the desired one (in your case it is 117 000).
Select another object (donw the list) if you have significantly exceeded the desired amount.
Create a new column (you only need to do it once), in which the value of the group of objects will be written (in your case it is the year field).
When you are satisfied with the sum of values - open the field calculator and enter the value of the group in the year field (1, 2, 3, ..., 10). Don't forget to check the Only seleted features checkbox, otherwise everything will be overwritten.
Create in query builder such query, that already filled in values would not be shown in the attribute table, for example "year" NOT IN (1,2,3,4,5,6,7,8,10). Save the changes and update the table to make them disappear.

Repeat the procedure until all objects get their group number.

Statistics Panel

Query Builder

Result (image)

Result (table)

This is not a solution, your effort is evident, but it is a manual guessing of the total value, I can do that in MS Excel as well. By the way, you can also fill in the selected objects in the "year" field through the attribute table, without using the Query builder. This is only part of about 10.000 objects — Frodo, Jan 18 '23 at 19:14

Cluster polygons into equal parts in QGIS

2 Answers2