| Вопрос: Как на Visual Basic Script (.net) реализовать выбо | Добавлено: 22.06.10 17:43 |
Автор вопроса:  Юрий
|
| Допустим, надо выделить точки у которых окружение не менее 6 соседних точек. А те точки которые окружены, допустим лишь 4-мя соседними точками, не выделять. Может есть какие нибудь книжки с похожими примерами? Надеюсь на помощь)) |
| Ответы | Всего ответов: 13 |
|
Номер ответа: 1 Автор ответа:  s12 Вопросов: 24 Ответов: 363 |
Профиль | | #1 | Добавлено: 25.06.10 09:56 |
| Что-то у меня сегодня третий глаз барахлит. Речь о теории графов? | ||
|
Номер ответа: 2 Автор ответа: Юрий Вопросов: 3 Ответов: 30 |
Профиль | | #2 | Добавлено: 25.06.10 10:05 |
| Имеется облако точек, в пространстве (плоскости). Задача вообще - убрать все внутренние точки облака, оставив только периметр (границу). Для этого необходим алгоритм. Чтобы найти границу, можно сделать анализ окружения каждой точки в облаке. На границах точки окружены меньшим количеством соседних точек, нежели в объеме. Исходя из этого, можно вычесть "объем", оставив только "поверхность". Такие дела. | ||
|
Номер ответа: 3 Автор ответа: ЮрийВопросов: 3 Ответов: 30 |
Профиль | | #3 | Добавлено: 25.06.10 10:05 |
| Имеется облако точек, в пространстве (плоскости). Задача вообще - убрать все внутренние точки облака, оставив только периметр (границу). Для этого необходим алгоритм. Чтобы найти границу, можно сделать анализ окружения каждой точки в облаке. На границах точки окружены меньшим количеством соседних точек, нежели в объеме. Исходя из этого, можно вычесть "объем", оставив только "поверхность". Такие дела. | ||
|
Номер ответа: 4 Автор ответа: s12Вопросов: 24 Ответов: 363 |
Профиль | | #4 | Добавлено: 25.06.10 11:03 |
|
Я бы заюзал другой путь. (для плоскости) Сначала определяются четыре т. н. базовые точки, делящие облако на 4 четверти, т. е. за пределами максимальной или минимальной координатой точек нет. Получим A(xMin, Ay), B(xMax, By), C(Cx, yMin), D(Dx, yMax)
Далее можно пойти двумя путями: Либо искать среднюю точку между базовыми, затем среднюю между базовой и средней и т. д. вобщем задачка для фанатов рекурсии. Либо классическим перебором т. е. на интервале AD ищем точку A1 такую что: A1x >= xMin и точек с х < A1x и y <= Ay нет, после A1x становиться xMin и по новой пока xMin <> Dx. Такие зависимости пишем для всех четвертей. Полученные точки естественно сохраняем, из них и получиться "поверхность". Вариант с пространством делается по этому же принципу, только опорных точек будет шесть. |
||
|
Номер ответа: 5 Автор ответа: Sharp Лидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #5 | Добавлено: 25.06.10 11:15 |
| Если тебе нужен только периметр, это называется "выпуклая оболочка". Читай про алгоритм Грэхема. | ||
|
Номер ответа: 6 Автор ответа: ЮрийВопросов: 3 Ответов: 30 |
Профиль | | #6 | Добавлено: 25.06.10 11:19 |
| он применим к n-мерным пространствам? К изо-поверхностям? | ||
|
Номер ответа: 7 Автор ответа: ЮрийВопросов: 3 Ответов: 30 |
Профиль | | #7 | Добавлено: 25.06.10 11:20 |
| Спасибо за идею, а если в облаке есть внутренние дыры, то есть пустые области, тогда как быть? | ||
|
Номер ответа: 8 Автор ответа: s12Вопросов: 24 Ответов: 363 |
Профиль | | #8 | Добавлено: 25.06.10 15:02 |
|
он применим к n-мерным пространствам?
Да. Количество опорных точек равно 2n К изо-поверхностям?
Знать бы что это такое? а если в облаке есть внутренние дыры, то есть пустые области, тогда как быть?
А никак. Облако может быть абсолютно любой формы. Единственное условие - количество точек >= четырем. Вот здесь туева куча алгоритмов. Можно что нибудь из них собрать. http://algolist.manual.ru/maths/geom/convhull/ |
||
|
Номер ответа: 9 Автор ответа: s12Вопросов: 24 Ответов: 363 |
Профиль | | #9 | Добавлено: 25.06.10 15:06 |
|
Sharp
Насколько я помню Грэхем не годиться для пространственных моделей. Хотя если вспомнить, что меня выгнали с третьего курса универа, то могу и ошибаться. |
||
|
Номер ответа: 10 Автор ответа: ЮрийВопросов: 3 Ответов: 30 |
Профиль | | #10 | Добавлено: 25.06.10 15:10 |
|
Вот здесь туева куча алгоритмов. Можно что нибудь из них собрать.
http://algolist.manual.ru/maths/geom/convhull/ Спасибо огромное! |
||
|
Номер ответа: 11 Автор ответа: ЮрийВопросов: 3 Ответов: 30 |
Профиль | | #11 | Добавлено: 25.06.10 15:13 |
|
А никак. Облако может быть абсолютно любой формы. Единственное условие - количество точек >= четырем.
Я почитаю обязатльно, а если.. Внутренние дыры тоже должны формироовать поверхности, как и за пределами массива. Например сфера в сфере 
|
||
|
Номер ответа: 12 Автор ответа: s12Вопросов: 24 Ответов: 363 |
Профиль | | #12 | Добавлено: 25.06.10 15:36 |
|
Ну и что? Формируем внешнюю сферу. Задействованные точки (и при необходимости рядом стоящие) исключаем из перебора. И повторяем алгоритм, и так далее пока не останется меньше четырех незадействованных точек.
Более сложный случай когда внутренняя сфера касается внешней. В этом случае перед исключением точек внешней сферы потребуется найти точку соприкосновения, которая не будет исключаться из перебора. |
||
|
Номер ответа: 13 Автор ответа: SharpЛидер форума ICQ: 216865379 Вопросов: 106 Ответов: 9979 |
Web-сайт: Профиль | | #13 | Добавлено: 25.06.10 21:23 |
| Если нужна сфера в сфере, это уже не выпуклая оболочка. Опиши изначальную задачу целиком. | ||
Страница: 1 |