Ответы пользователя по тегу Математика
  • Алгоритмы визуализации графов, откуда взять информацию?

    Например, есть GraphViz -- программа для визуализации графов. Ею можно пользоваться, а кроме того, у них большой и информативный сайт.

    Сайт: www.graphviz.org
    примеры работы: www.graphviz.org/Gallery.php
    описание на русском: www.portablecomponentsforall.com/edu/graphviz-about-ru
    ссылки на теорию: www.graphviz.org/Theory.php
    Википедия английская: en.wikipedia.org/wiki/Graph_drawing
    Википедия русская: ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%B7%D1%83%D0%...

    Надеюсь, ссылки в какой-то степени помогут.

    Кстати, существует целый ежегодный Международный визуализации графов (организаторы: graphdrawing.org), так что тема весьма серьезна.
    Ответ написан
    Комментировать
  • Есть массив треугольников, заданных координатами вершин. Как определить номера треугольников, подобных первому?

    1. Проверять подобие по соотношениям периметра и площади -- недостаточно. Контрпример есть в комментарии @tsarevfs, теоретическое обоснование -- в комментарии @jcmvbkbc.

    2. Если треугольники заданы координатами вершин -- проще всего проверять третий признак подобия (все три стороны одного треугольника пропорциональны сторонам другого).

    3. Если координаты вершин -- небольшие целые числа, то лучше проверять пропорциональность не самих сторон, а их квадратов, причем проверять не отношения сторон, а произведения "крест-накрест".
    Чтобы сравнивать только потенциально соответственные стороны -- сортировать длины сторон (на самом деле квадраты длин) в каждом треугольнике по возрастанию.

    Например, вот так можно модифицировать исходный код:
    # квадрат расстояния между двумя точками
    def length2(a, b):
        return (a[0] - b[0])**2 + (a[1] - b[1])**2
    
    # подобны ли 2 треугольника, заданные отсортированными массивами длин сторон
    def is_sim(sample, triangle):
        if sample[0] * triangle[1] != sample[1] * triangle[0]:
            return False
        elif sample[0] * triangle[2] != sample[2] * triangle[0]:
            return False
        elif sample[1] * triangle[2] != sample[2] * triangle[1]:
            return False
        else:
            return True
    
    # преобразование массивов координат в массивы длин сторон
    def make_triangles(v):
        triangles = []
        for i in v:
            a2 = length2(i[0], i[1])
            b2 = length2(i[0], i[2])
            c2 = length2(i[1], i[2])
            triangle = [a2, b2, c2]
            triangle.sort()
            triangles.append(triangle)
        return triangles
    
    # основной код
    triangles = make_triangles(v)
    
    for i in range(1, len(triangles) ):
        if is_sim(triangles[0], triangles[i]):
            print "found similar trinangle: %s" % v[i]


    Если координаты могут быть большими и/или вещественными, то лучше вернуться к длинам и отношениям, но при сравнении в фунции is_sim полагаться не на точное равенство, а с допуском ("с эпсилонами", см. комментарии @bluesky и @tsarevfs)

    И на всякий случай: в комментариях были сомнения про зеркально-симметричные треугольники. Так вот, зеркальное отражение подобно исходному треугольнику, и порядок обхода сторон для сравнения роли не играет.
    Ответ написан
    Комментировать