Нахождение площади выпуклого четырехугольника
У меня тут такая задачка, долго думал, а решить не могу:
2 выпуклых четырехугольника заданы на плоскости перечислением координат вершин в порядке обхода границ. Определить площади четырехугольников и проверить, лежит ли один внутри другого.
помогите пожалуйста, можно даже не код, а общее решение, а то я что то запутался...
в одной из тем этого раздела уже пытались такое сделать методом разбиения четырехугольника на треугольники (для них формула есть. Можно считать через определители или найдя через координаты длины сторон). Правда возникла проблема с правильным разбиением четырехугольника на два треугольника. Как это сделать правильно, я не знаю, поэтому могу предложить поступить с треугольниками несколько иначе. На каждой из сторон четырехуголника можно построить два треугольника (соединив концы данной стороны с двумя другими вершинами). Всего в выпуклом четырехугольнике можно построить четыре различных треугольника, но чтобы не заморачиваться с условиями или проверкой "был ли уже такой треугольник", можно рассматривать по два треуг. для каждой из сторон (в итоге получится их восемь), находить их площадь и суммировать с общим результатом. В конце общий результат поделить на 4.
Можно еще попробовать сделать через прибавление/вычитание площади под каждым из отрезков, составляющих Четырехуг. Если над стороной нет других сторон, то площадь под данной стороной записывается со знаком '+', если есть - со знаком '-'. В итоге - площадь четырехуг.
во-первых, нужно проверить, пересекаются ли они или нет (для каждой из сторон первого Ч. проверить, пересекается ли она с какой-либо из сторон второго Ч. Это можно сделать, составив по координатам уравнения прямых для сторон и найдя точки их пересечения, а именно - где они расположены: на стороне или на ее продолжении). Во-вторых, если Ч. не пересекаются, нужно сравнить их крайние координаты (т.е. наибольшие и наименьшие координаты x и y), чтобы проверить, лежит ли одни внутри другого или они просто рядом расположены.
Вот такое мое решение. Может можно и проще, но я пока этого не вижу.
a1*x' + b1*y' <= c1
a2*x' + b2*y' <= c2
..........................
an*x' + bn*y' <= cn
n - количество граней многоугольника .
x',y' - координаты точки .
(an*x + bn*y = cn) - уравнения образующей прямой . находится по соседним вершинам многоугольника .
круто конечно. А если не секрет, как это здесь использовать можно? (Автор топика что-то молчит, но мне тоже интересно - для общего развития).
если все вершины одного многоугольника находятся внутри другого , то и весь многоугольник находится внутри другого .
ааа ! Спасибо, теперь понятно. Неверно поняла фразу "принадлежность точки", а уравнения почему-то не догадалась проанализировать. Действительно, этот способ легок и удобен.