8
$\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$
    – kglr
    Sep 5 '18 at 15:03
  • 2
    $\begingroup$ What does fixing mean? Possibly removing regions which can be removed without changing the area of the polygon? $\endgroup$
    – kirma
    Sep 5 '18 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$
    – kirma
    Sep 5 '18 at 16:52
  • $\begingroup$ @kirma, right. The last point is added to have a structure similar to the polygon in the question. $\endgroup$
    – kglr
    Sep 5 '18 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$
    – kirma
    Sep 5 '18 at 17:05
5
$\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
  • $\begingroup$ nice use of DiscretizeRegion! Brilliant! $\endgroup$
    – sunt05
    Sep 8 '18 at 7:01
-2
$\begingroup$

Just remove the last point, the polygon closes itself:

Region @ Polygon @ Most @ p

enter image description here

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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