?

Log in

No account? Create an account

[icon] Задача из реальной жизни - Lorem Ipsum igitur, juvenes dum sumus — ЖЖ
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).

Tags:,
Security:
Subject:Задача из реальной жизни
Time:05:13 pm
Есть набор точек в пространстве RGB (подмножество декартова с ограничением на каждую координату: 0<=x<=255, x-целое).
Нужно найти три наиболее удаленные друг от друга точки A, B, C. Критерий удаленности - максимальная площадь треугольника ABC.

Есть идеи как написать очень быстрое и близкое к оптимальному решение? Нужна помощь, в общем.
comments: Оставить комментарий Previous Entry Поделиться Next Entry


codenamed
Link:(Link)
Time:2010-09-30 06:53 pm
Подозреваю, что вы тут имеете в виду не выпуклую оболочку, а составленный из треугольников ограничивающий множество точек полигон с вершинами в точках самого множества :)

Я бы тоже так решал: построил бы mesh, пронумеровал бы вершины и перебирал бы тройки. Но хорошо бы иметь оценку количества точек и примерно представлять, как они угрожают распределяться.

А из эвристик - построил бы bounding rectangle, выбрал бы точку, ближайшую к границе (или несколько). Для каждой такой точки находил бы максимально удаленную (или несколько, скажем, 5) и проходился бы по разу по всем остальным, вычисляя площади. Мне кажется, было бы что-то близкое к правде на выходе. Весь массив перебираем три раза: сортируем (ищем минимум расстояния), для "самой крайней" ищем самую дальню, и для каждой из оставшихся вычисляем площадь :)
(Ответить) (Thread)


torrio
Link:(Link)
Time:2010-09-30 06:59 pm
Ага, такую эвристику уже предложил ze_oboltus... Хорошая идея, мне нравится:-)
(Ответить) (Parent) (Thread)


codenamed
Link:(Link)
Time:2010-09-30 07:10 pm
Ждем результатов вычислительного эксперимента ;)
Ну и если расскажешь про исходную задачку, будет интересно. Про распознавание элементов изображений см. OpenCV и книжечку Gary Bradski, Adrian Kaehler - Learning OpenCV - O'Reilly (2008). Книжечка вроде ничего такая :)
(Ответить) (Parent) (Thread)


torrio
Link:(Link)
Time:2010-10-01 05:50 am
OpenCV - ха-ха - люди, смотрите, он сказал OpenCV! Ха-ха!:)))

(Саша, не обижайся. На самом деле мы испольуем кое-какие методы из OpenCV, но в целом это такая клоака...)

Про исходную задачу расскажу, когда мы её решим (может быть сегодня).
(Ответить) (Parent) (Thread)

[icon] Задача из реальной жизни - Lorem Ipsum igitur, juvenes dum sumus — ЖЖ
View:Свежие записи.
View:Архив.
View:Друзья.
View:Личная информация.
View:Website (Мой сайт).