Разрезать двумя взаимноперпендикулярными прямыми выпуклый многоугольник на 4 равные части

@1vlad · Регистрация: 13.08.2013

Студворк — интернет-сервис помощи студентам

Здравствуйте программисты!

Мне необходимо написать программу, которая бы разрезала двумя взаимноперпендикулярными прямыми выпуклый многоугольник на 4 равные части.
Количество вершин и координаты каждой вводятся при старте программы.
Подскажите как это реализовать в теории

@tarasso · 08.11.2013, 21:28

Интересно, программа проверяет многоугольник на выпуклость. Или при вводе Вы точно уверены, что многоугольник выпуклый?

@1vlad · 08.11.2013, 21:50 **[ТС]**

да,проверяет,код уже написал,только не могу теперь понять что там с разрезом

@tarasso · 08.11.2013, 23:35

На идейном уровне можно попробовать поступить т.о.
1) найти центр выпуклого многоугольника
2) совместить точку пересечения взаимно перпендикулярных прямых с центром многоугольника
3) вращая взаимно перпендикулярные прямые относительно центра многоугольника на угол $https://www.cyberforum.ru/cgi-bin/latex.cgi?0<\alpha <180$ находить площади четырех фигур, полученных в результате разреза. Решение будет найдено, когда на всем диапазоне изменения угла будет получен разрез при котором раница между площадями фигур будет минимальной (в идеале о)

@palva · 09.11.2013, 01:01

Похоже, что это трудоемкая вычислительная задача.
Одна из прямых должна делить площадь пополам. Выберем произвольно направление этой прямой. Это будет начальное направление, потом мы будем это направление менять. Двигая прямую параллельно самой себе, добиваемся, чтобы она разбивала площадь пополам. Далее берем перпендикулярное направление и так же, двигая прямую, получаем прямую, разбивающую площадь пополам. Но это не будет решением, поскольку четвертушки будут по площади одни с избытком, другие с недостатком. Договоримся поворачивать направление первой прямой в сторону четвертушек с избытком (они лежат в вертикальных углах), шаг выберем сначала 45 градусов, следующий шаг в два раза меньше, потом еще в два раза меньше и т. д. После поворота потребуется сдвинуть прямые параллельно самим себе, чтобы выровнять площади, лежащие по разные стороны прямых. Так что точка пересечения прямых будет сдвигаться. По идее этот процесс должен сойтись к решению, если оно существует для данного многоугольника. Для меня непонятен вопрос, для любого ли многоугольника решение существует.

Наверно, можно придумать другой алгоритм. Можно также взять другой алгоритм для уменьшения шагов поворота.

@tarasso · 09.11.2013, 12:07

Разбиений на четире равновеликие части выпуклого многоугольника тоже может быть некоторое множество. Поэтому какое выбрать разбиение здесь тоже непонятно. В принципе можно выбрать первое попавшееся разбиение, которое удовлетворяет заданной степени точности и на этом остановиться.

@Firsto · 29.11.2013, 15:31

Сообщение от palva

Похоже, что это трудоемкая вычислительная задача.
Одна из прямых должна делить площадь пополам. Выберем произвольно направление этой прямой. Это будет начальное направление, потом мы будем это направление менять. Двигая прямую параллельно самой себе, добиваемся, чтобы она разбивала площадь пополам.
...
Наверно, можно придумать другой алгоритм. Можно также взять другой алгоритм для уменьшения шагов поворота.

Мучаюсь с подобной задачей, писал здесь: https://www.cyberforum.ru/java/thread1022760.html

Суть решения понял, но как записать это алгоритмически - не могу понять.
Т.е. есть у меня координаты вершин. Могу их складывать, вычитать, умножать, делить.

Можете помочь?

@Old_Daniel · 14.08.2014, 01:47

Сообщение от tarasso

3) вращая взаимно перпендикулярные прямые относительно центра многоугольника на угол https://www.cyberforum.ru/cgi-bin/latex.cgi?0<\alpha <180 находить площади четырех фигур, полученных в результате разреза. Решение будет найдено, когда на всем диапазоне изменения угла будет получен разрез при котором раница между площадями фигур будет минимальной (в идеале о)

-- вот на этом месте программа и повиснет. Посчитать это можно, но не за несколько секунд, как хотелось бы.

@Firsto · 14.08.2014, 03:31

Сообщение от Old_Daniel

- вот на этом месте программа и повиснет. Посчитать это можно, но не за несколько секунд, как хотелось бы.

Если разбивать сторону методом бисекции и сдвигать линию в нужную сторону - не больше 50 итераций потребуется даже для очень большой точности.

ValeryS · 14.08.2014, 04:02

Сообщение от 1vlad

выпуклый многоугольник на 4 равные части.

а что есть "равные части" ?
равные по площади или подобные?

@Firsto · 14.08.2014, 04:38

Сообщение от ValeryS

а что есть "равные части" ?
равные по площади или подобные?

По площади.

@Alex5 · 14.08.2014, 14:17

Не по теме:

Сообщение от tarasso

1) найти центр выпуклого многоугольника

tarasso, имеется в виду центр тяжести? Но прямая, делящая многоугольник на две равновеликие части, может не проходить через центр тяжести. Что такое "центр многоугольника"?

Сообщение от palva

для любого ли многоугольника решение существует

Сообщение от palva

Выберем произвольно направление этой прямой. Это будет начальное направление, потом мы будем это направление менять. Двигая прямую параллельно самой себе, добиваемся, чтобы она разбивала площадь пополам. Далее берем перпендикулярное направление и так же, двигая прямую, получаем прямую, разбивающую площадь пополам. Но это не будет решением, поскольку четвертушки будут по площади одни с избытком, другие с недостатком.

Так как S₁ + S₂ = S/2, то (см. рис.)

$https://www.cyberforum.ru/cgi-bin/latex.cgi?S_1 \;=\; \frac{1}{4}S \:+\: \delta(a), \;\; S_2 \;=\; \frac{1}{4}S \:-\: \delta(a), \\ S_3 \;=\; \frac{1}{4}S \:+\: \delta(a), \;\; S_4 \;=\; \frac{1}{4}S \:-\: \delta(a). \\$

При повороте на 90 градусов 1-я часть переходит 2-ю. Следовательно, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\delta( a+90^{\circ} ) \;=\; -\delta( a).$

@Alex5 · 14.08.2014, 14:25

Не по теме:

Сообщение от Alex5

При повороте

Здесь подразумевается, что выбирается другое направление. И строятся прямые так, как описано в сообщении от palva.

@Old_Daniel · 14.08.2014, 14:36

Всё это здорово. Вот мы выбираем прямую и разбиваем ей многоугольник. Чтобы проверить, разбили ли мы его на пополам, надо посчитать площади частей. Как это сделать быстро? Или, точнее, как это сделать быстро, если нам многоугольник задан только координатами вершин?
После того, как мы сдвинем пряммую/прямые, площади получающихся новых частей надо будет пересчитывать. Как это лучше сделать?

@Alex5 · 14.08.2014, 16:07

Сообщение от Old_Daniel

площади получающихся новых частей надо будет пересчитывать

Многоугольник можно разбить на треугольники. Для треугольника:

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\vec{AB} \:\times\: \vec{AC} \;= \; 2 \cdot S_{ABC}$

(Здесь площадь со знаком. Если поменять местами B и C, знак изменится на противоположный.)

На рис.2, для произвольной точки O, $https://www.cyberforum.ru/cgi-bin/latex.cgi?\;\;2\cdot S \;=\; \vec{OA_1} \times \vec{A_1A_2} \:+\: \vec{OA_2} \times \vec{A_2A_3} \:+\: ... \:+\: \vec{OA_n} \times \vec{A_nA_1}.$

@Old_Daniel · 14.08.2014, 16:45

Этим вы ведёте к тому, что можно разбить многоугольник на треугольники один раз, а затем довольно быстро искать тот треугольник, который будет "посередине", не пересчитывая каждый раз площадей остальных?

@Alex5 · 15.08.2014, 12:27

Сообщение от Old_Daniel

Этим вы ведёте к тому, что можно разбить многоугольник на треугольники один раз

Это на Ваше усмотрение. Я написал, как найти площадь многоугольника, зная координаты вершин. Для треугольника (x₀, y₀), (x₁, y₁), (x₂, y₂), например, получится

$https://www.cyberforum.ru/cgi-bin/latex.cgi?2\cdot S \;=\; \begin{vmatrix}x_{\small 1} -x_{\small 0} & x_{\small 2} -x_{\small 0} \\ y_{\small 1} -y_{\small 0} & y_{\small 2} -y_{\small 0} \end{vmatrix}$

@Old_Daniel · 15.08.2014, 12:58

Спасибо. За себя скажу, что я это уже знал. Но вот как с использованием этого построить качественный алгоритм, который решит задачу, пока не придумал.

12.09.2014, 00:20

1vlad, вам удалось написать программу?

@Nacuott · 12.09.2014, 21:04

Любая прямая, проходящая через центр тяжести плоской, выпуклой фигуры, делит ее на две равные площади. Две (любые) перпендикулярные прямые,проходящие через центр тяжести этой фигуры делят ее на четыре равновеликие области.По-моему, так.

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@1vlad 10 / 1 / 0 Регистрация: 13.08.2013 Сообщений: 70

	Разрезать двумя взаимноперпендикулярными прямыми выпуклый многоугольник на 4 равные части 08.11.2013, 21:03. Показов 6209. Ответов 23 Метки нет (Все метки) Здравствуйте программисты! Мне необходимо написать программу, которая бы разрезала двумя взаимноперпендикулярными прямыми выпуклый многоугольник на 4 равные части. Количество вершин и координаты каждой вводятся при старте программы. Подскажите как это реализовать в теории 0

@tarasso 749 / 460 / 50 Регистрация: 13.05.2012 Сообщений: 963
	08.11.2013, 21:28
	Интересно, программа проверяет многоугольник на выпуклость. Или при вводе Вы точно уверены, что многоугольник выпуклый? 0

@1vlad 10 / 1 / 0 Регистрация: 13.08.2013 Сообщений: 70
	08.11.2013, 21:50 [ТС]
	да,проверяет,код уже написал,только не могу теперь понять что там с разрезом 0

@tarasso 749 / 460 / 50 Регистрация: 13.05.2012 Сообщений: 963
	08.11.2013, 23:35
	На идейном уровне можно попробовать поступить т.о. 1) найти центр выпуклого многоугольника 2) совместить точку пересечения взаимно перпендикулярных прямых с центром многоугольника 3) вращая взаимно перпендикулярные прямые относительно центра многоугольника на угол $https://www.cyberforum.ru/cgi-bin/latex.cgi?0<\alpha <180$ находить площади четырех фигур, полученных в результате разреза. Решение будет найдено, когда на всем диапазоне изменения угла будет получен разрез при котором раница между площадями фигур будет минимальной (в идеале о) 1

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	09.11.2013, 01:01
	Похоже, что это трудоемкая вычислительная задача. Одна из прямых должна делить площадь пополам. Выберем произвольно направление этой прямой. Это будет начальное направление, потом мы будем это направление менять. Двигая прямую параллельно самой себе, добиваемся, чтобы она разбивала площадь пополам. Далее берем перпендикулярное направление и так же, двигая прямую, получаем прямую, разбивающую площадь пополам. Но это не будет решением, поскольку четвертушки будут по площади одни с избытком, другие с недостатком. Договоримся поворачивать направление первой прямой в сторону четвертушек с избытком (они лежат в вертикальных углах), шаг выберем сначала 45 градусов, следующий шаг в два раза меньше, потом еще в два раза меньше и т. д. После поворота потребуется сдвинуть прямые параллельно самим себе, чтобы выровнять площади, лежащие по разные стороны прямых. Так что точка пересечения прямых будет сдвигаться. По идее этот процесс должен сойтись к решению, если оно существует для данного многоугольника. Для меня непонятен вопрос, для любого ли многоугольника решение существует. Наверно, можно придумать другой алгоритм. Можно также взять другой алгоритм для уменьшения шагов поворота. 2

@tarasso 749 / 460 / 50 Регистрация: 13.05.2012 Сообщений: 963
	09.11.2013, 12:07
	Разбиений на четире равновеликие части выпуклого многоугольника тоже может быть некоторое множество. Поэтому какое выбрать разбиение здесь тоже непонятно. В принципе можно выбрать первое попавшееся разбиение, которое удовлетворяет заданной степени точности и на этом остановиться. 1

@Old_Daniel 0 / 0 / 0 Регистрация: 13.08.2014 Сообщений: 9
	14.08.2014, 14:36
	Всё это здорово. Вот мы выбираем прямую и разбиваем ей многоугольник. Чтобы проверить, разбили ли мы его на пополам, надо посчитать площади частей. Как это сделать быстро? Или, точнее, как это сделать быстро, если нам многоугольник задан только координатами вершин? После того, как мы сдвинем пряммую/прямые, площади получающихся новых частей надо будет пересчитывать. Как это лучше сделать? 0

@Old_Daniel 0 / 0 / 0 Регистрация: 13.08.2014 Сообщений: 9
	14.08.2014, 16:45
	Этим вы ведёте к тому, что можно разбить многоугольник на треугольники один раз, а затем довольно быстро искать тот треугольник, который будет "посередине", не пересчитывая каждый раз площадей остальных? 0

@Old_Daniel 0 / 0 / 0 Регистрация: 13.08.2014 Сообщений: 9
	15.08.2014, 12:58
	Спасибо. За себя скажу, что я это уже знал. Но вот как с использованием этого построить качественный алгоритм, который решит задачу, пока не придумал. 0

AlexB
	12.09.2014, 00:20
	1vlad, вам удалось написать программу?

@Nacuott 1833 / 1027 / 192 Регистрация: 24.02.2013 Сообщений: 3,084 Записей в блоге: 12
	12.09.2014, 21:04
	Любая прямая, проходящая через центр тяжести плоской, выпуклой фигуры, делит ее на две равные площади. Две (любые) перпендикулярные прямые,проходящие через центр тяжести этой фигуры делят ее на четыре равновеликие области.По-моему, так. 0