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

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

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

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

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

[LPBoy]

Если я правильно понял задание и ничего не путаю, то наверно можно так:

Рассматриваем по очереди всевозможные комбинации из трех точек.
Для каждой из трех точек с координатами (x1, y1) проверяем справедливо ли неравенство
sqrt(x1^2+y1^2) <= R. Если в данной комбинации из 3-х точек есть такие точки(или одна точка) для
которых неравенство справедливо и в то же время есть такая точка(точки) для которой оно несправедливо
(что означает что какая-то одна точка лежит внутри окружности, а другая вне ее), то рисуем треугольник.

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

[Lapp]

Если я правильно понял задание и ничего не путаю,

Кое что путаешь. Точнее - упускаешь.

- тут все вершины тр-ка снаружи, а пересечение есть.

[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. Некоторые треугольники могут быть построены дважды. Нужно ли это отслеживать - решай сама. Можно исключать треугольники по мере их построения.

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

то, что с окружностью - точно.
а вот как рассматривать треугольник - не совсем понимаю: как три отрезка или как кусочек плоскости. в принципе, влияет это только на 1 вариант (когда окружность внутри треугольника), так что, думаю, не очень важно.

всем спасибо! буду пробовать...

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

LPBoy, а откуда берутся формулы?
все классно работает, всем спасибо.

Сообщение отредактировано: мисс_граффити - 7.05.2006 20:54