how to get the points inside the polygon?

[jojo41300000]

Hi,

Is anyone know that how to get the x and y points inside the polygon using C++ program?

I have the given polygon data to draw the polygon, but i don't know how to get all the points inside the polygon.

Eg. Let's say we have 5 points to draw a polygon.

                 Polygon
                  ---------------------
                 |  Region A          /
                 |                   \
                 \--------------------  
 

In above polygon, I am trying to get all the integer points(x and y coordinates) inside the polygon.

Above polygon is just to show you as example. In reality, the polygon is not that simple and really complex.


Any algorithm or ideas to get the points?

Thanks.

-Jason

[RRick]

What you're describing is a polygon fill technique used in computer graphics. One of the most common fill algorithms is the scan-line algorithm. Also, there are different ways to define polygons that allows you to define polygons with holes and self intersections. A book on basic computer graphics algorithms should have a chapter or two devoted to this topic.

The general purpose scan algorithms use a list of edges (or buckets) to define the line segments inside a polygon for each integer line that intersects the polygon. This technique should be good for integer or double sized vertices. There are a lot of variations on this algorithm so find one that fits your needs. There is probably a graphics library out there with a scan algorithm that you use and/or modify.

[jojo41300000]

What you're describing is a polygon fill technique used in computer graphics. One of the most common fill algorithms is the scan-line algorithm. Also, there are different ways to define polygons that allows you to define polygons with holes and self intersections. A book on basic computer graphics algorithms should have a chapter or two devoted to this topic.

The general purpose scan algorithms use a list of edges (or buckets) to define the line segments inside a polygon for each integer line that intersects the polygon. This technique should be good for integer or double sized vertices. There are a lot of variations on this algorithm so find one that fits your needs. There is probably a graphics library out there with a scan algorithm that you use and/or modify.

Thanks alot. I
The algorithm works only on kind of simple polygon.
It doesn't fill completely to very complex (self intersecting) polygon.

Is there any idea why it doesn't fill completely? ( I use polygon fill alg)

[RRick]

It all depends on the algorithm. Some algorithms make assumptions about the polygon for simplicity and calculations. There is definitely more than one polygon fill algorithm.

Also, there are two schools of thought on self intersecting polygons. One says to switch the interior fill on and off as each intersection line is crossed. This results in a complex polygon with interior holes. The other idea says that all of the interior should be filled no matter how many times the polygon intersects itself.

While it is nice to have the most capable and complex algorithm available, sometimes its better to get the simplest one that does the job.