Найти треугольник [решено]

[Igors]

Двумерный массив списков. Каждый список - номера треугольников (из nvtr), которые попадают в соответствующий прямоугольник. У меня сетка достаточно равномерная, так что в адаптивной прямоугольной сетке нужды не было. Если нужна адаптивная - например список списков. Первые k*p элементов символизируют первичную прямоугольную сетку. Если в этих элементах содержатся положительные числа - то это индексы из nvtr, если отрицательные - то это четыре элемента списка (с индексом больше чем k*p) являющиеся четырьмя прямоугольниками, на которые разбит первичный четырехугольник ну и дальше по рекурсии.

Я сам заядлый велосипедист, но здесь - не стоит, octree сильнее (и его не нужно будет бесконечно латать). У меня расчет начинается с облака точек, по ним я строю треугольники, поэтому дерево для поиска вертексов у меня по-любому есть. Строить еще одно дерево - жаба давит. Неужели нельзя обойтись одним? Давайте-ка подумаем, а то как что нешаблонное - так сразу уж и "неудобная структура данных" 

(Следующий параграф слабонервным лучше не читать)
Объем данных не фиксирован. Т.е. если получен отказ на malloc -  надо парить по частям. Так что сажать (кучерявые) деревья почем зря в мои планы не входит   

[pastor]

Т.е. если получен отказ на malloc

Под какую ось пишешь?

[alexman]

OcTree используется только для поиска вершин? Или еще для чего то? (Просто интересно)

[Blackwanderer]

У меня расчет начинается с облака точек, по ним я строю треугольники, поэтому дерево для поиска вертексов у меня по-любому есть.

А зачем вам дерево для поиска вертексов? У вас логическая единица задачи - треугольник.
Проблемы вашей структуры данных следующие:
1) Сборка треугольника из вертексов - это дополнительная подзадача, к тому же с кучей if-ов.
2) Понятие ближайшей точки субъективно. Что такое ближайшая точка?
Какие у вашей структуры данных преимущества?

[Igors]

Под какую ось пишешь?

OSX + (злополучное) Вындоуз

OcTree используется только для поиска вершин? Или еще для чего то? (Просто интересно)

А зачем вам дерево для поиска вертексов? У вас логическая единица задачи - треугольник.

Наоборот, треугольники в данном случае играют вспомогательную роль. Упрощенно: сначала создается облако вертексов, у каждого есть "зона захвата/влияния" которая многократно корректируется в процессе расчета. Если один вертекс влияет на другой - образуется ребро. Какие-то вертексы могут не иметь ребер, в каких-то (пусть редких) случаях треугольников может вообще не быть.

[alexman]

Igors, есть какое-то решение? Или хотите посмотреть варианты?

[Igors]

Igors, есть какое-то решение? Или хотите посмотреть варианты?

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

Задумка простая: сначала (предрасчет) для каждого вертекса рассортировать все выходящие из него ребра "по углу". Тогда треугольники будут (почти) готовы

[pastor]

OSX + (злополучное) Вындоуз

Чисто к сведению: на юникс-лайк системах malloc/new не всегда возвращает NULL (или генерит bad_alloc в случае new), а возвращает "корректный" адрес на участок памяти. При первом обращении к такому участку памяти получаем краш. Так что проверки на NULL, ловля bad_alloc, установка new handler бесполезны. Все это связано с memory overcommit.. Думаю будет полезно ознакомиться.

Сорри за оффтоп.

[Igors]

Чисто к сведению: на юникс-лайк системах malloc/new не всегда возвращает NULL (или генерит bad_alloc в случае new), а возвращает "корректный" адрес на участок памяти. При первом обращении к такому участку памяти получаем краш. Так что проверки на NULL, ловля bad_alloc, установка new handler бесполезны. Все это связано с memory overcommit.. Думаю будет полезно ознакомиться.

Это я для простоты так сказал "отказ malloc". На самом деле в этом проекте все выделения памяти перекрыты и NULL возвращается если общее кол-во выделенной памяти превысило предел заданный пользователем. Дальше начинается (довольно мучительное) выяснение какие данные снести на диск (чтобы затем опять подгрузить). Это я к тому что с деревьями особо не разогнаться.

Пастор, Вы стали много читать 

[Igors]

В общем сделал, все оказалось легко. Для каждого вертекса сортирую исходящие из него ребра по углу. На поиске просто перебираю ребра, каждое образует треугольник с предыдущим. Плюс 2 дополнительные проверки

- проверка угла между ребрами на < 180
- проверка "треугольник уже был рассмотрен". Реализовал незатейливым массивом и линейным просмотром