Слияние массивов

← →
NickName (2010-12-07 11:58) [0]

Доброго времени суток. Имеется два массива с точками окружности элипса, ну или другой произвольной фигуры, но для начала пока элипс. Необходимо слить эти два массива в один, при этом исключить все точки попавшие на плоскости совмещаемых элипсов.
Скриншот для полной понятности моей "хотелки":
http://s47.radikal.ru/i116/1012/3e/06b16d869909.jpg

Буду благодарен за любые объяснения ну или пинок в нужную сторону раскопок :)

← →
Юрий Зотов © (2010-12-07 12:08) [1]

Если возможно аналитически определить абсциссу точек пересечения эллипсов, то из массива 1 выбрасываются все точки, лежащие левее, а из массива 2 выбрасываются все точки, лежащие левее.

← →
Юрий Зотов © (2010-12-07 12:09) [2]

Последнее слово - правее, а не левее.

← →
NickName (2010-12-07 12:10) [3]

Да, окружности так и идут точками как на рисунке, т.е. не сплошная линия, а только наметки для полигона. Но при надобности массивы можно и "допилить" до кондиции Брезенхемом, но не хотелось бы, ибо большая затратность, получится, по времени выволнения...

← →
Кщд (2010-12-07 12:35) [4]

Для каждой точки 1-го массива(b):
1. находим ближайшую из 2-го. назовем её a1;
2. берем ближайшую к а1 слева(а0) и справа(а2), строим векторы A1(а1, а0), A2(а1, а2), B(а0, b);
3. если векторные произведения: A1xB, BxA2, AxB, - одного знака, "стираем" с рисунка точку b.

Повторяем для массива №2.

← →
Кщд (2010-12-07 12:36) [5]

поправка
п.2 читать как:
2. берем ближайшую к а1 слева(а0) и справа(а2), строим векторы A1(а1, а0), A2(а1, а2), B(а1, b);

← →
12 © (2010-12-07 12:38) [6]

тупо
http://msdn.microsoft.com/en-us/library/dd162883%28VS.85%29.aspx

← →
NickName (2010-12-07 12:47) [7]

> 12 © (07.12.10 12:38) [6]

неее выньапи не пойдет

> Кщд (07.12.10 12:35) [4]

ща попробую прикинуть

пока проверяю эту формулу

http://dxdy.ru/math/5d2f2e51273cd661425efc7e1e566cde82.gif

← →
NickName (2010-12-07 12:47) [8]

отсюда
http://dxdy.ru/topic8441.html

← →
Юрий Зотов © (2010-12-07 12:59) [9]

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

← →
12 © (2010-12-07 13:03) [10]

во..

http://zalil.ru/30093518
И выкидываем точки с координатами из красного из обоих фигур

или нет?

← →
NickName (2010-12-07 13:18) [11]

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

т.е. находить все точки плоскости (что собсно не проблема), например в массиве один и исключать из них окружность массива два, затем наоборот. Так?

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

Может можете посоветовать что-нить более оптимальное?

← →
NickName (2010-12-07 13:33) [12]

> 12 © (07.12.10 13:03) [10]
> во..http://zalil.ru/30093518И выкидываем точки с координатами
> из красного из обоих фигурили нет?

э не ;) расположив под другим углом очистятся нужные точки

← →
han_malign (2010-12-07 14:29) [13]

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

> затем эллипсы сливаем в единную кривую исключая лишние точки

- общие касательные не проще посчитать?

← →
NickName (2010-12-07 15:01) [14]

> - общие касательные не проще посчитать?

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

> Через треугольники (есть такой алгоритм построения такой
> линии) - это, я как понял, недостижимо.

← →
MBo © (2010-12-07 15:08) [15]

Это построение НЕвыпуклой оболочки множества точек.
Для выпуклых оболочек (convex hull) алгоритмы хорошо известны.
Для невыпуклых задачи могут быть решаемы в конкретных случаях (для выпуклой оболочки есть абсолютно четкие критерии, какие из точек должны принадлежать оболочек, а для невыпуклой они могут быть умозрительными ("некрасиво" и т.п.) ).
Собственно, проблема сводится к формализации критериев принадлежности.

← →
Юрий Зотов © (2010-12-07 15:53) [16]

> NickName (07.12.10 13:18) [11]
> т.е. находить все точки плоскости (что собсно не проблема),
> например в массиве один и исключать из них окружность массива
> два, затем наоборот. Так?

Посмотрите в справке WinAPI раздел "region functions".

Создаем по точкам каждого массива регион. Потом, комбинируя эти 2 региона, создаем регион их общей области и из обоих массивов исключаем точки, попадающие в этот регион.

← →
NickName (2010-12-07 16:52) [17]

Не, WinAPI нельзя юзать, только ручками. ибо кроссплатформ...

← →
NickName (2010-12-07 16:53) [18]

Так бы проблем небыло...

Посмотрите FastGeo - там много чего есть.

← →
NickName (2010-12-07 23:17) [20]

> Посмотрите FastGeo - там много чего есть.

Какая интересная штука, с удовольствием покавыряю.
Спасибо!

> FastGeo
> ...
> ..интересная штука

Действительно - по уму сделана.
Кратко, изящно, понятно и достаточно эффективно.

← →
NickName (2010-12-09 08:20) [22]

Похоже линия получилась. Делал так:
На начальных и конечных координатах утолщамой линии формируем круги с центром на координатах линии, затем из окружности путем перебора точек выбираем ту точку которая дает самый точный перпендикуляр на центр круга, относительно линии. Затем разворачиваем эту точку на 180 градусов относительно центра круга и вуаля, получили четыре точки для пропроброса касательных на окружность кругов :)

юзал две функции из FastGeo, покрайне мере одну, вторая похоже какаята производная из них (нашел на просторах тернета)

← →
NickName (2010-12-18 11:51) [23]

Модифицировал.
Формируем один круг, получаем перпендикуляр, разворачиваем на 180 градусов - получаем вторую точку, переносим эти точки относительно второго конца отрезка - получаем вторые две точки. Итого есть касательные. Так же добавил закругление концов линии. Короче получил полноправный полигон, для заливки, например, построчным методом заполнения полигонов.
Теперь задача: избавиться от круга и соответственно перебора в поисках перпендикуляра.
Т.е имеем отрезок, одна из координат отрезка лежит в центре круга, имеем радиус круга, как математически получить точку из окружности, которая дает перепендикуляр на центр круга, относительно отрезка. Вещественые типы юзать можно.

← →
NickName (2010-12-23 08:31) [24]

Ну собсно я получил все, что хотел. Прошу прокоментировать алгоритм/код. Там немного...

Демка D7
http://ifolder.ru/20972059

Слияние массивов Найти похожие ветки