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, Commented Jan 10, 2023 at 18:44
@Kasper, attribute field is PJ (01,02,03) and field StrOdl. It is enough to make nessesary geomertry if you like. — Frodo, Commented Jan 11, 2023 at 6:15
What you need looks like a variant of the Knapsack problem, you might want to investigate the related algorithms — Kasper, Commented Jan 11, 2023 at 7:22

Comrade Che · Accepted Answer · 2023-01-17 17:34:42Z

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] >= 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 => 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, Commented Jan 17, 2023 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, Commented Jan 17, 2023 at 20:01
Biomass cannot be a random value. This value is in the field "StrOdl". — Frodo, Commented Jan 17, 2023 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, Commented Jan 19, 2023 at 12:33

Comrade Che · Accepted Answer · 2023-01-18 10:11:43Z

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, Commented Jan 18, 2023 at 19:14

Stack Exchange Network

Cluster polygons into equal parts in QGIS

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged
qgis
clustering
spatial-analysis
geostatistical-analyst
spatial-cluster
or ask your own question.

Linked

Hot Network Questions

Cluster polygons into equal parts in QGIS

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged qgisclusteringspatial-analysisgeostatistical-analystspatial-cluster or ask your own question.

Linked

Related

Hot Network Questions

Not the answer you're looking for? Browse other questions tagged
qgis
clustering
spatial-analysis
geostatistical-analyst
spatial-cluster
or ask your own question.