Кол-во треугольников в фигуре
Пользователи, просматривающие топик: none
|
Зашли как: Guest
|
Имя  |
| Сообщение |
<< Старые топики Новые топики >> |
|
|
Кол-во треугольников в фигуре - 2006-06-21 11:55:36
|
|
|
Le_Flaw
Сообщений: 49
Оценки: 0
Присоединился: 2006-05-26 13:12:43
|
Всем привет!
Значит так…
Нам дана фигура. Допустим такая(BMP 800kb) или такая (JPG 24kb).
Нам нужно узнать количество всех треугольников в данной фигуре.
У меня получается вот такой алгоритм:
1) Пронумеруем все вершины
2) Занесем в массив пересечения всех вершин с другими
Например для данной фигуры будет:
<BR>1: 2,3,4,5,6,7,8,9,10,11,12<BR>2: 1,3,4,5,9,11<BR>3: 1,2,6,9,11,12<BR>4: 1,2,5,8,9,12<BR>5: 1,2,4,6,7,9,10,11,12<BR>6: 1,3,5,7,9,12<BR>7: 1,5,6,9,8,11<BR>8: 1,4,7,9,11,12<BR>9: 1,2,3,4,5,6,7,8,10,11,12<BR>10: 1,5,9,11,12<BR>11: 1,2,3,5,7,8,9,12<BR>12: 1,3,4,6,8,9<BR>
3) Уже программно искать треугольники:
Для примера возьмем треугольник с вершинами 1,2,3, для определения этого треугольника нам нужно найти в массиве:
с ячейкой 1 - числа 2 и 3,
с ячейкой 2 - числа 1 и 3,
с ячейкой 3 - числа 1 и 2.
Если мы все это найдем, то это треугольник.
Но еще это может быть и прямая(например если ищем 1,3,12), это конечно можно решить добавлением массива прямых, но все-таки что-то некрасиво получается.
Может быть у кого-нибудь есть другие идеи по решению данной задачи?
Ну или дополнения к моей?
Кароче пишите!
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 13:35:09
|
|
|
Pupkin-Zade
Сообщений: 9398
Оценки: 1489
Присоединился: 2004-03-10 13:54:16
|
800 Кб BMP это круто…
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 14:06:31
|
|
|
Le_Flaw
Сообщений: 49
Оценки: 0
Присоединился: 2006-05-26 13:12:43
|
quote:
—————-<BR>Цитата: Дата:21.06.2006 13:35:09, Автор:Pupkin-Zade ::
800 Кб BMP это круто…
—————-
[sm=sm128.gif] Понял
Теперь два варианта - BMP и JPG![sm=2.gif]
А насчет алгоритма есть идеи?[sm=1.gif]
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 15:09:19
|
|
|
Pupkin-Zade
Сообщений: 9398
Оценки: 1489
Присоединился: 2004-03-10 13:54:16
|
Ну так перебором
Очевидно, что каждая точка связана с каждой, соответственно нужно только алгоритм уточнить
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 15:22:54
|
|
|
Le_Flaw
Сообщений: 49
Оценки: 0
Присоединился: 2006-05-26 13:12:43
|
Поясни, не въехал…
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 18:04:29
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
ну вроде как только перебором:
foreach v1 in points; do
foreach v2 in points; do
if (v1 != v2 && exists_line (v1, v2))
foreach v3 in points; do
if (v3 != v1 && v3 != v2 &&
exists_line (v3, v1) &&
exists_line (v3, v2))
count ++
fi
done
fi
done
done
имеет смысл поиграть это с порядком перебора. Чтобы почём зря не перебирать вершины.
То есть, например, вместо того чтобы тупо перебирать
foreach v2 in points; if (…)
можно попробовать сказать:
foreach l1 in lines(v1);
foreach v2 in l1;
if (v2 != v1)
…
ну и `foreach v3 in points; if (…)' тоже можно так обработать.
а вообще надо подумать… вряд ли тут можно без перебора вообще, но может что-то и можно выудить
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 18:08:43
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
а! придумал как обойтись без этих foreach и тд :)
надо взять prolog. Штука для таких задач офигенная, но я чего-то тут два дня сидел, так и не научился им пользоваться :(
а так, там получиться три-четыре правила, и описание того, какие точки на каких прямых лежат. А алгоритм поиска пролог сам будет искать.
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 18:54:38
|
|
|
Le_Flaw
Сообщений: 49
Оценки: 0
Присоединился: 2006-05-26 13:12:43
|
Пасиба всем вам за помощь! [sm=em121.gif]
rgo, не мог бы сам описать в двух словах пролог.
Я где-то конечно слышал, что это язык логического программирования, основанный на логике дизьюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка, но как бы это попроще сформулировать! [sm=2.gif]
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 19:33:48
|
|
|
Pupkin-Zade
Сообщений: 9398
Оценки: 1489
Присоединился: 2004-03-10 13:54:16
|
Забей
ты потратишь на пролог полгода и чуть чуть только начнешь понимать как он работает
я сам его учил…
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 19:55:36
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
—————-<BR>Цитата: Дата:21.06.2006 18:54:38, Автор:Le_Flaw ::
Пасиба всем вам за помощь! [sm=em121.gif]<BR><BR>rgo, не мог бы сам описать в двух словах пролог.<BR><BR>Я где-то конечно слышал, что это язык логического программирования, основанный на логике дизьюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка, но как бы это попроще сформулировать! [sm=2.gif]
—————-
нну как его описать… Идея в том, чтобы писать не алгоритмы, а описывать логику задачи, и пускай пролог сам думает как эту задачу решать.
Он декларативный язык. То есть в императивном C ты пишешь:
сделай то, потом сделай это. И если всё получилось то сделай ещё то-то, то-то и то-то. А в прологе ты декларируешь правила, ну например, применительно к данной задаче, программа на прологе могла бы выглядеть примерно так (в переводе на русский, тк на прологе я так и не научился изъясняться):
сначала общие правила:
1) если три точки не лежат на одной прямой и попарно объединены отрезками, то это треугольник.
2) если точки v[1], v[2], v[3] … v[n] лежат на одной прямой, то любые v[i1], v[i2], …, v[ik], где 0 < ij <= n – тоже лежат на одной прямой.
3) две прямые имеют не более одной общей точки
и далее пошло описание конкретной задачи:
1) точка v1 лежит на прямой a
2) точка v2 лежит на прямой a
3) точка v4 лежит на прямой a
4) точка v5 лежит на прямой a
5) точка v1 лежит на прямой b
6) точка v3 лежит на прямой b
…
и последний этап – надо задать вопрос, типа сколько треугольников есть. Причём делается это довольно просто: если определение треугольника которое я дал вначале определено как функция triangle аргументы которой – три точки а результат true или false, то если написать:
triangle (A, B, C)
вернёт список возможных треугольников (A, B, C – upcase –> это не значения а переменные, и пролог начинает перебирать все тройки вершин и искать среди них треугольники).
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 20:00:33
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
—————-<BR>Цитата: Дата:21.06.2006 19:33:48, Автор:Pupkin-Zade ::
Забей<BR><BR>ты потратишь на пролог полгода и чуть чуть только начнешь понимать как он работает<BR><BR>я сам его учил…
—————-
а мне вот всё интересно, нельзя ли к прологу прикрутить более "умный" поиск решения. Ну, например, генетические алгоритмы. Типа я, например, пишу так вот логическое определение задачи, функцию оценки "удачности" решения, входные данные, и пролог, вместо того чтобы дцать миллиардов лет перебирать варианты в поисках лучшего, начинал бы эволюционный процесс возможных решений (мб частичных), до тех пор пока не родиться полноценное решение удовлетворяющее всем условиям.
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-21 20:16:06
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
в качестве альтернативы первому предложенному мной решению, могу предложить решение от обратного. В том смысле что считать количество треугольников, сравнивая имеющуюся картинку, и картинку в которой действительно любые две вершины соединены отрезками.
Когда все вершины соединены, сосчитать количество треугольников будет проще – это будет просто количество троек различных вершин. простая комбинаторика.
После этого надо будет вычесть количество вырожденных треугольников – тех, что лежат на одной прямой.
И наконец, вычесть количество треугольников, которые построены с использованием, нами добавленных, отрезков.
При некоторых условиях это будет быстрее.
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-22 08:50:12
|
|
|
Le_Flaw
Сообщений: 49
Оценки: 0
Присоединился: 2006-05-26 13:12:43
|
quote:
—————-<BR>Цитата: Дата:21.06.2006 20:16:06, Автор:rgo ::
в качестве альтернативы первому предложенному мной решению, могу предложить решение от обратного. В том смысле что считать количество треугольников, сравнивая имеющуюся картинку, и картинку в которой действительно любые две вершины соединены отрезками.<BR><BR><BR>Когда все вершины соединены, сосчитать количество треугольников будет проще – это будет просто количество троек различных вершин. простая комбинаторика.<BR><BR>После этого надо будет вычесть количество вырожденных треугольников – тех, что лежат на одной прямой.<BR><BR>И наконец, вычесть количество треугольников, которые построены с использованием, нами добавленных, отрезков.<BR><BR><BR>При некоторых условиях это будет быстрее.
—————-
Я понял твой замысел! Но в данной фигуре построить общее количество ребер, равное 66, будет не очень удобно(мне кажется), а замысел неплохой - нестандартный![sm=em121.gif]
А вот на ваш взгляд, сколько в этой фигуре(первое сообщение) треугольников?[sm=1.gif]
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-22 20:36:30
|
|
|
rgo
Сообщений: 7170
Оценки: 281
Присоединился: 2004-09-25 05:14:25
|
quote:
—————-<BR>Цитата: Дата:22.06.2006 8:50:12, Автор:Le_Flaw ::
<BR>Я понял твой замысел! Но в данной фигуре построить общее количество ребер, равное 66, будет не очень удобно(мне кажется), а замысел неплохой - нестандартный![sm=em121.gif]<BR><BR><BR>А вот на ваш взгляд, сколько в этой фигуре(первое сообщение) треугольников?[sm=1.gif]
—————-
зачем стоить? Количество всех треугольников, за исключением тех у которых 2 или 3 вершины совпадают это:
n*(n-1)*(n-2)/3! /* ааа! я там, когда писал эти foreach сосчитал каждый трегольник по три раза :) count надо делить на 3 после всех исхищрений. или, что лучше, организовать циклы так чтоб по разу считать */
количество вырожденных трков среди них (лежащих на одной прямой) – это сумма по всем прямым, c колвом точек на них == k (k>=3), выражения k*(k-1)*(k-2)/3! То есть:
\sum_{l in lines, k(l) >= 3} k(l)*(k(l)-1)*(k(l)-2)/3!
с учётом предыдущего: количество треугольников использующих заданный отрезок в качестве стороны равно количеству вершин не лежащих на прямой содержащей отрезок.
короче надо перебирать в одном цикле прямые, а потом, в другом цикле пары точек (не тройки!). Это же бонус.
После более внимательного рассмотрения, я начинаю склоняться к мысли, что второй вариант будет быстрее почти всегда. и при больших n тем более.
ps замысел стандартный для комбинаторики. Да и не только – для математики вообще. Например, доказательство от противного; вместо того чтобы считать "a = 1 + x + x^2 +…+ x^n" можно сосчитать "a * (1 - x)", а потом поделить на (1 - x), в результате получается (1 - x^(n+1))/(1 -x); вместо того чтобы считать чётные числа, можно сосчитать нечётные и вычесть из общего количества…
мало тебе моск математикой ипали [sm=2.gif]
|
|
|
|
|
Кол-во треугольников в фигуре - 2006-06-23 23:51:54
|
|
|
tw-tw
Сообщений: 126
Оценки: 0
Присоединился: 2005-03-07 23:20:49
|
Короче это что то типа теории графов
|
|
|
|
|
|
