Геометрическая задача, Пересечение треугольника и окружности Опции

[мисс_граффити]

Сама задача:
На плоскости заданы множество точек и окружность радиусом R с центром в начале координат.Построить множество всех треугольников с вершинами в заданных точках, имеющих непустое пересечение с окружностью.

Идеи есть, но они мне абсолютно не нравятся:
1) брать каждую точку из круга и смотреть, не принадлежит ли она треугольнику. если хоть одна принадлежит - рисовать. и так для каждого треугольника...
2) разбить на случаи:
2.0 если все три внутри - этот треугольник нас сразу перестает интересовать. иначе:
2.1. если хотя бы одна вершина лежит внутри - пересечение есть.
2.2 центр окружности лежит внутри треугольника - рисуем.
2.3 хотя бы одна сторона пересекает окружность - рисуем.
для отлавливания 2.3 надо составлять ур-ния сторон.... из-за нецелочисленности возникают дополнительные заморочки.

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

[LPBoy]

А если так:

для каждой комбинации из 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) рисуем треугольник.

Сообщение отредактировано: LPBoy - 4.05.2006 1:36

[Lapp]

А если так:
...

В целом верно, хотя формулы я не проверял. Попробую словесно уточнить и кое-где подправить общий алгоритм.

1. На всякий случай: уточнить, что пересечение берется именно с окружностью, а не с кругом, а треугольник при этом рассматривается как совокупность сторон без внутренности. Нижеследующее верно только для этого случая.

2. Мне кажется, искать нужно не треугольники - искать нужно отрезки. То есть перебираем все пары точек, проводим через них прямую, ищем пересечения этом прямой с окружностью. Для каждой из точек пересечиния (их не более двух) проверяем, лежит ли она на отрезке, ограниченном выбранной парой точек (это сделать легко, достаточно проверить одну координату; если по ней не проверяется - другую).

3. Если отрезок пересекается с окружностью (или касается ее), то рисуем все треугольники, образованные этим отрезком как стороной и всеми остальными точками как третьей вершиной.

4. Некоторые треугольники могут быть построены дважды. Нужно ли это отслеживать - решай сама. Можно исключать треугольники по мере их построения.