Polygon border algorithm?

I have an array set of (x,y) values that define a polygon. The polygon is drawn based on the point's position * a pencil size. The thing is that i want to draw the border of such shape, ig开发者_JS百科noring the inner vertexes. See this example, the BLACK vertex are the ones i'm interested in, i want to get rid of the YELLOW ones.

I'd like to get the X in another array, ordered clockwise. Been thinking about evaluating every point to see if has a neighbor and where (north, south, east, west) but seems like too much crunching to check in every vertex and i believe must be another proven and more elegant algorithm.

Any tip?

---

Since your "points" are just little squares, it sounds like your inner points (those which don't contribute to the border of the shape) are just those where (x-1,y), (x+1,y), (x,y-1), and (x,y+1) are also all points.

You can do that test quickly by putting all of your points in a hashtable (or one of many other indexed structures).

Ordering clockwise just requires walking the border. You have to decide what you'd like to do about holes, if there are any.

---

Normally, a polygon is defined by an outline. That's an unfortunate format you have to deal with there.

If they're laid out like that (in rows with the same y coord) then you can just sort the array, first by x and then by y, then take the first point, the two points around any change in y, and the last point to form your outline.

If the real state of things is a little messier, then you might want to look into 'alpha shapes'. Some links: http://biogeometry.duke.edu/software/alphashapes/, http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html

---

Make sprite borders, place it same position every square and sorting oderlayout behind