Найти площадь наибольшего выпуклого многоугольника

29

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

  • каждая вершина находится в списке
  • ни один элемент списка не содержится в многоугольнике.

Пример:

(0, 0) (8, 0) (0, 1) (3, 1) (7, 1) (1, 2) (5, 2) (9, 2) (2, 3) (5, 3) (7, 3) (3, 4) (5, 5) (11, 5)

Визуализация:

o       o
o  o   o
 o   o   o
  o  o o
   o
     o     o

Самый большой выпуклый многоугольник, который вы можете сделать из этого:

o     
o  o  
 o   o
  o  o
   o
     o

С площадью 12.


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

Кроме того, вы должны использовать какой-то алгоритм, а не просто перебор всех подмножеств точек. Чтобы обеспечить это, ваша программа должна решить список из 50 вершин за минуту на современном ПК.

Самый короткий код в байтах побеждает.

orlp
источник
Знаете ли вы быстрый алгоритм для худшего случая?
xnor
3
Если вы хотите установить ограничение по времени на 100 вершин, вам, вероятно, следует включить хотя бы один такой тестовый пример (в идеале несколько, например, один, где все 100 вершин являются частью решения, один, где 99, и один, где только 10) ,
Мартин Эндер
@ MartinBüttner К сожалению, я не могу сгенерировать этот контрольный пример, поскольку у меня нет работающей реализации. Проблема довольно сложная :)
orlp
@xnor Несколько примеров можно найти здесь .
orlp
"округлено до двух цифр после десятичной точки"?
DavidC

Ответы:

12

Javascript ES6, 738 байт

((V,C,L,r,k,n,A,G,F,e,i,j,q)=>p=>{p=p.map((p,i)=>({i:i,x:p[0],y:p[1]}));A=(f,p,a,b,v,i)=>{for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))return 1};G=(p,i,a)=>{for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=(p,s,l,f,a,b,v)=>(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A((a,b)=>C(a,b)?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b),p,a,b)?0:(p=(v=V(a,b),p[k](x=>C(v,V(a,x))>=0)),A((a,b)=>C(a,b)>0,p,b,f)?0:(p.map(q=>F(p[k](r=>q!==r),[...s,q])),s[2]&&!p[n]&&!e[b.i][f.i]?G(s):0)));e=p.map(x=>p.map(y=>x===y));for(i=p[n];i--;){for(j=i;j--;){q=p[k]((p,x)=>x-i&&x-j);F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)})((a,b)=>({x:b.x-a.x,y:b.y-a.y}),(a,b)=>a.x*b.y-a.y*b.x,v=>v.x*v.x+v.y*v.y,0,'filter','length')

Вот версия ES5 или менее, которая должна работать в большинстве браузеров и узлов без подстройки: 827 байт

eval("(%V,C,L,r,k,n,A,G,F,e,i,j,q){@%p){p=p.map(%p,i){@{i:i,x:p[0],y:p[1]}});A=%f,p,a,b,v,i){for(i=p[n],v=V(a,b);i--;)if(f(v,V(a,p[i])))@1};G=%p,i,a){for(i=p[n]-1,a=C(p[i],p[0]);i--;)a+=C(p[i],p[i+1]);if((a/=2)>r)r=a};F=%p,s,l,f,a,b,v){@(l=s[n],f=s[0],a=s[l-2],b=s[l-1],e[a.i][b.i]||A(%a,b){@C(a,b)!=0?0:a.x<0==b.x<0&&a.y<0==b.y<0&&L(a)>L(b)},p,a,b)?0:(p=(v=V(a,b),p[k](%x){@C(v,V(a,x))>=0})),A(%a,b){@C(a,b)>0},p,b,f)?0:(p.forEach(%q){@F(p[k](%r){@q!==r}),s.concat([q]))}),s[2]&&p[n]==0&&!e[b.i][f.i]?G(s):0)))};e=p.map(%x,i){@p.map(%y,j){@i==j})});for(i=p[n];i--;){for(j=i;j--;){q=p[k](%p,x){@x!=i&&x!=j});F(q,[p[i],p[j]]);F(q,[p[j],p[i]]);e[i][j]=e[j][i]=1}}console.log(r)}})(%a,b){@{x:b.x-a.x,y:b.y-a.y}},%a,b){@a.x*b.y-a.y*b.x},%v){@v.x*v.x+v.y*v.y},0,'filter','length')".replace(/%/g,'function(').replace(/@/g,'return '))

Код возвращает анонимную функцию. В качестве параметра он принимает массив точек, например [[0,1],[2,3],[4,5]]. Чтобы использовать его, вы можете поместить var f=перед ним, или, если вы хотите использовать его из командной строки, добавить (process.argv[2].replace(/ /g,'').slice(1,-1).split(')(').map((x)=>x.split(',')))в конец, и назвать его какnode convpol.js '(1,2)(3,4)(5,6)'

Спасибо за вызов! Так как эталонной реализации нет, я не могу доказать, что это правильно, но это согласуется, по крайней мере, для перестановок списка точек. Я почти не думал, что это сработает, поскольку версии с отладочным кодом, даже отключенным, были слишком медленными с экспоненциальным увеличением времени. В любом случае, я решил сыграть в гольф, и мне было приятно увидеть, что на моей машине он опустился до 2 секунд и набрал 50 очков. Он может рассчитать примерно 130 баллов за 1 минуту.

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

объяснение

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

  1. Начните с пары точек и списка всех остальных точек.
  2. Если текущая пара точек проходит точно через любую точку в списке, остановитесь.
  3. Отфильтруйте все точки текущей пары по часовой стрелке, так как они сделают многоугольник вогнутым.
  4. Для всех оставшихся точек сделайте следующее:
    1. Если линия от этой точки до первой точки цепи проходит или закрывает какие-либо точки против часовой стрелки, пропустите эту точку, поскольку любые многоугольники будут заключать эту точку.
    2. Добавьте эту точку в цепочку, вернитесь к шагу 1 с текущей цепочкой и списком точек.
  5. Если не осталось ни одной точки и цепочка имеет не менее 3 точек, это допустимый выпуклый многоугольник. Запомните наибольшую площадь этих полигонов.

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

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

ricochet1k
источник
2
+1, это удивительный ответ. Вы могли бы заменить ===и !==на ==и !=, но я не могу быть уверен, не понимая ваш код ...
Jrich
1
Благодарность! Эти конкретные === и! == сравнивают объекты, так что нет, к сожалению. Раньше сравнивали индексы, но (x,i)=>p.i==i(13 символов) немного дольше, чем x=>p===x(8 символов) даже после оптимизации.
ricochet1k
2
Есть объяснение для вас @Lembik
ricochet1k
1
Вы, кажется, избили запись O (n ^ 3), упомянутую в комментариях к связанному вопросу SO!
1
Хорошо, я добираюсь до того места, где я не верю, что это возможно меньше, чем O (n ^ 3). Я очень плохо знаком с алгоритмической сложностью.
ricochet1k