ASCII-art polygons to GeoJSON coordinates

Question

We're going to turn ascii art versions of polygons into their equivalent GeoJSON.

The ASCII shape language

The input ASCII language only has 3 possible characters:

• * signifies a vertex
• - signifies a horizontal line
• | signifies a vertical line

A * will never be directly adjacent to another * (but may be diagonal to one). A * shall have exactly two lines adjacent to it, either a - to the left or right of it, or a | to the top or bottom. There will never be a | to the left or right of a *, and consequently, never a - directly above or below a *. It is possible to have a vertex along a line, e.g. -*-.

Each input only contains one "ring". There are no multi-part polygons, or polygons with holes.

The input is minimal. For example, there are no extra leading or trailing blank lines or trailing white spaces.

For example, some valid shapes are:

*--*
|  |
*--*

*--*
|  |
|  *--*
|     |
*-----*

  *--*
  |  |
*-*  |
|  *-*
|  |
*--*

The coordinate language

The above shapes shall be converted into their equivalent coordinates. The top left corner of the ASCII art is (0,0). The first coordinate is the x-axis.

For example, the 3 shapes above would turn into the following coordinates:

[[0,0],[3,0],[3,2],[0,2],[0,0]]

[[0,0],[3,0],[3,2],[6,2],[6,4],[0,4],[0,0]]

[[2,0],[5,0],[5,3],[3,3],[3,5],[0,5],[0,2],[2,2],[2,0]]

Note that other representations are possible too, depending on which coordinate you start with. Continuing with GeoJSON convention, the coordinate ring shall be clockwise.

Input/output

Take your input via any of the standard methods. The input may be:

• A string containing only the characters *, -, |, \n or
• or an array of strings where each string represents a line.

Output shall be via any standard format. The output shall be an n-by-2 dimensional JSON array. Any amount and type of whitespace is allowed in the resulting JSON.

---

This is code-golf, so fewest bytes wins.

Answer 1

Charcoal, 52 bytes

ＷＳ⟦ι⟧⊞υ⟦⌕θ*⁰⟧Ｊ⊕⌕θ*⁰ＷΦ⁴‹ ⊟ＫＤ²✳⊗κ«✳⊗⌊ι ≡ＫＫ*⊞υ⟦ⅈⅉ⟧»⎚⭆¹υ

Try it online! Link is to verbose version of code. Takes input as a list of newline-terminated strings. Explanation:

ＷＳ⟦ι⟧

Copy the input to the canvas.

⊞υ⟦⌕θ*⁰⟧

Start at the top left corner of the shape.

Ｊ⊕⌕θ*⁰

Jump to the top edge of the shape.

ＷΦ⁴‹ ⊟ＫＤ²✳⊗κ«

Repeat while there's at least one orthogonally adjacent shape part.

✳⊗⌊ι 

Overwrite the current shape part, moving to the next one.

≡ＫＫ*

If this is a *, then...

⊞υ⟦ⅈⅉ⟧

... record the current coordinates.

»⎚⭆¹υ

Clear the canvas and pretty-print the final list of coordinates.

Answer 2

J, ^{92 90 85 75} 67 bytes

[:(-.~{.,~{.,((]~.@,[#~1=(|@-{:))^:_{.)@}.)&($j./@#:I.@,)/'* '~:"{]

Try it online!

idea

1. Get positions of all non-space characters in "reading" order (left to right, top to bottom). This is easy using a standard idiom, and returns the positions as complex numbers.
2. Next, we need to get them in "ring" order. To do that, seed a list with the upper-leftmost position and re-build the list from step 1 as follows:
   • Add to the most recently added list element the four compass directions, as complex numbers, giving 4 new candidates for "next" list element.
   • Remove any candidates not in the list from step 1
   • Remove any candidates that would result in a repeat in the list we're building
   • The first seeded element will result in 2 candidates (we pick the first arbitrarily), but all subsequent elements will have only one "next" candidate.
   • Repeat this process "list length - 1" times. We now have the list from step 1 in ring order. We add the first element to the tail.
3. Remove all elements from step 2's list associated with -| positions, resulting in a list of just the * positions, but in "ring" order. This is our answer.

Answer 3

05AB1E, 45 43 bytes (non-competing†)

^{† My approach assumed -*- vectors weren't a thing, since I look for pairs of corner-vectors, making my entire solution worthless once that was added in as a (new) rule of the challenge.. :/}

εNUεNX)]Dζ«€`ʒ'*å}€¦2ôœ.Δðý©À`åθ®üåOP*}€`ÙĆ

-2 bytes by using 2x €` and θ instead of 2x í€` and н.

Input as a list of lists of characters.

Try it online or verify all test cases. (Will time out for test cases with 10 or more vertices due to the œ builtin.)

Explanation:

Step 1: Pair each character with it's coordinate:

ε          # Map over each row of the (implicit) input:
 NU        #  Store the 0-based index of the current row in variable `X`
 ε         #  Inner map over each inner cell of the current row:
  N        #   Push the cell's index
   X       #   Push the row's index from variable `X`
    )      #   Wrap the cell-value, cell-index, and row-index into a triplet-list
]          # Close the nested maps

Try just step 1 online.

Step 2: Merge the transposed result, since we want to check all *-* and *|* connections separately:

D          # Duplicate the result
 ζ         # Zip/transpose; with " " as implicit filler if the input isn't a rectangle
           # (which will be removed again with the filter later on)
  «        # Merge the regular and transposed lists together

Try just the first 2 steps online.

Step 3: Convert it to a flattened list of all pairs of coordinates for the vertices *, first for all *-* and then also for all *|*:

€`         # Flatten it one level down
           # (implicitly reverses the values of each row, but we'll fix this later)
ʒ          # Filter this list of triplets by:
 '*å      '#  Does the triplet contain "*"
}€¦        # After the filter: remove all first items (the "*") of the triplets
   2ô      # Split this list of pairs into pairs

Try just the first 3 steps online.

Step 4: Find the first valid permutation of this list of pairs:

œ          # Get all permutations of this list of pairs of coordinates
 .Δ        # Find the first which is truthy for:
   ðý      #  Join each inner-most coordinate with a space delimiter to a string
           #  (necessary because 05AB1E lacks a contains for pairs)
     ©     #  Store this in variable `®` (without popping)
      À    #  Rotate it once towards the right
       `   #  Pop and push all pairs of strings separated to the stack
        å  #  Check for both values inside the top pair of strings whether they're in
           #  the pair below it
         θ #  Only keep the last truthy/falsey check of this
     ®     #  Push list `®` again
      ü    #  For each overlapping pair of pairs of strings:
       å   #  Check for the values in the second pair if they're in the first pair
        O  #  Sum each pair of truthy/falsey values
         P #  Take the product, to check whether just one in each was truthy
     *     #  Check that both checks were truthy
 }         # Close the find-first

Try just the first 4 steps online.

Format it to the intended output:

€`         # Flatten it one level down (in reversed order again)
  Ù        # Uniquify this list of pairs
   Ć       # Enclose; append its own head
           # (after which the resulting list of pairs is output implicitly as result)

Try the entire program online.

Answer 4

Jelly, 23 bytes

n⁶ŒṪŒ!ạƝ§$ÞḢfœẹ”*$ṭ@Ṃ$’

Try it online!

This is a monadic link that accepts an array of lines as input and produces a 2D array (which the interpreter prints in the correct format) as output. The solution always starts with the first non-space character, which must be an asterisk.

Note that this solution is very slow, so the only valid input that will terminate within a minute on TIO is a 3x3 square. However, this program should work for any input where the non-space characters form a Hamiltonian cycle and the first non-space is an asterisk.

Explanation

List all permutations of the non-space characters' coordinates:

ŒṪ and Œ! order their results lexicographically (according to the input's order in Œ!'s case), so this step's output is ordered lexicographically.

n      # Not equal
 ⁶     # " "
  ŒṪ   # Multidimensional indices of truthy values
    Œ! # Permutations (ordered lexicographically according to the input)

Find the valid permutation starting with the first non-space character:

Listing all permutations and then finding a valid one is a similar idea to step 4 in @KevinCruijssen's answer, although the details are very different.

Consider the list of Manhattan distances of adjacent elements of a permutation. (The Manhattan distance from (a, b) to (c, d) is |a-b| + |c-d|). No coordinate is repeated, so each distance is positive. Thus, the lexicographically minimum possible distance list is [1, 1, ..., 1]. This distance list means two adjacent points in the permutation have distance 1, so this permutation is valid or reverse-valid (i.e. the counterclockwise version of a valid permutation). Thus, sorting the permutations by their distance lists puts all of the (reverse-)valid permutations at the beginning.

Þ is implemented using Python's sorted function, which is guaranteed to be stable, so among the (reverse-)valid permutations, the lexicographically minimum one still comes first. This will be one that starts with the first two non-space characters in order. These characters are the first and second non-space characters on the top row (excluding space-only rows), so the first permutation must be clockwise, making it valid.

ạƝ§$ÞḢ
ạ      # Absolute-value difference
 Ɲ     # Apply to each adjacent pair
  §    # Sum
   $   # Group ạƝ§ as a monad
    Þ  # Sort
     Ḣ # First item

Filter non-asterisk coordinates:

fœẹ”*$
f      # Filter
 œẹ    # Multidimensional indices of
   ”*  # "*"
     $ # Group œẹ”* as a monad

Repeat the first coordinate (which is also the minimum coordinate in lexicographic order) and switch to 0-based indexing:

ṭ@Ṃ$’
ṭ     # Tack
 @    # Transpose arguments
  Ṃ   # Minimum
   $  # Group ṭ@Ṃ as a monad
    ’ # Decrement

Answer 5

jq -Rn, 166 bytes

[inputs|explode]|[tostream|select(.[1]>32)]
|reduce keys[]as$k(.;.[$k]as[[$y,$x]]|.[$k+1:]
|=sort_by(.[0]|hypot(.[0]-$y;.[1]-$x)))+.[:1]
|map(select(.[1]<45)[0]|reverse)

(newlines added for readability aesthetic pleasure)

Try it online!

Explanation:

[ inputs                             #  read each input line as raw string
| explode                            #  make them an array of ascii codes
]                                    #  collect line arrays into row array
| [ tostream                         #  convert items into path and value
  | select(.[1] > 32)                #  only keep non-empty cell values
  ]                                  #  collect them into a cell array
| reduce keys[] as $k (.             #  iterate over pivot cell indices
    ; .[$k] as [ [$y,$x] ]           #    destructure pivot cell into coords
    | .[$k+1:] |= sort_by(.[0]       #    sort remaining slice of cells wrt
        | hypot(.[0]-$y; .[1]-$x)    #      Euclidean distance to pivot cell
      )                              #    (hor or ver adjacency always wins)
  ) + .[:1]                          #  repeat the initial cell at the end
| map(                               #  prepare some cell items for output
    select(.[1] < 45)[0]             #    only keep paths of vertex cells
    | reverse                        #    turn row/col path into x/y coords
  )

Answer 6

Python 3, 244 233 bytes

Different approach, actually works

def g(a,o=[]):
 b=c=(0,0)
 while[b]!=o[1:2]:x,y=b;s=[(q,r)for q,r in((x+1,y),(x,y+1),(x-1,y),(x,y-1))if(len(a)>r>=0<=q<len(a[r])and a[r][q]or' ')in'-|*'and (q,r)!=c];o=a[y][x]=="*"and o+[(x,y)]or o;c=b;b=s and s[0]or(x+1,y)
 print(o)

Try it online!

Ungolfed

def g(a,o=[]):
 b=c=(0,0)                         # set starting point b and previous point c to (0,0)
 while[b]!=o[1:2]:                 # continue until we have passed the first point a second time
  x,y=b;
  s=[
   (q,r) for q,r in (
    (x+1,y),                        # east point
    (x,y+1),                        # south point
    (x-1,y),                        # west point
    (x,y-1)                         # north point
   ) 
   if (
    len(a)>r>=0                     # point is in y bounds of array
    and len(a[r])>q>=0              # point is in x bounds of row
    and a[r][q]                     # then character at point
    or ' '                          # else ' ' 
   ) in '-|*'                       # only include points where the character is "*", "-", or "|"; 
   and (q,r)!=c                     # exclude the point we just came from
  ];
  o=a[y][x]=="*"and o+[(x,y)]or o;  # if the current character is "*", add to output list
  c=b;                              # set previous point (c) to current point
  b=s and s[0]or(x+1,y)             # if we found "*", "-", or "|", move to that point; else, stay in row and move forward one place on the x-axis
 print(o)                           # return the output list