Площадь четырехугольника

Question

У меня есть n точек в плоскости и целевой области P. Я пытаюсь найти четыре точки, которые имеют площадь, которая представляет собой углы четырехстороннего с самым близким значением области до P. Ниже приведен пример с п = 5 и P = 30:

• 0, 0
• 10, 0
• 0, 10
• 10, 10
• 7, 3

Ответ должен быть 30,0 (самый близкий к P, в этом случай равен).

У вас есть идеи, как я могу это сделать? Я знаю, что могу рассчитать площадь каждого четырехугольника, используя формулу Херона, но мне нужно попробовать каждую комбинацию или есть более короткий путь?

Answer 1

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

Но вы можете использовать ускорение: если у вас есть три точки, найдите область связанного треугольника, и если она больше, чем abs (целевая область - лучшая область до сих пор), вам не нужно попробовать какие-либо значения для четвертой точки.

Как мы уже упоминали в комментариях, вам нужны Bretschneider's formula для четырехсторонних областей, Херон - для треугольников.

Answer 2

Вы можете

1. взять блок/шаблон многоугольник с желаемым числом вершин и формы.

2. добавить мультипликативный масштабный коэффициент t к нему, так что ее координаты выглядят как

   0, 0 
   10t, 0 
   0, 10t 
   10t, 10t 
   7t, 3t 
   

3. Используйте shoelace formula, чтобы выяснить область, скажем f(t).

4. Решить уравнение многочлена f(t) = 30.0 для масштабного коэффициента t и связанных с ним координат вашего многоугольника.

Это должно дать вам многоугольник области, которую вы хотели (30.0).

Кстати, я предполагаю, что вы знаете форму многоугольника, иначе будет (бесконечно) множество решений, которые могут соответствовать вашей целевой области.