информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Где водятся OGRыСетевые кракеры и правда о деле ЛевинаЗа кого нас держат?
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Очередной юбилей Linux 
 HP закрыла 16-летнюю уязвимость... 
 Microsoft советует пользователям... 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / miscellaneous
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
Полигон - 2D (проекциия реального 3D полигона), z=0... 28.06.05 22:59  Число просмотров: 1331
Автор: void <Grebnev Valery> Статус: Elderman
<"чистая" ссылка>
Полигон - 2D (проекциия реального 3D полигона), z=0. Соответственно и пересекающая полилиния - 2D.

>>А почему бы не использовать геометрические формулы плоскости и прямой в трехмерном базисе?

Что имеешь в виду и как это поможет получить более красивый алгоритм? Задача в том, чтобы все точки пересечения, ну, как бы (очень грубо с математической точки зрения) посторяли "путь" заданный векторами исходной полилинии. Т.е.

1) точки пересечения принадлежат отрезкам, составляющим полилинию ( как иначе, если это точки пересечения ;) )

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

<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?)


а далее такой же алгоритм как был описан но только для тех сегментов полилинии которые не попадаю явно в "свободные полупространствы" ))) их (полупространста).

блин ну вобщем нарисовать надо... тогда понятней станет )

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

проверки получатся не слишком сложные.

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

короче "обрезание дерева перебора", только так, наверно...
1






Rambler's Top100
Рейтинг@Mail.ru


  Copyright © 2001-2021 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach