1

Consider the picture :

enter image description here

Given the black "irregular line" segments, I want to have the green boundary surrounding them.

My Attempt to solve :

Note, that I need to capture the concavity. Thus the convex hull algorithm will not work. I have used some interpolations, to draw the straight line segments indicated by overlayed red stripes. Then I attempted to run a sweep algorithm. These stripes are roughly parallel, if that helps.

That is, their headings lay within some small interval.

Heading H in { angle alpha - x , angle alpha +x } union { angle alpha - x + 180 , angle alpha +x+ 180 } for some small x

However, it needs to be guaranteed, that the green boundary should not intersect any red lines.

So, my naive attempt was :

  1. Start at leftmost vertex of all lines.
  2. Pick the line attached to the vertices. (if more vertices, then take the top most and bottom most)
  3. Use this line to "partition" the plane. (or two lines or two "separatices", if 2 vertices)
  4. Pick the next leftmost unvisited vertices.
  5. See if the vertex lies above the top separatrix or below the bottom separatrix.
  6. If above the top separatrix, add it to a set called "top chain", if below the bottom one, the add to bottom chain.

But this runs into problems.

The problem

To determine whether the newly picked point is at the top or at the bottom of a separatrix, I use the vector product method. But consider this :

enter image description here

Imagine you are at the green square. Your separatrix now is the black line, vector pointing to the left, as the arrow shows.

At this stage, you compare this with the green vector showing the next vertex to be picked on the blue line. The vector method, intended to measure angles between -Pi to Pi will consider this a negative value. Thus the point, although necessary, will not be picked up.

If you reverse the direction of the vector, then the Magenta line will not be picked up.

Question

How to efficiently solve this problem? I am using D, so bonus if there is a D library capable of this.

Sean
  • 789
  • 6
  • 26
  • You say that you need to capture the concavity, yet the headline is about drawing a *non-concave* shape. These are not compatible, so which is it? – John Bollinger Mar 20 '21 at 22:11
  • draw a concave shape. my bad. Typo – Sean Mar 20 '21 at 22:13
  • 1
    Ok. In that case, how is the specific green line you're after determined? It is not the minimum-area shape covering all the lines. In fact, I don't think there *is* a minimum-area shape, because the original lines do not fully enclose any area. With concavity allowed, I think you can find polyhedra with area arbitrarily close to zero that cover all the lines. – John Bollinger Mar 20 '21 at 22:18
  • arbitrarily close is good enough for me, but I need an algorithm and detailed explanation, please. – Sean Mar 20 '21 at 22:19
  • 3
    How Long Is the Coast of Britain? – spinkus Mar 20 '21 at 22:24
  • 1
    The minimal concave shape that covers the black segments will exactly wrap all black segments, plus have zero-area connections between each non-overlapping black segment. – Vladimir Panteleev Mar 20 '21 at 22:26
  • @semisecure . thank you. that give me an idea, but still pointing me to some simple to understand algorithm will be absolutly wonderful – Sean Mar 20 '21 at 22:26
  • @semisecure oh. ****. I am stupid ****. I got it. Thank you soooooooooooooooooo much. I owe you a beer. – Sean Mar 20 '21 at 22:31
  • 1
    [This is what the minimal area result looks like](https://dump.cy.md/bb56f6f2693907874def8d6719409ef1/22%3A33%3A34-upload.png). It's probably not what you're looking for, since it doesn't look a lot like your image. You would need to define some additional constraints to do that, like, an upper bound on perimeter or number of straight-line edges. – Vladimir Panteleev Mar 20 '21 at 22:34
  • I solved it by laying a grid on it, and rejecting the squares which does not contain anything, then tracing the boundary of the resulting "truncated checkerboard". – Sean Mar 20 '21 at 23:40
  • @Sean so you used 2D density map and then polygonize the output simialr to [Finding holes in 2d point sets?](https://stackoverflow.com/a/21884021/2521214) – Spektre Mar 21 '21 at 06:44
  • @Spektre Yes. With special consideration taken for empty ells that are diagonal to each other causing a "pinch" in the boundary, where two edges that should be parallel end up touching each other. – Sean Mar 21 '21 at 20:30

1 Answers1

1

Filling concavities is a somewhat arbitrary operation. Have a look at Alpha-shapes, a generalization of the convex hulls.

https://en.wikipedia.org/wiki/Alpha_shape