mu_po_oformleniyu_mat_razdela_k_i_dp

41

Согласно формуле (6.7),

InnerRadius DCF		yD yC xV		xC xD	yV	xDyC		xC yD	20,3.
			xC	2	yC	2
				xD		yD

Окружностью максимального радиуса, которую можно построить внутри Q, в данном случае является максимальная из окружностей, вписанных в DAE

и DCF:

n = max(InnerRadius(	DAE),InnerRadius( DCF))=max(24;20,3)=24;
отсюда, по формуле (6.10),
S =	n	2 =	242 1809,6.
Истинно утверждение (	90 ) (		90 ).

Пусть задан четырехугольник со следующими координатами:

A (10; 10), B (90; 10), C (50; 30), D (60; 80) (рис. 6.13).

	y
			D
			C
	10	A	n
			B
	O	10	x
			Рис. 6.13

Проверим выпуклость четырехугольника ABCD, получив знаки определителей всех пар его смежных сторон:

sign					xA	xD	yA	yD			sign				60	10	80				sign				50		70				1;
														10
					xB	xA	yB	yA						90 10 10 10											80		0
sign					xB	xA	yB	yA			sign				10	10	10				sign			80			0				1;
													90
					xC	xB	yC	yB					50		90	30	10							40			20
sign					xC	xB	yC	yB			sign				90	30	10				sign					40	20				1;
														50
					xD	xC	yD	yC						60	50	80	30									10	50
sign					xD	xC	yD	yC			sign				50	80	30				sign					10	50				1.
														60
					xA	xD	yA	yD						10	60	10	80									50	70

42

Согласно формуле (6.2),

= +

1

+

1

–

1 + 1

= 2, причем

sign

xC

xB

yC

yB

= – sign , следовательно, ABCD – звездчатый четы-

xD

xC

yD

yC

рехугольник, значение угла BCD которого превышает 180 .

Рассмотрим значения углов

=

ACD и

=

ACB.

60

50

10

50

80

30

10

30

СD CA

cos

0,

следователь-

CD

CA

CD

CA

но,

> 90 .

90

50

10

50

10

30

10

30

CB CA

cos

0,

следователь-

CB

CA

CB

CA

но, > 90 .

Утверждение ( 90 ) ( 90 ) истинно.

Уравнение прямой AB в нормированном виде – 0x + 1y – 10 = 0, прямой

	AD –	7		x	5		y	20					0. Согласно формуле (6.4), биссектриса DAB оп-
		74			74			74
	ределяется уравнением										7			x 1	5		y 10	20		0, что приблизитель-
											74				74			74

но равно 7x – 13,6y + 66 =0.

Найдем координаты точки (x ,y ), являющейся центром окружности

единичного радиуса, вписанной в			DAB, как решение системы
7x			13,6y				66 0;
		0x	1y		10			1,	(6.12)
			0 2	1	2
также удовлетворяющее условию (x							10)(90 10) + (y		10)(10 10), то

есть x > 10.

Система (6.12) имеет два решения: (12; 11) и (8; 9). Выберем из них удовлетворяющее условию x > 10: (12;11). Найдем точки пересечения окружности с центром в точке (12;11), определенной уравнением (x – 12)2 + (y – 11)2 = 1, и радиусом 1 с прямой AC, уравнение которой x – 2y + 10 = 0.

Система уравнений
(x	12)2	(y 11)2 1;
x	2y 10	0

имеет два решения: (12,9; 11,45) и (11,1; 10,55). Выберем из этих точек ту, что расположена дальше от вершины A (10; 10). Этому условию удовлетворяет точ-

ка с координатами (12,9; 11,45): length((12,9; 11,45), A) = 3,24 > length((11,1; 10,55), A) = 1,23. Назовем выбранную точку C .

43

Зная координаты точек A(10; 10), C(50; 30), C (12,9; 11,45), определим радиус максимальной окружности, построенной внутри четырехугольника ABCD:

length C, A

x

x

2

y

y

2

50

10 2

30

10 2

A

2000

n

C A

C

13,8,

length C , A

2

2

10 2

11, 45 10 2

10,5125

x

x

y

y

A

12,9

C

A

C

отсюда по формуле (6.10) находим

S =

n

2 =

13,82

598,3.

6.2. Алгоритмическая форма представления метода

Шаг 1. Найти сумму

определителей всех пар сторон четырехугольника Q по

формуле

sign

xA

xD

yA

yD

sign

xB

xA

yB

yA

xB

xA

yB

yA

xC

xB

yC

yB

sign

xC

xB

yC

yB

sign

xD

xC

yD

yC

.

xD

xC

yD

yC

xA

xD

yA

yD

Шаг 2. Если |

| = 4 (четырехугольник Q – выпуклый) (рис. 6.14), найти значе-

ние максимального радиуса

max окружности, построенной внутри него,

по формуле

yq

yq

xM

xq

xq

yM

xq

yq

xq

yq

n

max

min

k

k mod4 1

ij

k mod4 1

k

ij

k

k mod4 1

k mod4 1

k

,

i, j 1...4 ;

k 1 4 ;

2

2

j

i 1, 1 i 3;

Inside(Mij,Q) 1

xqk mod4 1

xqk

yqk mod4 1

yqk

1, i 4.

где Mij

– точка пересечения биссектрис углов ui

и uj четырехугольника

Q, такая, что Inside(Mij, Q) = 1.

Функция принадлежности точки t фигуре F:

Inside (t, F)=

1, если t расположена внутри геометрической фигуры F;

0, если t расположена вне геометрической фигуры F.

где t – точка плоскости, t

T;

qp – вершины четырехугольника Q = (A, B, C, D), p = 1, …, 4;

xpt, ypt – координаты точки pt

T, xpt, ypt

.

Перейти к шагу 6.

Выпуклый четырехугольник (i = 1, j = 2)

max окружности, построенной

44

	Рис. 6.14
Шаг 3. Если |	| = 0 (Q – невыпуклый четырехугольник с самопересечением)
(рис. 6.15),
найти	{1, 2}: ( L T) (L = CrossingPoint((q , q mod 4 + 1), (q( + 1) mod 4 +

1, q( + 2) mod 4 + 1)),

где qj – вершины четырехугольника Q = (A, B, C, D), j = 1, …, 4; CrossingPoint((eн1, eк1), (eн2, eк2)) – функция, возвращающая точку пересечения отрезков (eн1, eк1) и (eн2, eк2); eн1, eк1, eн2, eк2 T.

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

max = max(InnerRadius((q ,L,q( +2)mod4+1)), InnerRadius((q mod4+1,L,q( +1)mod4+1))),

где функция InnerRadius(Tr) возвращает значение радиуса вписанной окружности для треугольника Tr.

Перейти к шагу 6.

Четырехугольник с самопересечением ( = 1)

Рис. 6.15

45

Шаг 4. Найти

: sign

xq

xq

2 mod4 1

yq

yq

2 mod4 1

= – sign .

xq mod4 1

xq

yq

yq

mod4 1

Если (

< 90 ) (

< 90 ),

где =

(q( +1)mod4+1, q , q mod4+1),

=

(q( +1)mod4+1,

q , q( +2)mod4+1)

–

углы,

образованные вершинами

q( +1)mod4+1, q , q mod4+1 и q( +1)mod4+1,

q ,

q( +2)mod4+1 четырехугольника Q =

(A, B, C, D) соответственно (рис. 6.16), найти значение максимального

радиуса max окружности, построенной внутри четырехугольника Q, по

формуле

max = max(InnerRadius((q( +1)mod4+1, q( +2)mod4+1, E)),

InnerRadius((q( +1)mod4+1, q mod4+1, F))),

где E = (q( +1)mod4+1, q mod4+1)

(q( +2)mod4+1, q );

F = (q( +1)mod4+1, q( +2)mod4+1)

(q , q mod4+1) (рис. 6.17).

Перейти к шагу 6.

Звездчатый четырехугольник ( = 3)

Рис. 6.16

max окружности, построенной

46

Рис. 6.17

Шаг 5. Найти (x ,y ):

K1биссx				+ K2биссy	+ K3бисс = 0;
		Kсторx Kстор y Kстор
		1		2	3		1;
				Kстор 2	Kстор 2
				1	2

x	xq	1 mod4 1	xq	2 mod4 1	xq	1 mod4 1
y	yq	1 mod4 1	yq	2 mod4 1		yq	1 mod4 1	0,

где K1биссx + K2биссy + K3бисс = 0 – уравнение биссектрисы угла (q mod4+1,

q( +1)mod4+1, q( +2)mod4+1), K1сторx + K2сторy + K3стор = 0 – уравнение прямой,

проходящей через точки q( +1)mod4+1, q( +2)mod4+1.

Найти точки пересечения P1, P2 окружности с центром в точке (x ,y )

и радиусом 1 с прямой (q( +1)mod4+1, q ). Найти значение максимального радиуса

внутри четырехугольника Q (рис. 6.18), по формуле

		length q ,q	1 mod4	,
	max
		length q ,q	1 mod4
где q' = P ,	{1, 2}:

length(P , q( +1)mod4+1)= max(length(P1, q( +1)mod4+1)), length(P2, q( +1)mod4+1),

где length(l) – функция, возвращающая длину отрезка l.

Звездчатый четырехугольник ( = 3)

Inside (t, F)=

1,

0,

47

Рис. 6.18

Шаг 6. Найти максимальную площадь окружности, которую можно построить внутри четырехугольника Q, по формуле

S = max 2.

6.3. Схема программы

На рис. 6.19 приведена блок-схема программы нахождения площади окружности, построенной внутри произвольного четырехугольника.

В блок-схеме использованы следующие обозначения:

1.(xA, yA), (xB, yB), (xC, yC), (xD, yD) – координаты точек A, B, C и D соответственно;

2.max - максимальный радиус окружности, построенной внутри четырехугольника Q;

3.k {AB, BC, CD, DA} – сторона четырехугольника Q;

4.pk – перпендикуляр к стороне k четырехугольника Q из точки M пересечения биссектрис углов ui и uj, если Inside(M, Q) = 1,

где

если t расположена внутри геометрической фигуры F; если t расположена вне геометрической фигуры F.

где t – точка плоскости, t T;

5.length(l) – функция, возвращающая длину отрезка l;

6.CrossingPoint((eн1, eк1), (eн2, eк2)) – функция, возвращающая точку пересе-

чения отрезков (eн1, eк1) и (eн2, eк2); eн1, eк1, eн2, eк2 T;

7. U=( DAB, ABC, BCD, CDA)– углы четырехугольника Q;

48

8.InnerRadius(Tr) – функция, возвращающая значение радиуса вписанной окружности для треугольника Tr;

9.= ( q( +1)mod4+1, q , q mod4+1), = (q( +1)mod4+1, q , q( +2)mod4+1) – углы, образованные вершинами q( +1)mod4+1, q , q mod4+1 и q( +1)mod4+1, q , q( +2)mod4+1 че-

тырехугольника Q = (A, B, C, D) соответственно;

10.max – такая точка внутри четырехугольника, Inside( max, Q) = 1,

что pv = length( max, q ),
где pv – перпендикуляры, проведенные к сторонам v, v	{(q( +1)mod4+1,
q( +2)mod4+1), (q( +1)mod4+1, q mod4+1)}, из точки max.

49

Начало

Координаты

точек A, B, C,

sign

xA

xD

yA

yD

sign

xB

xA

yB

yA

xB

xA

yB

yA

xC

xB

yC

yB

sign

xC

xB

yC

yB

sign

xD

xC

yD

yC

xD

xC

yD

yC

xD

yA

yD

xA

|

|

4

2

0

max

min

length

pk

Найти

{1, 2}: (

L

T):

max

i, j

L =CrossingPoint((q , q mod 4 +1),

1...4 ;

k AB, BC, CD, DA

j

i 1, 1 i 3;

(q( + 1)mod 4+1, q( +2)mod 4 +1))

1, i 4.

Найти

: u

> 180

max = max(InnerRadius((q , L, q(

+2)mod 4 +1 )),

InnerRadius((q

mod 4 +1, L, q(

+ 1)mod 4+1)))

нет

(

< 90 )

(

< 90 )?

max = length(

max, qk)

да

max = max(InnerRadius((q(

+ 1)mod 4+1, q(

+2)mod 4 +1, E)),

InnerRadius((q(

+ 1)mod 4+1, q mod 4 +1, F))), где

E = (q(

+ 1)mod 4+1, q mod 4 +1)

(q( +2)mod 4 +1, q );

F = (q(

+ 1)mod 4+1, q( +2)mod 4 +1)

(q , q mod 4 +1).

S = max 2

S

Конец

Рис. 6.19

50

Основная литература

1.Математическая энциклопедия: Гл. ред. И.М.Виноградов, т.3 Коо-Од – М: "Советская энциклопедия", 1982. – 1184 стб., ил.

2.Карманов В.Г. Математическое программирование, М.: – Наука, 1975.

3.Препарата Ф., Шеймос М. Вычислительная геометрия. Введение: Пер.

сангл. – М.: Мир, 1989. – 478 с.

4.Ласло М. Вычислительная геометрия и компьютерная графика на С++: Пер. с англ..: "Издательство Бином", 1997. – 304 с.

5.Фролькис В.А. Введение в теорию и методы оптимизации для экономистов. – СПб.: Питер, 2002.

Дополнительная литература

1.Дальниченко И.А. и др. Автоматизированные системы управления предприятиями: Учебник для инженерных специальностей вузов / И.А.Дальниченко, В.А.Мясников, В.Н.Четвериков. – М.: Машиностроение,

1984. – 360 с.

2.Новиков Ф.А. Дискретная математика для программистов. – СПб.: Пи-

тер, 2000. – 304 с.

3.Гуц А.К. Математическая логика и теория алгоритмов: Уч. пособие. – Омск: Диалог-Сибирь, 2003. – 108 с.