# Detect and fix invalid polygon

I have a polygon given by

poly = Polygon[
{{2437.21, 166.705}, {2437.38,166.856}, {2440.37,163.438}, {2435.84,159.581},
{2442.18,152.113}, {2431.45,142.989}, {2420.63,153.885}, {2428.72,160.067},
{2418.95,168.237}, {2435.2,183.216}, {2446.11,174.504}, {2437.21,166.705}}]


which looks good when rendered:

Graphics[poly]


However, this shape cannot be used for Region-related operations as it is "ill-defined" with an interior line:

Graphics[
{
FaceForm[None], EdgeForm[Black], poly,
Red, PointSize[Medium], Point@@poly
},
Frame->True
]


whose zoomed-in view is like this:

Graphics[
{
FaceForm[None], EdgeForm[Black], poly,
Red, PointSize[Medium], Point@@poly
},
Frame->True,
PlotRange->{{2437, 2438}, {166, 168}},
PlotRangeClipping->True
]


My question is: How can I detect such "ill-defined" polygons and fix them?

Edit:

As more people are concerning about the definition of a valid polygon, I just cite that used by the python package shapely here:

Rings of a valid Polygon may not cross each other, but may touch at a single point only.

Also, I have very little expertise in computational geometry; my intention was to use Region-related functions (e.g., RegionMeasure) with these polygons, where I came across the kernel crash and then discovered such "ill-defined" polygons.

• a simpler example: poly = Polygon@{{3, 3}/2, {3, 3}, {0,1}, {3, 1}, {2, 2},{3, 3}/2 };?
– kglr
Commented Sep 5, 2018 at 15:03
• What does fixing mean? Possibly removing regions which can be removed without changing the area of the polygon? Commented Sep 5, 2018 at 16:36
• @kglr Frankly, your polygon is twice ill-defined, as is the one in the question: you don't need to repeat the starting point as the last point. Commented Sep 5, 2018 at 16:52
• @kirma, right. The last point is added to have a structure similar to the polygon in the question.
– kglr
Commented Sep 5, 2018 at 16:56
• @kglr Oh, sure. I must say this problem still requires a some improvement on the definition of what is ill-defined in practice... your polygon is evil, but the one in question with real-valued coordinates is more fuzzy in this regard! Commented Sep 5, 2018 at 17:05

## 3 Answers

I expect there's a simpler way to do this, but here is a possibility. FIrst, discretize the polygon, and then find the boundary:

boundary = RegionBoundary @ DiscretizeRegion @ poly


Simplify the boundary using an undocumented, internal function:

boundary = RegionMeshMergeCells @ boundary


Notice the defect is gone. Convert the output to a BoundaryMesh and extract the polygon:

simple = MeshPrimitives[
BoundaryMeshRegion[MeshCoordinates[boundary], MeshCells[boundary, 1]],
2
]


{Polygon[{{2440.37, 163.438}, {2437.38, 166.855}, {2446.11, 174.504}, {2435.2, 183.216}, {2418.95, 168.237}, {2428.72, 160.067}, {2420.63, 153.885}, {2431.45, 142.989}, {2442.18, 152.113}, {2435.84, 159.581}}]}

The fixed polygon:

Graphics[{FaceForm[None], EdgeForm[Black], simple}]


And finally, here are the above steps packages as a function:

fixPolygon[poly_Polygon] := With[
{boundary = RegionMeshMergeCells @ RegionBoundary @ DiscretizeRegion @ poly},

MeshPrimitives[
BoundaryMeshRegion[MeshCoordinates[boundary], MeshCells[boundary, 1]],
2
]
]


Another example using a polygon from the comments:

fixPolygon @ Polygon @ {{3, 3}/2, {3, 3}, {0,1}, {3, 1}, {2, 2},{3, 3}/2}


{Polygon[{{3., 3.}, {0., 1.}, {3., 1.}, {2., 2.}}]}

• nice use of DiscretizeRegion! Brilliant! Commented Sep 8, 2018 at 7:01

Using OuterPolygon: (After v12.0, 2019)

p2 = OuterPolygon@poly

Graphics[{FaceForm[None], EdgeForm[Thin], p2, Red, Point@ \
PolygonCoordinates@p2}]


It also works with the example in the comments.

Just remove the last point, the polygon closes itself:

Region @ Polygon @ Most @ p