1 Востаннє редагувалося fer123 (09.02.2014 16:27:41)

Тема: Обхід найменшого многокутника на системі координат

збережено вершини відрізків, які з'єднуються у такий клас:

Chemist-i написав:

Мій варіант:

    Type
        TtwoCoordinates = Record
            X1 : Integer;
            Y1 : Integer;
            X2 : Integer;
            Y2 : Integer;
        End;     

і дано точку яку потрібно перевірити.
На малюнку коло - це вершина, зелена лінія - це відрізок який з'єднує вершини (на границях графіка також є точки, я просто не домалював).

Потрібний цикил який перейде тільки по відрізкам які оточують точку (оранжевий контур), та перевірить чи якась з них є на границі координат (тобто нулі або максимуми х та у).

Я не дуже добре пам'ятаю, але мені здається є цикл для виходу з лабіринту, який відповідно до напряму руху буде перевіряти чи можна рухатись вправо, якщо ні то вперед, якщо ні то вправо, якщо ні, то рух назад.
Чи підійде цей алгоритм для цієї задачі, та як його реалізувати?

Сама задаче це перевірити чи многокутник довколо точки доторкається до границь і чи доторкається взагалі. Можливо у вас є інші ідеї, пропонуйте, уточнюйте

Post's attachments

tab3.jpg 67.83 kb, 37 downloads since 2014-02-09 

2

Re: Обхід найменшого многокутника на системі координат

коло - це вершина, зелена лінія - це відрізок який з'єднує вершини
http://svalko.org/data/2014_02_04_10_20_images_vfl_ru_ii_1391368967_f7f49226_4143190_m.jpg
Подякували: Chemist-i, Bartash, DOP, fer1234

3

Re: Обхід найменшого многокутника на системі координат

ой, все розписав, а картинку забув загрузити. виправлено

4 Востаннє редагувалося Chemist-i (09.02.2014 21:11:12)

Re: Обхід найменшого многокутника на системі координат

fer123
Відрізок, якщо його продовжити умовною лінією, ділить простір на 2.
Обходячи то можна пам_ятати в якій ми півплощині. І коли дійшли до початкової точки, значить ми є у замкненій фігурі, а якщо до стінки(верха/низу) - розімкнутій.
Умова досить легка, кінцева точка і-того відрізка - є початковою (і+1)-того. Якщо з однієї точки багато відрізків стартує - вибираємо той який по часовій (якщо рухаймося по часовій) або навпаки. Якщо відрізок нікуди не веде (повертаймося в його початкову точку (1-шу).

x

5

Re: Обхід найменшого многокутника на системі координат

Chemist-i,
Можна більш детально