Упорядочение массива точек

[Tonny_Bennet]

Здравствуйте. Имеем некоторый массив точек Point(float x, float y) (в примере ниже из 16 элементов). Фактически это координаты вершин некоторых правильных фигур, вложенных друг в друга. Мне нужно программно определять попадает ли пробная точка внутрь области, содержащей точки (внешнего многоугольника).

http://s11.radikal.ru/i183/1109/a0/ee7faf70ce4e.png

В предыдущей теме я пытался найти метод определения принадлежности точки области. Нашёл при помощи создания Path: создаём Path используя массив точек и при помощи метода IsVisible() узнаём принадлежит ли наша пробная точка области.

Сейчас трудность заключается в том, что массив из точек не упорядочен. В предыдущей теме я грубо задавал эти точки вбивая координаты вершин восьмиугольника руками, по часовой стрелке, например. Сейчас же набор точек из 16 элементов считается программой и может быть совершенно произволен. Если их соединить то получается не совсем то что нужно!

http://s59.radikal.ru/i165/1109/7d/d0cb2f55cfa5.png

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

Какие будут предложения?

[Iska]

Сейчас трудность заключается в том, что массив из точек не упорядочен. »
Это как?

[lxa85]

Tonny_Bennet, сейчас попробую аккуратно объяснить мысль...
дело в том, что приведенный первый рисунок описывает именно ту "страшную" фигуру, которая и получилась. Т.е. предположение о том, что это два правильных 8 угольника - неверно. Фактически это координаты вершин некоторых правильных фигур, вложенных друг в друга. » Вот на этом этапе, утверждая, что фигуры правильные, мы накладываем ограничение на то, что координаты носят упорядоченный характер. Т.е. что ABCD - это квадрат, а ABCDEF - 6 угольник.

Есть мой любимый школьный пример про треугольники.
Например, есть треугольник ABC (см. картинку) он не равен треугольнику СВА, не смотря на то, что с виду они похожи.
Равенство треугольников приводит к равенствам сторон AB = CB, BC = BA, CA = AC. Так же из равенства треугольников следует равенство углов CAB = ACB, ABC = CBA, BCA = BAC, неравенство которых, при заданном треугольнике, должно развеять все сомнения.

Возвращаясь к заданию. Если мы говорим, что нам даны правильные фигуры, то массив точек описывающих фигуру автоматически, по законам геометрии, упорядочен.

[Beyound]

lxa85 - пожайлуства еще раз сформулируй свою детскую задачку, или рисунок. просто треугольники у тебя равнобедренные с вершиной B и одинаковы, поэтому что ABC или CBA его назвать - одно и тоже. они равны.

а на счет вопроса по теме. да - при составлении фигуры надо указывать точки с порядке их примыкания друг к другу. т.е. нельзя указать как на битом рисунке 4-5-6-7 и т.д. он их и соединит построив поверхность. Есть тривиальное но неоптимальное решение, которое годится для относительно небольшого объема точек - это для полной выборки из всех точек трех строить поверхности и потом эту поверхность объеденить. Но это работает только для выпуклой фигуры, т.е. скажем звезду так не построить. более сложный - это упорядочивать точки. для правильной фигуры это достаточно просто - выбираешь первую точку, к ней перебираешь все точки находя длинну до них в 2-хмерной плоскости по координатам точек и из 2-х самых маленьких выбираешь произвольно любую, далее для найденной 2-ой точки делаешь абсолютно тоже самое, только исключив первую точку из списка перебора, самой маленькой длинны будет всего одна. и так далее. главное учти - поиск длинны должен быть в double а то могут быть пробемы

[lxa85]

Beyound, пожайлуства еще раз сформулируй свою детскую задачку, или рисунок. »
Вот как то так. За основу взять прямоугольный треугольник, выполнено наложение треугольников с сопоставлением порядка следования вершин.

[Tonny_Bennet]

Тему создавал ночью, после тяжёлого учебного дня, непростого рабочего дня и тренировки по волейболу. А потом ещё кодил это дело.... видно совсем устал тогда.

Сейчас попробую сформулировать задачу иначе:

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

Т.е. если рассматривать первый рисунок то на выходе я должен получить массив такого вида: 2, 10, 11, 9, 13, 5, 4, 6. Ну или подобный, сдвинутый на любое количество позиций.

Проводя мозговой штурм с единомышленниками-алгоритмизаторами пришли в такой идее:

Последовательно выбирая точки: от трёх до N, соединять их и получать фигуру. И проверять попадают ли точки из набора внутрь этой фигуры. Если хоть одна не попала - переходить к следующей фигуре, пока мы не найдём фигуру, внутрь которой попадают все точки набора. Это и будет фигура, ограничивающая весь набор.

Пока запрограммировать было некогда. Видно что алгоритм затратный в смысле процессорного времени. Но лучше пока ничего не придумал.

[ferget]

это (http://algolist.manual.ru/maths/geom/convhull/) посмотрите

[Tonny_Bennet]

ferget, спасибо. Gift wrapping - достаточно понятный и не сложный алгоритм. Попробую изобразить.