единственное что приходит в голову при визуализайии задачи...27.06.05 03:27 Число просмотров: 1539 Автор: Tom_Pain Статус: Незарегистрированный пользователь
единственное что приходит в голову при визуализайии задачи -
перед перебором выяснить регион пространства которое занимает полигон
т.е. обхватывающий квадрат (или куб) в который этот полигон вписан.
сделать это можно пройдясь по вершинам полигона и собрав минимальные&максимальные значения по x,y,(z?)
а далее такой же алгоритм как был описан но только для тех сегментов полилинии которые не попадаю явно в "свободные полупространствы" ))) их (полупространста).
блин ну вобщем нарисовать надо... тогда понятней станет )
если например обе ординаты обеих точек сегмента полилинии меньше заветного минимума то искать пересечение ее со всеми сегментами полигона не нужно и т.д.
проверки получатся не слишком сложные.
тут скорее вопрос насколько сложен среднестатистический полигон/полилиния в твоей задаче - если объекты будут сложные, то имеет смысл делать то что я предлагаю, а в противном случае- наверное не нужно...
короче "обрезание дерева перебора", только так, наверно...
Не знаю, куда добавть. Вот, добавил в этот раздел.
Необходимо получить точки пересечения полилинии PL с невыпуклым полигоном PG «без дыр».
В PL различают начальную и конечную точки, так что можно задать совокупность веторов, представленных сегментами PL.
Точки пересечения должны представлять полилинию PL_INT, каждый сегмент которой является вектором, коллинеарным вектору сегмента исходной полилинии PL.
Разумеется хочется красивый алгоритм. Пока сделал так:
Цикл “А” по всем сегментам исходной полилинии PL:
1. Получить сегмент PL(i) полилинии PL (в начале цикла, очевидно первый сегмент PL(0)).
Цикл “B” по всем сегментам полигона PG:
2. Получить сегмент PG(j)
3. Проверить пересечение PG(j) c PL(i).
4. Если пересечение сушествует, то добавить точку
массив точек пересечения текущего сегмента PLPG(i).
5. Сортировать массив PLPG(i) по значению растояния точек
oт начала сегмента PL(i)
6. Добавить все точки массива PLPG(i) в результирующий
Массив PLPG
7. Конец цикла “B”
8. Конец цикла “A”
Спасибо.
А почему бы не использовать геометрические формулы плоскости и прямой в трехмерном базисе?27.06.05 16:42 Автор: Den <Денис Т.> Статус: The Elderman
Полигон - 2D (проекциия реального 3D полигона), z=0. Соответственно и пересекающая полилиния - 2D.
>>А почему бы не использовать геометрические формулы плоскости и прямой в трехмерном базисе?
Что имеешь в виду и как это поможет получить более красивый алгоритм? Задача в том, чтобы все точки пересечения, ну, как бы (очень грубо с математической точки зрения) посторяли "путь" заданный векторами исходной полилинии. Т.е.
1) точки пересечения принадлежат отрезкам, составляющим полилинию ( как иначе, если это точки пересечения ;) )
2) ветора, сотставленные из точек пересечений, взятых в их естественном порядке следования в результирующем массиве - коллинеарны соответсвующим векторам сегментов полилиний.
единственное что приходит в голову при визуализайии задачи...27.06.05 03:27 Автор: Tom_Pain Статус: Незарегистрированный пользователь
единственное что приходит в голову при визуализайии задачи -
перед перебором выяснить регион пространства которое занимает полигон
т.е. обхватывающий квадрат (или куб) в который этот полигон вписан.
сделать это можно пройдясь по вершинам полигона и собрав минимальные&максимальные значения по x,y,(z?)
а далее такой же алгоритм как был описан но только для тех сегментов полилинии которые не попадаю явно в "свободные полупространствы" ))) их (полупространста).
блин ну вобщем нарисовать надо... тогда понятней станет )
если например обе ординаты обеих точек сегмента полилинии меньше заветного минимума то искать пересечение ее со всеми сегментами полигона не нужно и т.д.
проверки получатся не слишком сложные.
тут скорее вопрос насколько сложен среднестатистический полигон/полилиния в твоей задаче - если объекты будут сложные, то имеет смысл делать то что я предлагаю, а в противном случае- наверное не нужно...
короче "обрезание дерева перебора", только так, наверно...
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
