I know how to test whether 2 polygons intersect each other, but I was wondering where I can find the most efficient algorithm discovered so far for it. This applies to other algorithms too because I'm developing for mobile and need everything to be as efficient as possible.

I've had a pretty easy time finding all of the sorting algorithms since those are more math related I guess, but I've had a hard time finding the popular algorithms for stuff like polygon intersection.

Are there things such as algorithm databases or something that I can check with?

## 5 Replies - 1003 Views - Last Post: 20 October 2009 - 07:01 AM

### #1

# Where can I find the MOST efficient version of an algorithm?

Posted 08 September 2009 - 07:20 PM

##
**Replies To:** Where can I find the MOST efficient version of an algorithm?

### #2 Guest_Neumann*

## Re: Where can I find the MOST efficient version of an algorithm?

Posted 08 September 2009 - 07:32 PM

To find the MOST efficient algorithm you need to either:

a.) Test every possible algorithm out there for efficiency, then compare the results.

b.) Find the place that has already done that.

I hardly doubt that option b is realistic. I also think the same thing about option a.

I've worked with computational geometry on some basic level, and let me tell you, it has the most complex algorithms I've ever dealt with. Is the efficiency so crucial to you that you're willing to deal with such complexities (although I doubt you fully realize the complexities I'm talking about)? If your current algorithm works fine, leave it as is. When it starts to have a serious impact on the performance is when you should look for a better alternative.

a.) Test every possible algorithm out there for efficiency, then compare the results.

b.) Find the place that has already done that.

I hardly doubt that option b is realistic. I also think the same thing about option a.

I've worked with computational geometry on some basic level, and let me tell you, it has the most complex algorithms I've ever dealt with. Is the efficiency so crucial to you that you're willing to deal with such complexities (although I doubt you fully realize the complexities I'm talking about)? If your current algorithm works fine, leave it as is. When it starts to have a serious impact on the performance is when you should look for a better alternative.

This post has been edited by **Neumann**: 08 September 2009 - 07:34 PM

### #3

## Re: Where can I find the MOST efficient version of an algorithm?

Posted 08 September 2009 - 07:58 PM

also the MOST efficient algorithm depends on different factors such as the size of your input or how many elements are you gonna process. for example if you will compare Merge sort algorithm with insertion sort to know which one is more efficient you will find that if your arrays contains a large number of elements for example 1000000 elements, then for sure merge sort will win, but if you have an array of not so much elements then for sure insertion sort will win over..so determining the most efficient algorithm depends on different factors which you'll have to think about

### #4

## Re: Where can I find the MOST efficient version of an algorithm?

Posted 09 September 2009 - 03:59 AM

Efficiency can also be subjective, to a degree. For a mathematical application, I'd want the most accurate. However, for some kind of game I'll generally want the fastest that is accurate enough. Quite a different mindset.

If the interest is in graphics and games, you'll want a book that specializes in that subject. Many gaming innovations have come from creatively determining "accurate enough."

The now legendary fast inverse square root comes to mind.

If the interest is in graphics and games, you'll want a book that specializes in that subject. Many gaming innovations have come from creatively determining "accurate enough."

The now legendary fast inverse square root comes to mind.

### #5

## Re: Where can I find the MOST efficient version of an algorithm?

Posted 20 October 2009 - 06:36 AM

Premature optimization is bad.

### #6

## Re: Where can I find the MOST efficient version of an algorithm?

Posted 20 October 2009 - 07:01 AM

e_barroga, on 20 Oct, 2009 - 07:36 AM, said:

Premature optimization is bad.

To a degree. You definitely first want a solution that works first. However, if you can optimize as you go, that is the best case rather than going back and optimizing later. Sometimes though, you may need to come up with a solution first (especially if you are struggling) and then go back to optimize.

Page 1 of 1