## 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.

Possibly Related Threads...
 Thread: Author Replies: Views: Last Post finding a training center - Heeeelp Glauter 1 4,011 Dec 26, 2011 12:30 PM Last Post: zenkimoto Adding lots of static shapes in Chipmunk - performance question TomorrowPlusX 3 8,659 Jul 11, 2011 01:39 PM Last Post: Skorche Finding an object by name markhula 2 5,550 Mar 29, 2011 08:08 AM Last Post: markhula Game rectangles & OpenGL vertices mk12 2 3,439 Sep 7, 2010 07:45 PM Last Post: mk12 Kind of a noob question - finding artwork within my .app?? Nethfel 2 3,573 Mar 8, 2010 08:00 AM Last Post: AndyKorth