3
$\begingroup$

So for example, using only pixels to form the shapes, though that isn't required to meet the criteria (assume they are joined when on adjacent rows).

Meet criteria:

  ██
███
███

██
██
██████

 ███
████████
  ███

Do not meet criteria:

█ █
███

████████
███ ████

  █████
 ██   ██
  ██ ██

The criteria for being part of the subset of concave shapes, are

a) Concave

b) If you have a rectangle with the same orientation as the shape you can test if each corner of the rectangle is within the shape, and if they all are then you can conclude that the rectangle is fully "within" the shape, as in, no part of the rectangle is outside.

For example with b, you could show the final shape doesn't meet the criteria if the rectangle was such that each corner was just outside the "hole" in the centre.


Someone reasonably pointed out that the rectangle cannot have an orientation the same as the shape if the shape isn't made of pixels, i.e. all straight edges are in one direction or perpendicular to that direction. This would be a criterion:

c) All edges are straight and in one direction or perpendicular to that direction.

$\endgroup$
5
  • $\begingroup$ If the shape isn't made of pixels, how do you define "the orientation of the shape"? $\endgroup$
    – Mark S.
    Commented Jun 18, 2018 at 9:21
  • $\begingroup$ I don't understand criterion (b), do you mean "for any axis aligned rectangle, if all 4 corners are within the shape, so does the interior of the rectangle"? $\endgroup$ Commented Jun 18, 2018 at 9:44
  • $\begingroup$ @MarkS You're right, I address that in a new edit at the bottom, adding a third criteria. $\endgroup$
    – Shefeto
    Commented Jun 18, 2018 at 9:51
  • $\begingroup$ @achillehui sorry, as Mark S. pointed out the orientation of the rectangle cannot be compared to the shape unless it meets a third criteria, I've added that in an edit. Technically I should have them in a different order I suppose but I think it's understandable as is so I'm keeping timing clarity by keeping this order. $\endgroup$
    – Shefeto
    Commented Jun 18, 2018 at 9:53
  • 3
    $\begingroup$ I believe what you are looking for is an orthogonally convex set, or more specifically, a nonconvex but orthogonally convex set. $\endgroup$
    – user856
    Commented Jun 18, 2018 at 18:14

1 Answer 1

1
$\begingroup$

According to Rahul in this comment:

I believe what you are looking for is an orthogonally convex set, or more specifically, a nonconvex but orthogonally convex set.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .