Ubah array boolean 2D menjadi poligon (bujursangkar)

Tantangan

Tulis sebuah program yang, diberi boolean array 2 dimensi (ekuivalen, bitmap monokromatik), menghasilkan serangkaian poligon yang menggambarkan garis besar wilayah yang “benar” (1).

Input diberikan sebagai urutan karakter '#'(hash), ' '(spasi) dan \n(baris baru). Garis mungkin berbeda panjangnya, dalam hal ini bagian yang hilang diasumsikan spasi. Keluaran harus berupa daftar (terpisah baris) poligon, setiap poligon diwakili oleh daftar koordinat (dipisahkan koma).

Contoh & Persyaratan

1. Koordinat harus terdaftar dalam urutan searah jarum jam. Memasukkan:

   #
   

   Output yang dapat diterima meliputi:

   (0,0), (1,0), (1,1), (0,1)
   
   (1,0), (1,1), (0,1), (0,0)
   
   (1,1), (0,1), (0,0), (1,0)
   
   (0,1), (0,0), (1,0), (1,1)
   

2. Wilayah yang terpisah harus mengembalikan banyak poligon. Memasukkan:

   # #
   

   Contoh output (output aktual harus terdiri dari dua baris):

   (0,0), (1,0), (1,1), (0,1)
   (2,0), (3,0), (3,1), (2,1)
   

3. Lubang-lubang dalam poligon harus terdaftar sebagai poligon terpisah, tetapi dalam urutan anti-jarum jam. Memasukkan:

   ###
   # #
   ###
   

   Contoh output:

   (0,0), (3,0), (3,3), (0,3)
   (1,1), (1,2), (2,2), (2,1)
   

4. Anda bebas memilih apakah simpul yang berdekatan secara diagonal bergabung atau tidak. Memasukkan:

   #
    #
   

   Contoh output:

   (0,0), (1,0), (1,1), (0,1)
   (1,1), (2,1), (2,2), (1,2)
   

   atau

   (0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)
   

5. Daftar koordinat tidak harus pendek secara optimal. Sebagai contoh:

   ##
   

   Output yang dapat diterima:

   (0,0), (2,0), (2,1), (0,1)
   
   // Redundant coordinates along a straight line are acceptable
   (0,0), (1,0), (2,0), (2,1), (1,1), (0,1)
   
   // Duplicate start- and end-point are acceptable
   (0,0), (2,0), (2,1), (0,1), (0,0)
   

Seperti biasa, program terpendek "menang".

Perl, 345 311 265 karakter

s!.!$i{$x++}=$&eq'#'!ge,$x=$r+=64for<>;sub a{$d+=@_||3;$d%=4;$y=$x%64;$z=$x>>6;$c.=", ($y,$z)";}for$x(keys%i){if($c=!$v{$x}&$i{$x}&!$i{$x-1}){$i{($x+=(1,64)[$d^3])-(64,65,1)[$d]}?$i{$x-(65,1,0,64)[$d]}?a 1:($x-=(64,1)[$d]):a while$d||!$v{$x}++;print substr$c.$/,3}}

Keterbatasan

Asumsikan bahwa input tidak lebih lebar dari 64 karakter (tetapi tingginya pada prinsipnya tidak terbatas). Ini dapat diperluas ke 512 atau 8192 atau kekuatan dua lainnya dengan mengubah konstanta yang relevan, membuat kode hanya sedikit lebih lama.

Versi yang sedikit lebih mudah dibaca

Beberapa kredit masuk ke mob karena baris pertama adalah saya menggunakan kembali idenya dalam laser . Selebihnya adalah pekerjaan saya sepenuhnya.

# Read “%i”nput (this line is essentially mob’s idea, see above)
s!.! $i{$x++} = $& eq '#' !ge, $x = $r += 64 for <>;

# Subroutine to add a vertex to the current polygon and change the current “$d”irection
sub a
{
    $d += @_ || 3;
    $d %= 4;
    $y = $x % 64;
    $z = $x >> 6;
    $c .= ", ($y,$z)";
}

for $x (keys %i)
{
    # Go to the next “upward-pointing” edge that we haven’t already “%v”isited.
    if ($c = !$v{$x} & $i{$x} & !$i{$x-1})
    {
        # We’re going in the “$d”irection of 0=up, 1=left, 2=down, 3=right
        $i{($x += (1,64)[$d^3]) - (64,65,1)[$d]}
        ?  $i{$x - (65,1,0,64)[$d]}
           ?  a 1               # take a 90° turn to the left
           : ($x -= (64,1)[$d]) # move straight ahead
        : a                     # take a 90° turn to the right

        # Only stop if the current “$d”irection is “up” and we encounter a “%v”isited edge
        # (which necessarily is the one we started from)
        while $d || !$v{$x}++;

        # Remove “1, ” and output this polygon
        print substr $c.$/, 3
    }
}

Suntingan

• (345 → 312) Sadar tidak perlu memperbarui $xketika mengambil belokan karena iterasi berikutnya sudah akan melakukannya
• (312 → 311) Ubah 1= turun, 2= kiri ke 1= kiri, 2= turun dan perbarui $dmelalui XOR alih-alih secara langsung
• (311 → 265) Hapus pengulangan ekspresi paling dalam dan gunakan array untuk menentukan parameternya

Python, 607 karakter

Kode berfungsi dengan menyimpan daftar batas yang ditemukan sejauh memproses simbol # dalam urutan input. Batas disimpan dalam tabel E yang memetakan tepi (4-tupel dari x_start, y_start, x_end, y_end) ke daftar tepi yang membentuk batas poligon. Saat kami memproses setiap # baru, ia dapat dihubungkan ke poligon di atas (p) atau ke kiri (q). Kode menemukan p dan q menggunakan E dan kemudian menggabungkan batas dari arus # (r) dengan p dan q, jika ada. Kasus di mana p == q menghasilkan lubang.

import sys
x=y=N=0
E={}
def P(L):
 if L:print ', '.join(map(lambda z:str(z[:2]),L))
while 1:
 r,a,b,c=[(x,y,x+1,y),(x+1,y,x+1,y+1),(x+1,y+1,x,y+1),(x,y+1,x,y)],(x+1,y,x,y),(x,y,x,y\
+1),sys.stdin.read(1)
 if not c:break
 p,q=E.get(a),E.get(b)
 if'#'==c:
  if p:
   i=p.index(a)
   if q:
    j=q.index(b)
    if p==q:
     if i<j:P(p[i+1:j]);p[i:j+1]=r[1:3]
     else:P(p[i+1:]+p[:j]);p[i:]=r[1:3];p[0:j+1]=[]
    else:p[i:i+1]=r[1:3]+q[j+1:]+q[:j]
   else:p[i:i+1]=r[1:]
  elif q:j=q.index(b);q[j:j+1]=r[:3];p=q
  else:p=r
  for e in p:E[e]=p
 x+=1
 if'\n'==c:y+=1;x=0
for L in E.values():
 if L:P(L);L[:]=[]