Невыпуклые многоугольники

From

Valentin Kononov (2:5035/26.12)

To

Aleksey Kuhtenkov

Date

2002-05-02T00:38:05Z

Area

RU.ALGORITHMS

Привет Aleksey!

 28.04.02 писал Aleksey Kuhtenkov к All, а было на часах 10:00:47.

 AK>     Имеем массив отрезков, заданных двумерными координатами. Отрезки не
 AK> пересекаются и образуют невыпуклые многоугольники (понятно сказал? :)).
 AK> Есть координаты точки. Подскажите, как получить многоугольник, в котором 
 AK> лежит точка.

Я бы начал с того, что сформировал массив многоугольников (МУ);
 затем урезал бы невыпуклые МУ, выбросив из них внутренние точки, т.е.
превратил бы их в выпуклые МУ;
 внутренние точки с 2 прилегающими точками выпуклого МУ дали бы мне
"минус-МУ" (МУ, точки которых не принадлежат исходному), которые тоже надо
включать в тот же массив и так же обрабатывать, но если они окажутся
невыпуклыми, то выброшенные из них "минус-минус-МУ" надо уже считать за
"плюс-МУ", т.к. принадлежащие им точки принадлежат исходному МУ;
 по мере обработки МУ я бы построил деревья: корень - выпуклый МУ, листья
поочередно "-" и "+" МУ.
  Дальше понятно. Надо только учитывать, что выпуклые МУ могут произвольно
пересекаться, быть вложенными и т.п., так что искать надо до тех пор, пока
не найдем МУ, которому точка принадлежит или не проверим все корни
деревьев и все деревья, корневым МУ которых точка принадлежит. 
  Если построения можно выполнить предварительно, то сам поиск будет
ненамного сложнее, чем для выпуклых МУ.

                    Всего хорошего, Valentin.

--- Таймыр 2.00 (c) Евгений Варнавский
 * Origin: Одежда от Версачки. Высокая мода "от купюр" (2:5035/26.12)