[_Andre_]

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

На ум приходит по-парная проверка на пересечение отрезков соединяющих все возможные пары точек, но более-менее изящной реализации такого метода сортировки не приходит на ум ;(

[_Andre_]

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

[VVA]

Может поможет
http://algolist.manual.ru/olimp/geo_prb.php Задача №12
http://mivmiv.narod.ru/Math/tetra.html Задача №1
http://www.autocad.ru/cgi-bin/f1/board.cgi?t=3908Xo
Найдешь решение-покажи.
Мое утверждение требует доказательств, но по моему этот четырехугольник - выпуклый и площадь его максимальна.
Как вариант перебрать все варианты расположения вершин, их по моему 2**4=16 и найти максимальную площадь, это если влоб.

[VVA]

Еще пришла идея поискать алгоритм построения выпуклой области, 4-х угольник частный случай.
Бесконечная прямая пересекает замкнутую выпуклую область ровно в двух точках.
http://www.codenet.ru/progr/cg/lec_3_1.php

[_Andre_]

to VVA
Спасибо за интересные ссылки.
Также нашел вот такую задачу http://algolist.manual.ru/olimp/geo_prb.php задача 3.

Из всего можно сделать вывод - что для того чтобы отсортировать четыре точки - углы выпуклого четырехугольника - надо сделать следующее:
1. найти любую внутренню точку четырехугольника
х=1/3*(х1+х2+х3); у=1/3*(у1+у2+у3)
2. найти углы образуемые отрезками соединяющими эту точку со всеми углами
3. отсортировать углы по возрастанию или убыванию, в данном случае неважно.
4. после сортировки сопоставить углу точку

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

сейчас сделаю lisp программку, проверю и выложу.

[PSW]

(defun C:sss (/)
; Как отсортировать список координат
; ((660 307) (0 307) (440 0) (660 0) (220 307) (0 0) (220 0) (440 307))
; чтобы получить
; ((0 0) (220 0) (440 0) (660 0) (0 307) (220 307) (440 307) (660 307))
;##############################################################################
(vl-sort
'((660 307) (0 308) (440 0) (500 600) (660 0) (220 307) (0 0) (220 0) (440 307))
(function (lambda (e1 e2)
(if
(= (cadr e1) (cadr e2))
(< (car e1) (car e2))
(< (cadr e1) (cadr e2))
)
)
)
)
;##############################################################################
(princ)
)

[_Andre_]

to PSW
Не очень понял алгоритм Вашей функции, но она сортирует не так как нужно (возможно я непонятно сформулировал задачу)

Мой вариант выглядит так:

Код:

[Выделить все]

(defun ba-ba (list_of_points /)
;;;находим внутреннюю точку выпуклого многоугольика, координаты считаем как треть суммы координат любых трех точек-углов
  (setq int_point
         (mapcar '(lambda (x) (* (/ 1.0 3.0) x))
                 (mapcar '+ (car list_of_points) (cadr list_of_points) (caddr list_of_points))
         ) ;_ end of mapcar
  ) ;_ end of setq
  ;|составляем список пар (угол к оси х . точка-угол) уголк сои мерием от внутреней точки до точки-угла|;
  (setq list_of_angle (mapcar '(lambda (x) (cons (angle int_point x) (list x))) list_of_points))
;;;сортируем по углу
  (setq sort_list_of_angle (vl-sort list_of_angle '(lambda (x1 x2) (< (car x1) (car x2)))))
;;;оставляем только точки
  (setq sort_list_of_points (mapcar 'cadr sort_list_of_angle))
)

Работает для не только для четырех но и для другого-количества-угольников. Главное условие чтобы многоугольник был выпуклым.

Кстати - как можно более изящно реализовать вот это выражение:

Код:

[Выделить все]

(mapcar '(lambda (x) (* (/ 1.0 3.0) x))
                 (mapcar '+ (car list_of_points) (cadr list_of_points) (caddr list_of_points))
         )