Сама задача:
На плоскости заданы множество точек и окружность радиусом R с центром в начале координат.Построить множество всех треугольников с вершинами в заданных точках, имеющих непустое пересечение с окружностью.
Идеи есть, но они мне абсолютно не нравятся:
1) брать каждую точку из круга и смотреть, не принадлежит ли она треугольнику. если хоть одна принадлежит - рисовать. и так для каждого треугольника...
2) разбить на случаи:
2.0 если все три внутри - этот треугольник нас сразу перестает интересовать. иначе:
2.1. если хотя бы одна вершина лежит внутри - пересечение есть.
2.2 центр окружности лежит внутри треугольника - рисуем.
2.3 хотя бы одна сторона пересекает окружность - рисуем.
для отлавливания 2.3 надо составлять ур-ния сторон.... из-за нецелочисленности возникают дополнительные заморочки.
эта задача одна из четырех... три решаются в 2 строчки, поэтому мне кажется, и для четвертой должно существовать несложное решение.
код мне не нужен, а если какую-то мысль подкинете - буду дико благодарна.
Если я правильно понял задание и ничего не путаю, то наверно можно так:
Рассматриваем по очереди всевозможные комбинации из трех точек.
Для каждой из трех точек с координатами (x1, y1) проверяем справедливо ли неравенство
sqrt(x1^2+y1^2) <= R. Если в данной комбинации из 3-х точек есть такие точки(или одна точка) для
которых неравенство справедливо и в то же время есть такая точка(точки) для которой оно несправедливо
(что означает что какая-то одна точка лежит внутри окружности, а другая вне ее), то рисуем треугольник.
А если так:
для каждой комбинации из 3-х точек перебираем все комбинации из 2-х точек (x1,y1), (x2, y2)
и проверяем на пересечение с окружностью, по формулам:
dx = x2 - x1
dy = y2 - y1
dr = sqrt(dx^2+dy^2)
D=x1*y2-x2*y1
Дискриминант = R^2*dr^2-D^2,
если <= 0, то прямая не пересекает или касательная
если > 0 - пересекает
точки пересечения:
x=(D*dy±sign(dy)*dx*sqrt(R^2*dr^2 - D^2))/(dr^2)
y=(-D*dx±|dy|*sqrt(R^2*dr^2-D^2))/(dr^2)
где sign(x) = -1 если x<0; 1 если x>0; 0 если x = 0;
и если хотя бы одна из этих 2-х точек лежит на отрезке (x1,y1), (x2, y2) рисуем треугольник.
то, что с окружностью - точно.
а вот как рассматривать треугольник - не совсем понимаю: как три отрезка или как кусочек плоскости. в принципе, влияет это только на 1 вариант (когда окружность внутри треугольника), так что, думаю, не очень важно.
всем спасибо! буду пробовать...
LPBoy, а откуда берутся формулы?
все классно работает, всем спасибо.