CODEWITHSUNDEEP
mathgeometrycomputer-sciencecomputational-geometry
erathorus
erathorus

Reputation: 117

How to find polygons in a given set of points and edges?

Consider the following problem:

Given N points in plane and M line segments connecting them, find all polygons (convex or concave) that do not contain any other polygons inside.

For instance: Example

There are 5 polygons founded:

1 - 2 - 5 - 6

2 - 3 - 5

3 - 4 - 5

7 - 8 - 9

10 - 13 - 20 - 12 - 11

How can I identify these polygons and there corresponding vertices and edges? And what is the fastest solution for this?

Upvotes: 5

Views: 3141

Answers (1)

MBo
MBo

Reputation: 80187

Build graph with segment ends as vertices and segments as edges, then find cycles using DFS.

Note that the same edges might belong to multiple cycles (polygons) like your 2-5 and there might be many variants to select cycles. To exclude ambiguity, you can build fundamental set of cycles

Edit. As weston noticed in comments, resulted polygons might contains others. So sketch of more geometric approach:

Build lists of adjacency for graph.
Sort edges in ever list by polar angle.
Choose the most bottom vertex A.
If it's degree is 0, remove vertex, if 1, remove vertex and edge.
Otherwise get edge E with the smallest angle from this vertex.

Walk to pair vertex B.
Choose the most left edge F from B.
Move along to F edge into C.
If dead end, remove F and vertex C and return to B.

Repeat moving using left-hand rule until meet vertex A or dead end vertex.
In the walk process remove edges outgoing from vertices of degree 2 or mark them as used.

Upvotes: 2

Related Questions