## Finding Outer Vertices of Shapes

Member
Posts: 161
Joined: 2005.07
Post: #16
Quote:With your method, none of them are computed correctly.
I just inputted all your examples and the shadows were fine for all of them.

One thing that I'm wondering about though... in your code, you use s._points.at(i) to get the point at index i, but in mine, you use s._points[i] for some reason. Does that matter?
Luminary
Posts: 5,143
Joined: 2002.04
Post: #17
at() is range-checked; [] is not. That's the only difference, I think.
Member
Posts: 26
Joined: 2006.09
Post: #18
The dot product method is the fastest and easiest to do. I think the bug in your code is that you are taking the dot product between the edge direction and direction to one of the vertices. You should use the edge normal instead. The normal is (-y, x) or (y, -x) depending on how you choose to use it . Also not need to normalize if you are just test if the edge is backfacing or not.

Code:
```size_t    n = m_verts.size(); for(size_t i = 0; i < n; ++i) {     size_t j = (i+1) % n;     Vec2i    edge(m_verts[j].x - m_verts[i].x, m_verts[j].y - m_verts[i].y);     Vec2i    norm(-edge.y, edge.x);     Vec2i    dir(m_verts[i].x - m_x, m_verts[i].y - m_y);     if(Dot(norm, dir) > 0)     {         // font facing         dc.MoveTo(m_verts[i].x, m_verts[i].y);         dc.LineTo(m_verts[j].x, m_verts[j].y);     } }```

Also note that this method requires you to always have same winding of the polygons otherwise the dot product test will fail. The easiest way to check the polygon winding is to calculate the area and if it is negative, reverse you array of points.
Sage
Posts: 1,066
Joined: 2004.07
Post: #19
Thanks memon! That worked perfectly. I realized yesterday I was using the edge instead of the edge normal, but when I switched it even my rectangles didn't work right. Your code works perfectly for all my shapes so far. Thanks.