ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Valentin Kononov                     2:5035/26.12   02 May 2002  00:38:05
 To : Aleksey Kuhtenkov
 Subject : Hевыпуклые многоугольники
 -------------------------------------------------------------------------------- 
 

 
  28.04.02 писал Aleksey Kuhtenkov к All, а было на часах 10:00:47.
 
  AK>     Имеем массив отрезков, заданных двумерными координатами. Отрезки не
  AK> пересекаются и образуют невыпуклые многоугольники (понятно сказал? :)).
  AK> Есть координаты точки. Подскажите, как получить многоугольник, в котором 
  AK> лежит точка.
 
 Я бы начал с того, что сформировал массив многоугольников (МУ);
  затем урезал бы невыпуклые МУ, выбросив из них внутренние точки, т.е.
 превратил бы их в выпуклые МУ;
  внутренние точки с 2 прилегающими точками выпуклого МУ дали бы мне
 "минус-МУ" (МУ, точки которых не принадлежат исходному), которые тоже надо
 включать в тот же массив и так же обрабатывать, но если они окажутся
 невыпуклыми, то выброшенные из них "минус-минус-МУ" надо уже считать за
 "плюс-МУ", т.к. принадлежащие им точки принадлежат исходному МУ;
  по мере обработки МУ я бы построил деревья: корень - выпуклый МУ, листья
 поочередно "-" и "+" МУ.
   Дальше понятно. Hадо только учитывать, что выпуклые МУ могут произвольно
 пересекаться, быть вложенными и т.п., так что искать надо до тех пор, пока
 не найдем МУ, которому точка принадлежит или не проверим все корни
 деревьев и все деревья, корневым МУ которых точка принадлежит. 
   Если построения можно выполнить предварительно, то сам поиск будет
 ненамного сложнее, чем для выпуклых МУ.
 
                     Всего хорошего, Valentin.
 
 --- Таймыр 2.00 (c) Евгений Варнавский
  * Origin: Одежда от Версачки. Высокая мода "от купюр" (2:5035/26.12)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    <без заголовка>   Aleksey Kuhtenkov   28 Apr 2002 10:00:47   Hевыпуклые многоугольники   Valentin Kononov   02 May 2002 00:38:05