Вводятся координаты четырёх точек на плоскости, определить могут ли они быть вершинами выпуклого четырёхугольника
Есть следующие идеи: если у нас есть четыре точки, то выпуклый четырехугольник может получится в том, и только в том случае, если для каждой точки справедливо условие: она не лежит внутри треугольника, образованного тремя оставшимися точками (можно легко проверить, нарисовав на бумаге четыре точки, являющиеся вершинами выпуклого и невыпуклого многоугольников). Осталось теперь это записать... для каждой точки. Может, у кого-нибудь есть идеи? Спасибо.
Ответы (2 шт):
Примитив
Если у вас есть три точки (p1 = (x1, y1), p2 = (x2, y2), p3 = (x3, y3)) на плоскости и они расположены против часовой стрелки, то этот определитель будет больше нуля:
| x1 y1 1 | > 0 - точки против часовой стрелки
| x2 y2 1 | = 0 - точки на одной прямой
| x3 y3 1 | < 0 - точки по часовой стрелке
Я буду через ds(p1, p2, p3) (det sign) обозначать знак определителя.
Проверка через треугольники
Через проверку знаков определителей можно установить что четвёртая точка находится внутри треугольника из первых трёх:
func in_triangle(p1, p2, p3, p4)
ds123 = ds(p1, p2, p3)
if ds123 != ds(p1, p2, p4)
return false
if ds123 != ds(p1, p4, p3)
return false
if ds123 != ds(p4, p2, p3)
return false
return true
Теперь нашу четвёрку точек разбиваем четырьмя способами на треугольник и точку. Для каждого способа проверяем что точка не внутри треугольника:
func convex(p1, p2, p3, p4)
if in_triangle(p1, p2, p3, p4)
return false
if in_triangle(p4, p1, p2, p3)
return false
if in_triangle(p3, p4, p1, p2)
return false
if in_triangle(p4, p1, p2, p3)
return false
return true
Как правильно
Вы спросите почему так сложно то? А потому что сделано элементарными средствами. Есть другой способ: построить выпуклую оболочку и проверить что все четыре точки в неё попали. Но это за пять минут не объяснишь.