Задаются произвольные координаты точек A, B, C, D на плоскос

[rouziqq]

Задаются произвольные координаты точек A, B, C, D на плоскости. Найти
максимальную площадь фигуры с вершинами в данных точках.
Доброго времени дня, стоит данная задача, выполнить необходимо в LabView, проблема состоит в расчёте площади возможного четырёхугольника, не очень хочется в вентильной схеме сортировать вершины... Каким способом можно найти площадь четырёхугольника?
Видел такое решение проблемы:
"Надо проверить, что точки $A$ и $C$ лежат по разные стороны от прямой $BD$, и точки $B$ и $D$ - по разные стороны прямой $AC$. Для того, чтобы проверить первую вещь, надо посчитать векторные произведения $[BA,\,BD]$ и $[BD,\,BC]$ и посмотреть, одинаковый ли у них знак."
Не совсем уверен что работает во всех случаях... Подскажите пожалуйста.

[Dan B-Yallay]

rouziqq в сообщении #1664549 писал(а):

Задаются произвольные координаты точек A, B, C, D на плоскости. Найти
максимальную площадь фигуры с вершинами в данных точках.

В такой постановке задача имеет не больше смысла чем такая: "Из натурального ряда случайно выбирается число. Найти его максимальное значение"

[wrest]

rouziqq в сообщении #1664549 писал(а):

Каким способом можно найти площадь четырёхугольника?

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

[rouziqq]

Цитата:

Как сумму площадей двух треугольников, по формуле Герона

в таком случае нужно определить выпуклый или вогнутый...

-- 11.12.2024, 23:30 --

Тут скорее вопрос, как определить выпуклость и вправду... С этим всё легко окажется

[wrest]

rouziqq в сообщении #1664556 писал(а):

Тут скорее вопрос, как определить выпуклость и вправду...

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

Дальше считаете для скольких из этих прямых по одну сторону лежат две точки. Если таких 4 -- выпуклый. Если 3 - нет.
Походу дела определятся и диагонали по которым резать.

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

Во втором случае (невыпуклый) у вас 3 возможных четырехугольника. Тогда считаете площади трёх треугольников. У всех трех треугольников будет общая вершина - это та точка через которую проходят три прямые такие, что две других точки лежат по разные стороны от неё. Из трех площадей отбрасываете наименьшую, две других складываете - сумма будет ответом.

[dgwuqtj]

wrest в сообщении #1664564 писал(а):

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

По условию нужна плошадь выпуклой оболочки, так что на самом деле надо просто выкинуть внутреннюю точку и посчитать площадь одного треугольника.

[EUgeneUS]

dgwuqtj в сообщении #1664631 писал(а):

По условию нужна плошадь выпуклой оболочки, так что на самом деле надо просто выкинуть внутреннюю точку и посчитать площадь одного треугольника.

Не факт, что условия следует трактовать так.

[dgwuqtj]

А, там же написано про четырёхугольник... Можно тогда вообще не перебирать случаи, а просто использовать формулу

$$S = \frac 1 2 \max\bigl(\bigl|[BA, CA] + [CA, DA]\bigr|, \bigl|[BA, DA] + [DA, CA]\bigr|, \bigl|[CA, BA] + [BA, DA]\bigr|\bigr).$$

Главное, вокруг отдельных слагаемых модули случайно не поставить, они могут быть разных знаков.

[wrest]

dgwuqtj в сообщении #1664631 писал(а):

По условию нужна плошадь выпуклой оболочки,

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