10
$\begingroup$

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]

enter image description here

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 ]

enter image description here

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 ]

enter image description here

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ a simpler example: poly = Polygon@{{3, 3}/2, {3, 3}, {0,1}, {3, 1}, {2, 2},{3, 3}/2 };? $\endgroup$ Commented Sep 5, 2018 at 15:03
  • 2
    $\begingroup$ What does fixing mean? Possibly removing regions which can be removed without changing the area of the polygon? $\endgroup$ Commented Sep 5, 2018 at 16:36
  • $\begingroup$ @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. $\endgroup$ Commented Sep 5, 2018 at 16:52
  • $\begingroup$ @kirma, right. The last point is added to have a structure similar to the polygon in the question. $\endgroup$ Commented Sep 5, 2018 at 16:56
  • $\begingroup$ @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! $\endgroup$ Commented Sep 5, 2018 at 17:05

3 Answers 3

Reset to default
6
$\begingroup$

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

enter image description here

Simplify the boundary using an undocumented, internal function:

boundary = Region`Mesh`MergeCells @ boundary

enter image description here

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}]

enter image description here

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

fixPolygon[poly_Polygon] := With[ {boundary = Region`Mesh`MergeCells @ 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.}}]}

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ nice use of DiscretizeRegion! Brilliant! $\endgroup$ Commented Sep 8, 2018 at 7:01
2
$\begingroup$

Using OuterPolygon: (After v12.0, 2019)

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

enter image description here

It also works with the example in the comments.

Improve this answer
$\endgroup$
0
$\begingroup$

Just remove the last point, the polygon closes itself:

Region @ Polygon @ Most @ p

enter image description here

Improve this answer
$\endgroup$
0

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.