Поиск треугольника в триангулированной области - Алгоритмы

Здравствуйте, Cruelty, Вы писали:

C>Буду благодарен за любые идеи!
Есть алгоритм "с динамическим/статическим кешем поиска", там как раз сетка (кеш) используется для поиска одного из ближних треугольников. Далее по связям треугольников в трианг-ии ищется нужный, путем последовательных перескоков. Работает способ "быстро". Когда я тестил на большенстве примерно рандомно расположеных точках трианг-ии, то каждая новая точка добавлялась за const время, не зависимо от числа уже добавленных точек (порядка 10млн. точек было), в итоге O(N) в среднем, а поиск треугольника соответственно за const. Деревья так быстро не работают наверно

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, michus, Вы писали:

M>>Для этого надо выполнить условия:
M>>1. пустые области оформить в виде выпуклых многоугольников с направлением обхода аналогичным треугольникам
FM>По идее, можно выкидывать из рассмотрения те стороны треугольников, которые граничат с дырами.

Этого делать как раз и не надо, т.к. это приводит к преждевременной остановке поиска. Дыры в триангуляции надо заштопывать или, по крайней мере, проверять на попадение точки в дырку, если произойдёт переход в неё из триангуляции. ИМХО проще заштопать, т.к. если точка не в дырке, то прийдётся рестартовать поиск (маркер при этом не изменять) с треугольника, лежащего по другую сторону от треугольника входа в дырку. Ещё один неприятный момент — невыпуклость границы триангуляции, что тоже приводит к преждевременному останову.

M>>2. ввести маркировку пройденных треугольников/многоугольников и не давать переходить на уже помеченные просто пропуская переход
FM>Почти поиск на графе получается. В глубину. С эвристикой.

Возврата только нет.

Маркировка нужна для предотвращения зацикливания метода поиска на триангуляциях, не удовлетворяющих условиям Делоне.

FM>Соответственно, есть подозрение, что алгоритм в некоторых случаях может работать некорректно.
FM>Пример ячейки грида.
FM>Текущее положение при поиске — нижний треугольник.
FM>Красным цветом обозначена точка, для которой ищем треугольник. В соответствии с алгоритмом, движемся вверх.
FM>Можно будет попасть внутрь подковы, а обратно уже нельзя, потому что треугольники будут маркированы, как пройденные.
FM>

Для предотвращения такого случая "дырку" надо заштопывать.

FM>Еще один случай (развитие предыдущего), когда может не получится найти нужный треугольник последовательными переходами от произвольно выбранного — при наличии разрывов у триангуляции.

Общий подход можно рекомендовать такой:
Имея любую триангуляцию надо проверить на выпуклость границы и если её нет — достроить до выпуклой. Если есть дыры, т.е. рёбра не лежащие на границе с одной из сторон не имеют треугольника, то их тоже надо заштопывать. При этом, если дыра выпуклая, то можно просто вставить в неё полигон, если не выпуклая, то надо её триангулировать. Способ триангуляции — любой, т.к. главная цель — получить выпуклые полигоны.
Т.к. в общем случае триангуляция получится не удовлетворяющая условиям Делоне, то во время поиска надо применять маркировку.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, Cruelty, Вы писали:

C>Пока единственное что приходит на ум -- ето покрыть область гридом и в каждой ячейке хранить индексы треугольников, которые пересекают её. Когда надо найти треугольник, то вначеле надо найти ячейку, а потом проверить все её треугольники. Но такой подход кажется все-таки не оптимальным ни в терминах памяти ни в терминах производительности.
Откуда подозрения?

Когда сам реализовывал подобный способ, работало все очень шустро.
Если хочется выбирать, то в качестве альтернативы можно предложить дерево.
(Близкая задача http://gzip.rsdn.ru/forum/?mid=564551)

Здравствуйте, FreshMeat, Вы писали:

FM>Интересно. Как выбирается направления перескока?
Можно искать какое ребро пересекает отрезок, идущий от i-й вершины треугольника до заданной точки. Для каждой из трех вершин ищем пересечение ребра и отрезка — одна из них, где отрезок пересечет ребро, и будет следующим шагом (два другие ребра отрезок не пересечет).

Но я делал иначе. Правда у меня дырок в триангуляции не было.
Имеем нашу точку, попадание которой в триангуляцию ищем (x0,y0)
Вычисляем вот это:

s[0] = (x2-x1)*(y0-y1) - (y2-y1)*(x0-x1)
s[1] = (x3-x2)*(y0-y2) - (y3-y2)*(x0-x2)
s[2] = (x1-x3)*(y0-y3) - (y1-y3)*(x0-x3)
//где A(x1,y1), B(x2,y2), C(x3,y3) - точки текущего треугольника, взятые по ч.с.

Эти числа нужны для проверки попадания точки в треугольник или в i-е ребро.
Условия попаданий такие:

(s[0]<0) && (s[1]<0) && (s[2]<0) //точка внутри треугольника
(s[i]=0) && (s[j]<0) && (s[k]<0) //точка на i-ом ребре (j, k - индексы двух других ребер)

Если ни одно условие не выполняется, то нужен скачок к следующему смежному треугольнику:

— если среди s есть одно, которое >0, то в этом направлении и идем (индекс этой s — и есть наше направление);
— если два значения s[i], [j] оба >0, то выбираем то направление, где значение s больше.

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, piAnd, Вы писали:

A>>Есть алгоритм "с динамическим/статическим кешем поиска", там как раз сетка (кеш) используется для поиска одного из ближних треугольников. Далее по связям треугольников в трианг-ии ищется нужный, путем последовательных перескоков. Работает способ "быстро". ...
FM>Интересно. Как выбирается направления перескока?

Можно сделать, например так:

// Поиск треугольника, содержащего точку. Если такового нет, то возвращается NULL.
SNetTriangle * FindTriangle (STriangle * _pFirst, double _x, double _y) {
    // ПРИМЕЧАНИЕ: Предполагается отрицательное направление всех треугольников.
    while (_pFirst) {
        // Найти ребро для приближения к точке.
        if (Orientation (_pFirst->Points [0]->x, _pFirst->Points [0]->y, _pFirst->Points [1]->x, _pFirst->Points [1]->y, _x, _y) > 0)
            _pFirst = _pFirst->Triangles [2];
        else if (Orientation (_pFirst->Points [1]->x, _pFirst->Points [1]->y, _pFirst->Points [2]->x, _pFirst->Points [2]->y, _x, _y) > 0)
            _pFirst = _pFirst->Triangles [0];
        else if (Orientation (_pFirst->Points [2]->x, _pFirst->Points [2]->y, _pFirst->Points [0]->x, _pFirst->Points [0]->y, _x, _y) > 0)
            _pFirst = _pFirst->Triangles [1];
        else
            return _pFirst;
    }
    return NULL;
}

inline int Orientation (double _x1, double _y1, double _x2, double _y2, double _x3, double _y3) {
    const double s = (_x2 - _x1) * (_y3 - _y1) - (_x3 - _x1) * (_y2 - _y1);
    return s > 0.0 ? 1 : (s < 0.0 ? -1 : 0);
}

Где Points [] — указатели на вершины, Triangles [] — указатели на соседей.
При этом, 0-му соседнему треугольнику противостоит 0-ая вершина.

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Есть нерегулярная триангуляция плоской области произвольной формы с произвольным количеством дырок опять таки произвольной формы. Она задана массивом точек (углов треугольников) и массивом треугольников (каждый из которых содержит три индекса образуюсчих точек). Их менять нельзя (либо надо иметь очень весомые аргументы).

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

Треугольников много и искать надо часто. Как ето сделать побыстрее?

Пока единственное что приходит на ум -- ето покрыть область гридом и в каждой ячейке хранить индексы треугольников, которые пересекают её. Когда надо найти треугольник, то вначеле надо найти ячейку, а потом проверить все её треугольники. Но такой подход кажется все-таки не оптимальным ни в терминах памяти ни в терминах производительности.

Буду благодарен за любые идеи!

Здравствуйте, Cruelty, Вы писали:

C>На плоскость бросается точка. Надо быстро определить к какому треугольнику она принадлежит или сказать, что она вне области.

При построении триангуляции отрисовывать вспомогательную картинку, каждый треугольник — своим цветом
Дальше просто GetPixel

Здравствуйте, MBo, Вы писали:

MBo>При построении триангуляции отрисовывать вспомогательную картинку, каждый треугольник — своим цветом
MBo>Дальше просто GetPixel

Это очень интересная идея, но для получения приемлимой погрешности потребуется хранить огромные картинки из многих гигабайт (если использовать битмапку с 32 битным цветом, для использования цвета как индекса треугольника). Как правило триангулируемая область занимает как минимум 25% описывающего ее прямоугольника, так что даже хитрое разбиение на многих картинок предьявляет невыполнимые требования к памяти

Здравствуйте, piAnd, Вы писали:

A>Здравствуйте, Cruelty, Вы писали:

C>>Буду благодарен за любые идеи!
A>Есть алгоритм "с динамическим/статическим кешем поиска", там как раз сетка (кеш) используется для поиска одного из ближних треугольников. Далее по связям треугольников в трианг-ии ищется нужный, путем последовательных перескоков. Работает способ "быстро". Когда я тестил на большенстве примерно рандомно расположеных точках трианг-ии, то каждая новая точка добавлялась за const время, не зависимо от числа уже добавленных точек (порядка 10млн. точек было), в итоге O(N) в среднем, а поиск треугольника соответственно за const. Деревья так быстро не работают наверно

Перескоки, к сожалению не заработают из-за дырок, а вот на сам алгоритм очень хотелось бы взглянуть. Вот только я не смог найти ни в гугле ни в яндексе ссылок на такой алгоритм (либо даже с похожим названием). Можно ли уточнить название? Или еще лучше ссылку на описание алгоритма (желательно на английском)

Здравствуйте, Cruelty, Вы писали:

C>Перескоки, к сожалению не заработают из-за дырок, а вот на сам алгоритм очень хотелось бы взглянуть. Вот только я не смог найти ни в гугле ни в яндексе ссылок на такой алгоритм (либо даже с похожим названием). Можно ли уточнить название? Или еще лучше ссылку на описание алгоритма (желательно на английском)
здесь

Здравствуйте, piAnd, Вы писали:

A>Есть алгоритм "с динамическим/статическим кешем поиска", там как раз сетка (кеш) используется для поиска одного из ближних треугольников. Далее по связям треугольников в трианг-ии ищется нужный, путем последовательных перескоков. Работает способ "быстро". Когда я тестил на большенстве примерно рандомно расположеных точках трианг-ии, то каждая новая точка добавлялась за const время, не зависимо от числа уже добавленных точек (порядка 10млн. точек было), в итоге O(N) в среднем, а поиск треугольника соответственно за const. Деревья так быстро не работают наверно

1. Смотря какие деревья, а то есть и деревья триангуляций

2. Оценка поиска треугольника переходами через ребро, отсекающее искомую точку от противоположной вершины треугольника — O(N^1/3) кеширование что-то улучшить может, но врят ли сильно, особенно в процессе построения триангуляции. На малых (~ 10^5) триангуляциях его поддержание, ИМХО, дороже будет. Т.е. меняем C на O(.). С 10^7 точек не работал на таких объёмах — не знаю

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, michus, Вы писали:

M>1. Смотря какие деревья, а то есть и деревья триангуляций

M>2. Оценка поиска треугольника переходами через ребро, отсекающее искомую точку от противоположной вершины треугольника — O(N^1/3) кеширование что-то улучшить может, но врят ли сильно, особенно в процессе построения триангуляции. На малых (~ 10^5) триангуляциях его поддержание, ИМХО, дороже будет. Т.е. меняем C на O(.). С 10^7 точек не работал на таких объёмах — не знаю

.

При псевдо-случайном разбросе точек в каждый элемент кеша попадает примерно const треугольников, поэтому переходов тоже примерно const, т.е. в таком случае (рандомном) получается именно const время поиска треугольника. Строил график скорости (причем полный на все операции, включая флип и перестройку структуры), и получил примерно линейный рост. До 10млн точек. М/б это const не очень маленькое, но тенденция прослеживается точно. Ну... это собственно и было заявлено тем, кто придумал алгоритм

Здравствуйте, piAnd, Вы писали:

A>Здравствуйте, michus, Вы писали:

M>>1. Смотря какие деревья, а то есть и деревья триангуляций

M>>2. Оценка поиска треугольника переходами через ребро, отсекающее искомую точку от противоположной вершины треугольника — O(N^1/3) кеширование что-то улучшить может, но врят ли сильно, особенно в процессе построения триангуляции. На малых (~ 10^5) триангуляциях его поддержание, ИМХО, дороже будет. Т.е. меняем C на O(.). С 10^7 точек не работал на таких объёмах — не знаю

.

A>При псевдо-случайном разбросе точек в каждый элемент кеша попадает примерно const треугольников, поэтому переходов тоже примерно const, т.е. в таком случае (рандомном) получается именно const время поиска треугольника. Строил график скорости (причем полный на все операции, включая флип и перестройку структуры), и получил примерно линейный рост. До 10млн точек. М/б это const не очень маленькое, но тенденция прослеживается точно. Ну... это собственно и было заявлено тем, кто придумал алгоритм

А сам кеш дорого обходился и был ли рост области охваченной триангуляцией во время работы ?

... << RSDN@Home 1.1.4 stable SR1 rev. 568>>

Здравствуйте, piAnd, Вы писали:

A>Здравствуйте, FreshMeat, Вы писали:

FM>>Интересно. Как выбирается направления перескока?
A>Можно искать какое ребро пересекает отрезок, идущий от i-й вершины треугольника до заданной точки. Для каждой из трех вершин ищем пересечение ребра и отрезка — одна из них, где отрезок пересечет ребро, и будет следующим шагом (два другие ребра отрезок не пересечет).

A>Но я делал иначе.
Понятно — ненадежный способ.

A>- если среди s есть одно, которое >0, то в этом направлении и идем (индекс этой s — и есть наше направление);
A>- если два значения s[i], [j] оба >0, то выбираем то направление, где значение s больше.
Ага, примерно что-то такое и ожидал. Спасибо.

Здравствуйте, michus, Вы писали:

FM>>Как выбирается направления перескока?

M>Можно сделать, например так:
<>
M>Где Points [] — указатели на вершины, Triangles [] — указатели на соседей.
M>При этом, 0-му соседнему треугольнику противостоит 0-ая вершина.
Если правильно понимаю, это решение аналогичное, предложенному piAnd здесь?

Здравствуйте, michus, Вы писали:

M>А сам кеш дорого обходился и был ли рост области охваченной триангуляцией во время работы ?
1. по теории размер кеша рекомендуется такой --- (2^N) x (2^N), где N = (NN^2)/k, где NN общее число точек, k выбирается ~ 3...8. Вобщем как-то так... Забыл точную величину. На практике можно ограничивать его размер до любого, в итоге получится просто падение скорости.

Короче про кеш — тут есть возможность его модифицировать (сделать деревом

и т.д.) для разных исходных точек — рандом или другое распределение. Потом данной задачей я буду заниматься.

2. Область одна — суперструктура. Делал так, чтоб не искать выпуклую оболочку.

Здравствуйте, FreshMeat, Вы писали:

FM>Здравствуйте, michus, Вы писали:

FM>>>Как выбирается направления перескока?

M>>Можно сделать, например так:
FM><>
M>>Где Points [] — указатели на вершины, Triangles [] — указатели на соседей.
M>>При этом, 0-му соседнему треугольнику противостоит 0-ая вершина.
FM>Если правильно понимаю, это решение аналогичное, предложенному piAnd здесь?

Общий подход — аналогичен, но в качестве оптимизации используется строгая одинаковость направлений обхода треугольников. Это позволяет сразу выбирать рёбра, через которые надо идти не вычисляя направления для всех. Что сокращает среднее время поиска в 1.5 раза.

Приведённый метод можно использовать и в триангуляции общего вида (и с пустыми областями тоже)

Для этого надо выполнить условия:
1. пустые области оформить в виде выпуклых многоугольников с направлением обхода аналогичным треугольникам
2. ввести маркировку пройденных треугольников/многоугольников и не давать переходить на уже помеченные просто пропуская переход

Напрмер так:

...
while (_pFirst) {
    _pFirst->SerachMarker = _SearchId;

    int i;
    for (i = 0; i < _pFirst->cEdges; ++ i) {
        // Подразумевается дублирование координат первой точки в последней. Т.е. для N-угольника N+1 координат точек.
        if (
            Orientation (_pFirst->Points [i]->x, _pFirst->Points [i]->y, _pFirst->Points [i+1]->x, _pFirst->Points [i+1]->y, _x, _y) > 0
         && _pFirst->Object [i]->SerachMarker != _SearchId
        ) {
            _pFirst = _pFirst->Object [i];
            break;
        }
    }

    if (i != _pFirst->cEdges)
        return _pFirst;
}
...

где SearchMarker — поле для хранения маркера, _SearchId — номер текущего поиска увеличивается при каждом поиске.

Опечатка: (!=) вместо (==)

M>...
M>    if (i == _pFirst->cEdges)
M>        return _pFirst;
M>...

Здравствуйте, michus, Вы писали:

M>Общий подход — аналогичен, но в качестве оптимизации используется строгая одинаковость направлений обхода треугольников. Это позволяет сразу выбирать рёбра, через которые надо идти не вычисляя направления для всех. Что сокращает среднее время поиска в 1.5 раза.
Любопытно. А на первый взгляд действие не выглядит способным дать такой прирост производительности

M>Для этого надо выполнить условия:
M>1. пустые области оформить в виде выпуклых многоугольников с направлением обхода аналогичным треугольникам
По идее, можно выкидывать из рассмотрения те стороны треугольников, которые граничат с дырами.
M>2. ввести маркировку пройденных треугольников/многоугольников и не давать переходить на уже помеченные просто пропуская переход
Почти поиск на графе получается. В глубину. С эвристикой.

Соответственно, есть подозрение, что алгоритм в некоторых случаях может работать некорректно.
Пример ячейки грида.
Текущее положение при поиске — нижний треугольник.
Красным цветом обозначена точка, для которой ищем треугольник. В соответствии с алгоритмом, движемся вверх.
Можно будет попасть внутрь подковы, а обратно уже нельзя, потому что треугольники будут маркированы, как пройденные.

Еще один случай (развитие предыдущего), когда может не получится найти нужный треугольник последовательными переходами от произвольно выбранного — при наличии разрывов у триангуляции.

	От:	piAnd
	Дата:	04.05.06 12:36
	Оценка:	12 (2)

	От:	michus
	Дата:	06.05.06 20:22
	Оценка:	7 (1)

От:	FreshMeat	http://www.rsdn.org
Дата:	04.05.06 10:11
Оценка:	6 (1)

	От:	piAnd
	Дата:	04.05.06 14:20
	Оценка:	6 (1)

	От:	michus
	Дата:	04.05.06 17:24
	Оценка:	6 (1)