Search code examples
c++mathiterationshapesmultimap

Iterate through points in an arbitrary shape

I've a multimap of points multimap<int,int> which surrounds (gapless) an arbitrary shape (a land area to be specific). How would I iterate through all points contained in the arbitrary shape?

I know that the multimap is not enough to determine the interior points, therefore I've got an additional point, that's inside of the shape (to determine inner and outer of the shape).

Further information: The points are sorted x-wise because multimap is a sorted container. All points are located in a grid, because I'm using bitmaps.

Solution

    1. If your points are farther apart than 1 pixel, then Points sorted by x coordinate are not going to be very helpful. Sort them such that points which should be connected are next to each other.

    2. Draw lines between the points

    3. Find a point thats inside and flood fill the shape. If you implement it yourself, you need to iterate over every pixel inside the shape for that.