Алгоритм разделения сложной области на примитивы (прямоугольники) ⇐ JAVA

[Гость]

I have a problem for which I did not find a solution on the Internet and did not invent on my own.
There is an area of the room given by an array of points with X and Y coordinates, for example

Код: Выделить всё

CGPoint(x, y)

(their consecutive connection forms the outline of the room).
It is necessary to create an algorithm that would divide a complex area into simple geometric shapes - rectangles (example in the image below).
Preferably without third-party solutions.
The language in general does not matter, Swift/Java/Python/C++/C#/JS or any other, the main thing is the algorithm.
Example Image here
Here is an example of an array of area points from an image:

Код: Выделить всё

let exmplArray: [CGPoint] = [
(3, 12), (0, 12), (0, 18), (3, 18), (8, 18),
(8, 20), (15, 20), (15, 18), ( 18, 18),
(18, 0), (15, 0), (8, 0), (3, 0)
]

UPD: Now we assume that all angles are straight and all areas can be divided into rectangles (horizontally or vertically).
I tried to find ready-made solutions on the Internet, asked ChatGPT / Copilot, and then tried to create my algorithm, but it did not work, due to lack of experience.
The solutions I found here are not suitable for my task.
I would appreciate it if you could provide useful links to existing solutions, finished discussions, or offer your own.
Thanks a lot.


Источник: https://stackoverflow.com/questions/781 ... rectangles