4
$\begingroup$

Given a non-self-intersecting polygon made of straight segments how do you detect/trim sections of the polygon that are "thin"?

Example sectioning of a polygon

If an algorithm exists for this, then great! If not, then...

  1. I think the "correct" definition of "thickness" at a point on the edge is related to the smallest circle that touches that edge and some other part of the polygon.
  2. The thickness at the point where two lines meet is always zero so there will need to be some minimum allowed angle.

As for the algorithm.. some sort of checking every line against every other line? Some sort of convert to convex hulls first? Some sort of triangulation of the polygon?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

This was answered in this question using the python library "shapely". A general explanation is you shrink (sometimes called buffer) the polygon by some amount, grow/buffer the polygon by some % more than you shrunk it, then take the intersection of this new polygon and your original polygon.

The amount you shrink approximately defines how narrow a "hallway" can be before its removed. The % more you grow the polygon (called "cofactor" in the linked answer) approximately defines the angle of "spikes" that are allowed in the polygon (a bigger number means allowing sharper spikes).

Visual representation of algorithm

Improve this answer
$\endgroup$
5
  • $\begingroup$ I added an answer to the question you linked to that follows the same general idea but gives a resulting polygon that will be closer in shape compared to the input polygon than the original answer. $\endgroup$
    – Pieter
    Commented Aug 24 at 4:03
  • 1
    $\begingroup$ Some minor corrections to your explanation for clarity if others user read/use it: 1) you can do an intersection with the original polygon, not a union, 2) the amount you shrink is ~half of the minimum width you want to retain. $\endgroup$
    – Pieter
    Commented Aug 24 at 4:06
  • $\begingroup$ (@Pieter unless you suggest Christopher Pratt should edit the post accordingly, I prefer that you yourself edit in corrections to what you clearly identify as simple mistakes.) $\endgroup$
    – greybeard
    Commented Aug 24 at 9:52
  • $\begingroup$ It was indeed a suggestion @christopher pratt to update his post $\endgroup$
    – Pieter
    Commented Aug 24 at 10:29
  • $\begingroup$ My error, good catch. I updated the post. $\endgroup$
    – Christopher Pratt
    Commented Aug 24 at 22:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.