Есть массив треугольников, заданных координатами вершин. Как определить номера треугольников, подобных первому?

Question

[Дмитрий Демидов]

Здравствуйте!

Есть массив треугольников, заданных координатами вершин. Нужно определить номера треугольников, подобных первому.

Что я делаю.
1. Нам понадобится формула расстояния между точками:

def length(a, b):
	return math.sqrt((a[0] - b[0])**2 + (a[1] - b[1])**2)

2. Для определения подобных треугольников я буду пользоваться тем фактом, что отношение периметров таких треугольников равно коэф. подобия, а отношение площадей - квадрату того же числа. Соответственно мне нужно найти их для каждого из треугольников. Вот так:

triangles = []

for i in v:
	a = length(i[0], i[1])
	b = length(i[0], i[2])
	c = length(i[1], i[2])
	triangle = []
	p = (a + b + c)/2
	area = math.sqrt(p * (p - a) * (p - b) * (p - c))
	triangle.append(p*2)
	triangle.append(area)
	triangles.append(triangle)

3. Теперь функция, которая будет определять подобные треугольники:

def is_sim(sample, triangle):
	if int(sample[0]/triangle[0])**2 == int(sample[1]/triangle[1]):
		return True
	else:
		return False

4. И этой функцией побежали по списку треугольников

for i in range(0, len(triangles) - 1):
	if is_sim(triangles[0], triangles[i]):
		print str(i+1)

Есть компетентный человек, который утверждает, что результат работы неверен. Но категорически отказывается даже заглядывать в код.

В чем моя ошибка?

Comments

[sim3x]

Пфф, сделайте набор тестов, которые вручную проверьте.
И проверяйте.
Людям свойственно ошибаться

[sim3x]

Версия питона и полный код были бы не лишними.

Answer 1

[Валентин]

Почитал про подобие треугольников... задумался, почему нельзя действовать по определению или признакам подобия? Повернуть треугольник так, чтоб одно ребро легло на ось ничто ведь не мешает? А значит ничто не мешает построить высоту и угол посчитать? А значит так можно сделать три раза)

Comments

[Дмитрий Демидов]

А чем это будет проще?

[tsarevfs]

@vvpoloskin @ptitca_zu Сложные признаки предлагаете. Отсортировать стороны каждого треугольника по длине и проверить равенство 3 отношений. @ptitca_zu

[tsarevfs]

@ptitca_zu Причем нельзя просто сравнивать floating point числа: попробуйте выполнить 0.1 + 0.2 == 0.3.

[tsarevfs]

@tsarevfs используйте:

def eq( a, b, eps=0.0001 ):
    return abs(a - b) <= eps

eq(0.1 + 0.2, 0.3)

[Дмитрий Демидов]

@tsarevfs первое решение было как раз "по трем сторонам". Видимо дело было не в признаке, а в неправильном подходе к сравнению.

[tsarevfs]

@ptitca_zu и просто по сторонам тоже не получится. Могут попасть зеркальные треугольники.

[Дмитрий Демидов]

@tsarevfs почему? Третий признак подобия же по трем сходственным сторонам?

[tsarevfs]

@ptitca_zu

Если три стороны одного треугольника пропорциональны трём сходственным сторонам другого, то треугольники подобны.

В том и дело что по сходственным. Значит просто отсортировать не вариант. Важно направление обхода треугольника. Код не проверял, но идея вроде такая.

[tsarevfs]

@ptitca_zu
вот пример:
I.
a = (0, 0)
b = (1, 0)
c = (0, 1)
II.
a = (0, 0)
b = (-1, 0)
c = (0, 1)

Answer 2

[tsarevfs]

I.
b = 1/32 * (137-sqrt(9553))
a = 9 / b
c = 16 - a - b
II.
a = 5
b = 5
c = 6

далеко не подобны, однако под 2 ваших признака попадают.
вы выбрали не достаточное условие для определения подобия.

Comments

[tsarevfs]

+ еще попробуйте выполнить 0.1 + 0.2 == 0.3

Answer 3

[Елена Большакова]

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)

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

Answer 4

[jcmvbkbc]

Зеркальное отражение одного из подобных треугольников сохраняет пропорции сторон и площадей, но треугольники перестают быть подобными, если они не равнобедренные.

Answer 5

[jcmvbkbc]

А вообще, если немного подумать, то легко увидеть (с), что существует бесконечно много разных треугольников с равными периметром и площадью. Доказательство (нестрогое) примерно таково:
Рассмотрим все треугольники заданного периметра. Представим каждый из них точкой P в полярной системе координат, одна из вершин треугольника лежит в начале координат, вторая -- данная точка, третья лежит на полярной оси. Представим площадь такого треугольника высотой z в цилиндрической системе координат основанной на данной полярной. Множество всех треугольников данного периметра описывается множеством точек P, которое покрывает некоторую односвязную область, на границах которой площадь равна 0. Кроме того, площадь треугольника -- непрерывная функция от P. Выберем произвольную точку P0 внутри области. Пусть S(P0) = S0 > 0. Рассмотрим все возможные пути от точки P0 до границ области. На каждом из этих путей S является непрерывной функцией, изменяющейся от S0 до 0. Выберем значение S1, 0 < S1 < S0. По теореме о промежуточных значениях непрерывной функции на каждом из путей существует точка, в которой значение площади равно S1, и это -- не P0 => таких точек бесконечно много.

Answer 6

[SiDChik]

А что значит подобный? по сути нужно взять набор углов, разве нет? дале отсортировав набор углов можно данные сгруппировать и выдать подобные. Зеркально отраженный он же тоже подобный?

Comments

[SiDChik]

точней я перечитал ставить наименьший угол в начало, чтобы была хоть какаято сортировка углов и тем самым будет сохранен поворот и зеркальные треугольники отсеются

[tsarevfs]

@SiDChik Зеркальный не подобный в математическом смысле. Не нужно забывать, что порядок обхода во входных данных тоже не определен.

[Mrrl]

В математическом смысле он как раз подобный. Все расстояния изменились в одно и то же число раз, значит, свойство преобразования подобия сохраняется. А про ориентацию там ничего не сказано.

[tsarevfs]

@Mrrl во всех определениях есть слова "соответственные" или "сходственные" что указывает на ориентацию.

[tsarevfs]

@Mrrl Хотя преобразование подобия похоже не обязано сохранять ориентацию. Возможно вы и правы.

[Дмитрий Демидов]

@tsarevfs @Mrrl если говорить о преобразованиях, то подобные треугольники получаются параллельным переносом, поворотом или масштабированием. Меня зеркальные тоже смущают, я думаю, что они все же будут подобными.

[Mrrl]

Есть ещё такое преобразование подобия, как "зеркальная гомотетия". Оно ориентацию не сохраняет.

Answer 7

[lookid]

Берете 3 признака подобия.
Пишите для них тесты.
Прогоняете по 100000 треугольников. Берете что быстрее. У одних синусы-косинусы, у других квадратные корни

Comments

[Mrrl]

Квадратные корни не нужны. Достаточно, чтобы были равны отношения квадратов сторон.
Считаем квадраты сторон треугольника, для каждого берем минимум, максимум и сумму квадратов сторон (это чтобы не сортировать). Считаем отношения минимумов, максимумов и сумм. Если все три отношения равны - значит, треугольники подобны.

Answer 8

[bluesky]

Скорее всего, в задаче предполагаются целочисленные координаты. В этом случае ошибка в использовании sqrt, так как задачу можно решить в целых числах: использовать например, скалярные произведения.

Если же нет, то сравнивать на равенство надо с использованием эпсилонов. И в любом случае забыть про формулу Герона.