Jump to content
  • Advertisement
Sign in to follow this  
Basiror

2D polygon recognition

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!