Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Нахождение площади выпуклого четырехугольника

5.7K
31 мая 2007 года
denxx
45 / / 05.01.2006
Всем привет!
У меня тут такая задачка, долго думал, а решить не могу:

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

помогите пожалуйста, можно даже не код, а общее решение, а то я что то запутался...
7.8K
31 мая 2007 года
Hrew
185 / / 23.04.2007
Цитата: denxx
Определить площади четырехугольников


в одной из тем этого раздела уже пытались такое сделать методом разбиения четырехугольника на треугольники (для них формула есть. Можно считать через определители или найдя через координаты длины сторон). Правда возникла проблема с правильным разбиением четырехугольника на два треугольника. Как это сделать правильно, я не знаю, поэтому могу предложить поступить с треугольниками несколько иначе. На каждой из сторон четырехуголника можно построить два треугольника (соединив концы данной стороны с двумя другими вершинами). Всего в выпуклом четырехугольнике можно построить четыре различных треугольника, но чтобы не заморачиваться с условиями или проверкой "был ли уже такой треугольник", можно рассматривать по два треуг. для каждой из сторон (в итоге получится их восемь), находить их площадь и суммировать с общим результатом. В конце общий результат поделить на 4.
Можно еще попробовать сделать через прибавление/вычитание площади под каждым из отрезков, составляющих Четырехуг. Если над стороной нет других сторон, то площадь под данной стороной записывается со знаком '+', если есть - со знаком '-'. В итоге - площадь четырехуг.

Цитата: denxx
проверить, лежит ли один внутри другого.


во-первых, нужно проверить, пересекаются ли они или нет (для каждой из сторон первого Ч. проверить, пересекается ли она с какой-либо из сторон второго Ч. Это можно сделать, составив по координатам уравнения прямых для сторон и найдя точки их пересечения, а именно - где они расположены: на стороне или на ее продолжении). Во-вторых, если Ч. не пересекаются, нужно сравнить их крайние координаты (т.е. наибольшие и наименьшие координаты x и y), чтобы проверить, лежит ли одни внутри другого или они просто рядом расположены.

Вот такое мое решение. Может можно и проще, но я пока этого не вижу.

252
01 июня 2007 года
koderAlex
1.4K / / 07.09.2005
для треугольников и выпуклх многоугольников принадлежность почки доказывается если верны неравенства вида :
a1*x' + b1*y' <= c1
a2*x' + b2*y' <= c2
..........................
an*x' + bn*y' <= cn
n - количество граней многоугольника .
x',y' - координаты точки .
(an*x + bn*y = cn) - уравнения образующей прямой . находится по соседним вершинам многоугольника .
7.8K
02 июня 2007 года
Hrew
185 / / 23.04.2007
Цитата: koderAlex
для треугольников и выпуклх многоугольников принадлежность почки доказывается если верны неравенства вида :


круто конечно. А если не секрет, как это здесь использовать можно? (Автор топика что-то молчит, но мне тоже интересно - для общего развития).

252
02 июня 2007 года
koderAlex
1.4K / / 07.09.2005
Цитата: denxx
... и проверить, лежит ли один внутри другого ...



если все вершины одного многоугольника находятся внутри другого , то и весь многоугольник находится внутри другого .

7.8K
02 июня 2007 года
Hrew
185 / / 23.04.2007
Цитата: koderAlex
если все вершины одного многоугольника находятся внутри другого , то и весь многоугольник находится внутри другого .


ааа ! Спасибо, теперь понятно. Неверно поняла фразу "принадлежность точки", а уравнения почему-то не догадалась проанализировать. Действительно, этот способ легок и удобен.

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог