Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
|
единственное что приходит в голову при визуализайии задачи... 27.06.05 03:27 Число просмотров: 1418
Автор: Tom_Pain Статус: Незарегистрированный пользователь
|
единственное что приходит в голову при визуализайии задачи -
перед перебором выяснить регион пространства которое занимает полигон
т.е. обхватывающий квадрат (или куб) в который этот полигон вписан.
сделать это можно пройдясь по вершинам полигона и собрав минимальные&максимальные значения по x,y,(z?)
а далее такой же алгоритм как был описан но только для тех сегментов полилинии которые не попадаю явно в "свободные полупространствы" ))) их (полупространста).
блин ну вобщем нарисовать надо... тогда понятней станет )
если например обе ординаты обеих точек сегмента полилинии меньше заветного минимума то искать пересечение ее со всеми сегментами полигона не нужно и т.д.
проверки получатся не слишком сложные.
тут скорее вопрос насколько сложен среднестатистический полигон/полилиния в твоей задаче - если объекты будут сложные, то имеет смысл делать то что я предлагаю, а в противном случае- наверное не нужно...
короче "обрезание дерева перебора", только так, наверно...
|
|
<miscellaneous>
|
Пересечение полилинии с полигоном 25.06.05 01:16
Автор: void <Grebnev Valery> Статус: Elderman
|
Не знаю, куда добавть. Вот, добавил в этот раздел.
Необходимо получить точки пересечения полилинии PL с невыпуклым полигоном PG «без дыр».
В PL различают начальную и конечную точки, так что можно задать совокупность веторов, представленных сегментами PL.
Точки пересечения должны представлять полилинию PL_INT, каждый сегмент которой является вектором, коллинеарным вектору сегмента исходной полилинии PL.
Разумеется хочется красивый алгоритм. Пока сделал так:
PLPG – массив искомых точек пересечения (вершины PL_INT)
Цикл “А” по всем сегментам исходной полилинии 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 <Denis> Статус: The Elderman
|
|
|
| |
Полигон - 2D (проекциия реального 3D полигона), z=0... 28.06.05 22:59
Автор: void <Grebnev Valery> Статус: Elderman
|
Полигон - 2D (проекциия реального 3D полигона), z=0. Соответственно и пересекающая полилиния - 2D.
>>А почему бы не использовать геометрические формулы плоскости и прямой в трехмерном базисе?
Что имеешь в виду и как это поможет получить более красивый алгоритм? Задача в том, чтобы все точки пересечения, ну, как бы (очень грубо с математической точки зрения) посторяли "путь" заданный векторами исходной полилинии. Т.е.
1) точки пересечения принадлежат отрезкам, составляющим полилинию ( как иначе, если это точки пересечения ;) )
2) ветора, сотставленные из точек пересечений, взятых в их естественном порядке следования в результирующем массиве - коллинеарны соответсвующим векторам сегментов полилиний.
|
|
единственное что приходит в голову при визуализайии задачи... 27.06.05 03:27
Автор: Tom_Pain Статус: Незарегистрированный пользователь
|
единственное что приходит в голову при визуализайии задачи -
перед перебором выяснить регион пространства которое занимает полигон
т.е. обхватывающий квадрат (или куб) в который этот полигон вписан.
сделать это можно пройдясь по вершинам полигона и собрав минимальные&максимальные значения по x,y,(z?)
а далее такой же алгоритм как был описан но только для тех сегментов полилинии которые не попадаю явно в "свободные полупространствы" ))) их (полупространста).
блин ну вобщем нарисовать надо... тогда понятней станет )
если например обе ординаты обеих точек сегмента полилинии меньше заветного минимума то искать пересечение ее со всеми сегментами полигона не нужно и т.д.
проверки получатся не слишком сложные.
тут скорее вопрос насколько сложен среднестатистический полигон/полилиния в твоей задаче - если объекты будут сложные, то имеет смысл делать то что я предлагаю, а в противном случае- наверное не нужно...
короче "обрезание дерева перебора", только так, наверно...
|
|
|
подробно о проекте
Анализ криптографических сетевых... 
