Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #5608

Re: Detecting four sided figures

Show key headers only | View raw

On 2015-08-07, Chad <cdalten@gmail.com> wrote:
> A description of the problem can be found here...
>
> http://www.reddit.com/r/dailyprogrammer/comments/3e5b0o/20150722_challenge_224_intermediate_detecting/
>
> Ihe question is what is a possible approach I would take to solve this
> problem.  Counting the number of pluses doesn't work and I can't seem to
> establish a relationship between the lines and stars that form a box. I also
> looked at the solutions and I have zero clue on the algorithm or algorithms
> they used to solve this problem. Ideas?

A four-sided figure occurs when an angle configuration like the following ABC:

  A              B
  +--------+-----+
  |
  |
  +
  |
  +
  | C
  +

Has a completing corner, such as this D:

  A              B
  +--------+-----+
  |              |
  |              |
  +              |
  |              +
  +              |
  | C            |
  +--------------+ D

For every + character in the diagram, enumerate all the possible angle figures which
have that character as their upper-left corner. Test which of these angle figures
have a completing corner: each of those is a four-sided figure. Count these.

For instance, the above A has 2x3 possible angle figures, since it is flanked by
a horizontal edge with two + characters, and a vertical edge with three + characters.

Connectivity testing can be performed by simple walks: start a given character
and march horizontally or vertically while you see only dashes, pipes and
pluses.

If the coordinates of C are (cx, cy) and those of B are (bx, by), then those of
D are necessarily (bx, cy).  The job is to test whether C connects
horizontally to D (unbroken path of dashes and pluses from (cx, cy) to (bx,
cy)) and similarly for C to D.

Once you know that C connects to D, or verify that it doesn't, you can cache
this knowledge so as not to repeat these scans. An initial scan thorugh the
figure could find all horizontal and vertical lines, and associate together the
vertices which they connect.  Then the subsequent computation reduces to a
graph problem.

For every vertex, we can have a is singly linked list of vertices which lie on
the same horizontal segment to the right, and another list of vertices which
lie on the same vertical below. Every diagram reduces to a DAG and the right
kind of combinatorial traversal of this DAG finds the four-sided figures.

Back to comp.programming | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Detecting four sided figures Chad <cdalten@gmail.com> - 2015-08-07 14:37 -0700
  Re: Detecting four sided figures Ben Bacarisse <ben.usenet@bsb.me.uk> - 2015-08-08 01:25 +0100
  Re: Detecting four sided figures Kaz Kylheku <kaz@kylheku.com> - 2015-08-08 01:05 +0000

csiph-web