#### Archived

This topic is now archived and is closed to further replies.

# Simple inside convex polygon question

This topic is 5403 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

At gamastura there's an article about inside convex polygon testing for points. The first example confuses me a bit. Shouldn't the quad be splitted? If it looks like this, numbers are vertices. Letters are vectors. 1A2 D\B 4B3 then according to me first test create vector and normal for vector 3 to 1 if the point is on top side do the dotproduct test for B ans A else do the dotproduct test for C and D Shouldn't this give 3 multiplications less? http://www.gamasutra.com/features/20000210/lander_01.htm [edited by - __fold on September 2, 2003 5:49:46 AM]

##### Share on other sites
> Shouldn''t this give 3 multiplications less?

Sometimes yes, sometimes the opposite ;->

The standard algo presented by Jeff allows an ''early-out'' with each edge-test ( if the point is outside the edge, it must be outside the poly ). The splitting variant does not have this property for the split edge tests.

Once you factor in other complications ( the standard algo results in simpler, smaller code with less branching ) the standard algo will win out on average unless the input polygons have a very large number of vertices.

##### Share on other sites
The branching can be eliminated. My algo saves a dot product, a normal calculation and an vector subtraction.
It''s true though that my version must do an extra test before first exit. So it depends on how often the point will actually be inside the quad. If WCET only matters then my version would be nice.

But I know, it''s against the rules to not do calculations as late as possible.

• 32
• 12
• 10
• 9
• 9
• ### Forum Statistics

• Total Topics
631352
• Total Posts
2999483
×

## Important Information

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!