Простенькая задачка на выходные

← →
Igorek © (2004-04-16 17:27) [0]

На координатной плоскости дан произвольный, несамопересекающийся многоугольник, каждая сторона которого паралельна одной из осей координат.
Требуется найти радиус наибольшего круга (с точностью t), который можно поместить в многоугольник.
---
Алгоритм решения желательно изложить просто словами.

← →
Igorek © (2004-04-16 17:27) [0]

← →
Serrrrg (2004-04-16 17:39) [1]

Система координат надо полагать декартова? Т.е. все углы прямые?

← →
Serrrrg (2004-04-16 17:39) [1]

Система координат надо полагать декартова? Т.е. все углы прямые?

← →
Igorek © (2004-04-16 17:41) [2]

> Serrrrg (16.04.04 17:39) [1]
> Система координат надо полагать декартова? Т.е. все углы
> прямые?

Да.

← →
Igorek © (2004-04-16 17:41) [2]

> Serrrrg (16.04.04 17:39) [1]
> Система координат надо полагать декартова? Т.е. все углы
> прямые?

Да.

← →
Romkin © (2004-04-16 17:47) [3]

Тогда этот многоугольник - квадрат :))

← →
Romkin © (2004-04-16 17:47) [3]

Тогда этот многоугольник - квадрат :))

← →
Serrrrg (2004-04-16 17:47) [4]

Нет :)

← →
Serrrrg (2004-04-16 17:47) [4]

Нет :)

← →
Romkin © (2004-04-16 17:48) [5]

Тьфу. Пятница. Прямоугольник.
Наибольший радиус окружности равен наименьшему расстоянию между сторонами (выбираем из двух пар - вертикальной и горизонтальной)

← →
Romkin © (2004-04-16 17:48) [5]

← →
Serrrrg (2004-04-16 17:49) [6]

Опять нет :)

← →
Serrrrg (2004-04-16 17:49) [6]

Опять нет :)

← →
Serrrrg (2004-04-16 17:50) [7]

Спираль например прямоугольная.

← →
Serrrrg (2004-04-16 17:50) [7]

Спираль например прямоугольная.

← →
Nikolay M. © (2004-04-16 17:50) [8]

> Romkin © (16.04.04 17:48) [5]

Не-а :)
В условии не сказано, что углов нельзя касаться :(

← →
Nikolay M. © (2004-04-16 17:50) [8]

> Romkin © (16.04.04 17:48) [5]

Не-а :)
В условии не сказано, что углов нельзя касаться :(

← →
Igorek © (2004-04-16 17:51) [9]

> Romkin © (16.04.04 17:48) [5]

---
| |
| --
| |
------

← →
Igorek © (2004-04-16 17:51) [9]

> Romkin © (16.04.04 17:48) [5]

---
| |
| --
| |
------

← →
Romkin © (2004-04-16 17:51) [10]

ТАк он что, не замкнутый?

← →
Romkin © (2004-04-16 17:51) [10]

ТАк он что, не замкнутый?

← →
Igorek © (2004-04-16 17:52) [11]

> Romkin © (16.04.04 17:51) [10]
> ТАк он что, не замкнутый?

А что такой бывает?

← →
Igorek © (2004-04-16 17:52) [11]

> Romkin © (16.04.04 17:51) [10]
> ТАк он что, не замкнутый?

А что такой бывает?

← →
Romkin © (2004-04-16 17:52) [12]

Igorek © (16.04.04 17:51) [9] "Бегущая линия" по точкам. Сначала вертикаль, потом горизонталь. С выбором наибольшей прямоугольной внутренней области

← →
Romkin © (2004-04-16 17:52) [12]

← →
Serrrrg (2004-04-16 17:53) [13]

> А что такой бывает?

Бывает.

← →
Serrrrg (2004-04-16 17:53) [13]

> А что такой бывает?

Бывает.

← →
Nikolay M. © (2004-04-16 17:54) [14]

> Romkin © (16.04.04 17:52) [12]

Задача не сводится к нахождению макс. вписанного прям-ка.

← →
Nikolay M. © (2004-04-16 17:54) [14]

> Romkin © (16.04.04 17:52) [12]

Задача не сводится к нахождению макс. вписанного прям-ка.

← →
Romkin © (2004-04-16 17:56) [15]

ЗАдача сводится к нахождению максимального вписанного выпуклого многоугольника.
Тогда отсекаем точки, пока он не останется :))

← →
Romkin © (2004-04-16 17:56) [15]

← →
Nikolay M. © (2004-04-16 17:58) [16]

Окружность тоже можно считать правильным многоугольником с бесконечным числом сторон :)

← →
Nikolay M. © (2004-04-16 17:58) [16]

Окружность тоже можно считать правильным многоугольником с бесконечным числом сторон :)

← →
Igorek © (2004-04-16 18:04) [17]

> Serrrrg (16.04.04 17:53) [13]
> > А что такой бывает?
>
> Бывает.

Бывает "незамкнутый многоугольник"??? А незамкнутый прямоугольник, квадрат? Это уже ломаная линия.

← →
Igorek © (2004-04-16 18:04) [17]

← →
Serrrrg (2004-04-16 18:08) [18]

>Бывает "незамкнутый многоугольник"??? А незамкнутый >прямоугольник, квадрат? Это уже ломаная линия.

Незамкнутое множество это множество не содержащее свою границу.

Вот например незамкнутый квадрат:

0<x<1, 0<y<1

А вот замкнутый:

0<=x<=1, 0<=y<=1

← →
Serrrrg (2004-04-16 18:08) [18]

← →
Igorek © (2004-04-16 18:10) [19]

> Romkin © (16.04.04 17:56) [15]
> ЗАдача сводится к нахождению максимального вписанного выпуклого
> многоугольника.
> Тогда отсекаем точки, пока он не останется :))

К слову.
Какой из двух многоугольников в Вашем контексте больший?
----
| |
| |
----

--------------------------------------------
| |
--------------------------------------------

А теперь рассмотрим такой:
--------
| |
| ----
| |
| ----
| |
--------

← →
Igorek © (2004-04-16 18:10) [19]

← →
Igorek © (2004-04-16 18:13) [20]

> Serrrrg (16.04.04 18:08) [18]
> >Бывает "незамкнутый многоугольник"??? А незамкнутый >прямоугольник,
> квадрат? Это уже ломаная линия.
>
> Незамкнутое множество это множество не содержащее свою границу.
>
> Вот например незамкнутый квадрат:
>
> 0<x<1, 0<y<1
>
> А вот замкнутый:
>
> 0<=x<=1, 0<=y<=1

Понял что вы имеете ввиду. Вот только у множества нету границ, как таковых. Вобщем скажем проще - круг может (да и наверное будет) касаться многоугольника.

← →
Igorek © (2004-04-16 18:13) [20]

← →
Serrrrg (2004-04-16 18:28) [21]

> Вот только у множества нету границ, как таковых.

Как это нет границ?
Границей множества называется множество точек, в любой эпсилон-окрестности которых есть точки как принадлежащие к заданному множеству так и не принадлежащие. (За точность определения не ручаюсь).
Хотя к задаче это никакого отношения не имеет. :)

← →
Serrrrg (2004-04-16 18:28) [21]

← →
Igorek © (2004-04-16 18:36) [22]

> Serrrrg (16.04.04 18:28) [21]
> > Вот только у множества нету границ, как таковых.
>
> Как это нет границ?
> Границей множества называется множество точек, в любой эпсилон-окрестности
> которых есть точки как принадлежащие к заданному множеству
> так и не принадлежащие.

Я имелл ввиду множество вообще. Какая граница у множества (яблоко, груша, слива)?

← →
Igorek © (2004-04-16 18:36) [22]

← →
Igorek © (2004-04-18 10:27) [23]

So what?

← →
Igorek © (2004-04-18 10:27) [23]

So what?

Имхо попробовать применить такой принцип:

var
ln:double
...
ln:=0;
while (внутри многоугольника остаются незакрашеные области) do
begin
Закрашиваем в многоугольнике все что находится на расстоянии <=ln от его контура;
ln:=ln+t;
end;
Result:=ln;

Это только принцип (первое что мне пришло в голову). На самом деле нужно немного его переработать, но имхо это можно сделать.

Что-бы не было так грусно, скажу что эта "простенькая" задача была в составе заданий на коммандном чемпионате мира по программированию среди ВУЗов.

Igorek © (16.04.04 18:10) [19] Млин. Наибольший выпуклый. Это и будет прямоугольник, после отсечения сторон :)) А как найти радиус для прямоугольника, я уже писал.
Впрочем, тут сложность есть: если эта штука имеет вид гантели, то не очень удобно, она распадется на две части...

> Romkin © (19.04.04 10:55) [27]
> Впрочем, тут сложность есть: если эта штука имеет вид гантели,
> то не очень удобно, она распадется на две части...

Это не сложность - это сущность задачи.

>Romkin © (19.04.04 10:55)

Неа... Ты не прав...
Учти что могут быть варианты, где вписаный круг может касаться не только сторон, но также и одного или нескольких из "вогнутых" углов многоугольника.
Например нарисуй многоугольник в форме креста. И посмотри теперь как там будет врисываться круг

Жаль, что народ не заинтересовала эта задача. Если еще пару дней не будет ответа - я выложу свои соображения насчет решения.

В принципе можно применить что-то типа волнового алгоритма для нахождения центра круга. Но при этом есть некоторые сложности и не гарантируется хорошая точность...

А если применить инверсию с центром, лежащим за пределами многоугольника и радиусом меньшим, чем мин. расстояние до любой точки многоугольника. Тогда, по определению отрезки перейдут в окружности. Потом находим пересечение окружностей, а... вот тут мысль останавливается, потому как не помню, чего нужно нарисовать, чтобы это чего-то перешло в окружность. Надеюсь, идея понятна.

Решение конечно построительное, но помня аналитические формулы инверсии, я думаю можно как-то изгольнуться.

← →
Кабан (2004-04-20 14:29) [33]

Мне кажется, что окружность будет вписана в максимальный квадрат, стороны которого расположены либо параллельно осям координат, либо под углом в 45%. Для первого случая найти такой квадрат не сложно. Во втором случае как минимум одна из сторон квадрата (а может даже и 2) будет проходить через вершину многоугольника (иначе такой квадрат вписан в другой квадрат большего размера, у которого стороны параллельны осям). В конце- концов можно просто перебрать все вершины многоугольника и отталкиваясь от них попытаться построить такой квадрат.

← →
Кабан (2004-04-20 14:29) [33]

Привожу свои мысли насчет решения задачи.
Для начала определяем минимальный прямоугольник P, который полностью покроет наш многоугольник М. Назовем его "покрывающим". В нем будем выбирать некоторые точки, анализ которых даст нам возможность исключить области, в которых может находиться центр искомого круга. Такие области будем хранить в глобальном списке.
Определим функцию f(x, y), которая в точках внутри Р дает расстояние до ближайшей границы М. Пусть для точек не внутри М это значение будет со знаком минус.
Также определим простую функцию g(x, y), которая даст расстояние от точки до ближайшей границы Р.
Напишем процедуру FindCenter(x, y), которая:
- находит значение функций f и g
- значение f сохраняет в глобальную переменную maxradius
- на основании этих значений f и g добавляет в список исключенные области (предлагаю подумать как)
- если среди доступных областей нету "покрывающего" прямоугольника, диагональ которого ...(додумать :-) ) относительно точности, то выставить глобальный флажок found и вернуться
- вызывает сама себя для прибл. центральной точки из каждой доступной области
- после каждого вызова если установлен found, то возвращается.

Вызываем FindCenter для центра Р.

---
подозреваю, что решение не досконально и можно рекурсию заменить итерацией

Простенькая задачка на выходные Найти похожие ветки