Задача о треугольниках

scorpi.on · 17 мар 2006, 19:58

Помогите пожалуйста.
Даны два треугольника заданные координатами своих точек.
Нужно узнать площадь получившейся фигуры, в результате пересечения треугольников. Площадь может быть и нулевой.

18 мар 2006, 12:12

Тема переехала. Из Паскакаля. Потому что не сезон

На самом деле задачка тривиальная. У тебя даны 6 уравнений прямых, решая 9 систем ЛУ с граничными условиями,
находишь все точки пересечения. Если ничего не путаю, то максимум их может быть 6 штук. Полученную фигуру разбиваешь на треугольники, т.е. объединяешь точки пересечения по 3. Находишь площади треугольников и суммируешь. Не забывай о ситуации, когда один треугольник исходный треугольник внутри другого.

scorpi.on · 22 мар 2006, 21:19

AiK писал(а):Тема переехала. Из Паскакаля. Потому что не сезон
На самом деле задачка тривиальная. У тебя даны 6 уравнений прямых, решая 9 систем ЛУ с граничными условиями,
находишь все точки пересечения. Если ничего не путаю, то максимум их может быть 6 штук. Полученную фигуру разбиваешь на треугольники, т.е. объединяешь точки пересечения по 3. Находишь площади треугольников и суммируешь. Не забывай о ситуации, когда один треугольник исходный треугольник внутри другого.

Вам легко говорить. И недо делить ни на какие треугольники. Можно просто найти площадь получившегося многоугольника.

Oscar · 22 мар 2006, 22:19

AiK писал(а):находишь все точки пересечения. Если ничего не путаю, то максимум их может быть 6 штук

А если одна сторона - (частично) общая? :-)

scorpi.on писал(а):Вам легко говорить. И недо делить ни на какие треугольники. Можно просто найти площадь получившегося многоугольника.

Да ну? Можно просто найти площадь произвольного многоугольника (12-угольника, в худшем случае) по всем его точкам?

А формулу можно посмотреть? ))

Oscar · 22 мар 2006, 23:00

Так, я вижу 7 случаев.

Как их распознать:

1. Исключаем первые три случая
2. Ищем точки пересечения

3. Если точек пересечения - две
3а. Внутри одного лежит одна точка: Суммируем площадь двух, отнимаем площадь маленького (случай 4)
3б. Если внутри две точки: Площадь внешнего плюс площадь маленького (случай 5)

4. Если четыри точки пересечения (случай 6): Если есть формула произвольного четырёхугольника - используем её, если нет - делим на два треугольника и получаем площадь внутреннего четырёхугольника. Суммируем площадь двух треугольников и отнимаем площадь полученого четырёхугольника.

5. Если точек пересечения - 6 (случай 7) Площадь одного треугольника, плюс площадь трёх маленьких треугольничков

6. Исключительная ситуация: Если я чего-то не учёл

Oscar · 22 мар 2006, 23:39

Блин, хорошая, ведь задачка ....

7. Случай 8 - частный случай от 5-ого, но не вздумать его исключать, как третий
8. Случай 10 - частный случай от 6-го, но точек пересечения всего три
9. Случай 12 - частный случай от 4-го
10. Случай 13, обратить внимание, если есть одна общая точка.

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

Хм .... Задумаешься тут .... Как бы это всё оптимизировать.

Kolinus · 23 мар 2006, 19:08

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