информационная безопасность
без паники и всерьез
 подробно о проектеRambler's Top100
Портрет посетителяВсе любят медСтрашный баг в Windows
BugTraq.Ru
Русский BugTraq
 Анализ криптографических сетевых... 
 Модель надежности двухузлового... 
 Специальные марковские модели надежности... 
 Три миллиона электронных замков... 
 Doom на газонокосилках 
 Умер Никлаус Вирт 
главная обзор RSN блог библиотека закон бред форум dnet о проекте
bugtraq.ru / форум / miscellaneous
Имя Пароль
ФОРУМ
если вы видите этот текст, отключите в настройках форума использование JavaScript
регистрация





Легенда:
  новое сообщение
  закрытая нитка
  новое сообщение
  в закрытой нитке
  старое сообщение
  • Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
  • Новичкам также крайне полезно ознакомиться с данным документом.
А почему бы не использовать геометрические формулы плоскости и прямой в трехмерном базисе? 27.06.05 16:42  Число просмотров: 2503
Автор: Den <Denis> Статус: The Elderman
<"чистая" ссылка>
<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-2024 Dmitry Leonov   Page build time: 0 s   Design: Vadim Derkach