# 2D polygon recognition

This topic is 4474 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi, I am thinking about extracting concave polygons from a 2d image (see underneath) What I want to do is, you click into one of the enclosed zones and the program calculates the polygon surrounding that zone. One way I thought about is: a)find all black pixels of the image and treat them as nodes of an undirected graph. b) select all cycles with only 3 nodes, c) scan the previously selected nodes if they are horizontal, vectical or diagonal neighbours, if so merge them to a single node ( e.g.: the stair of black pixels once we got so far there are only the relevant nodes left. d) now we have to find all cycles of that graph, and check whether we can simplify them, e.g.: A->B and B->C point into the same direction so we can merge A-B-C to A-C without loosing details of the resulting polygon. e) now we have to split all relevant cycles( the concave polygons) into convex polygons and do a point in polygon check for the cursor coordinates. That the basic algorithm I thought of, however it appears to be computational expensiv Do you know any algorithms that could do the same thing in a more efficient manner? thx in advance

##### Share on other sites
1° The encompassing polygon is not unique.
2° Use an expanding polygonal non-convex contour, moving points "outward" (following a normal) until they hit something, then splitting edges into more edges until you reach appropriate accuracy. Then, split-and-expand some more, but ignoring edges inside the convex hull, until you get pixel-level accuracy.

2° Is the method generally used in image recognition, only it's simplified here by the fact that your contour is black and your zone is white.

##### Share on other sites
Thx, the 2nd method seems to be easy to implement too and it would solve another problem where another concave polygon is completely inside the one you picked

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634046
• Total Posts
3015222
×