Author Topic: [SOLVED] I know what I want, just not what it's called (point density algorithm)  (Read 1835 times)

0 Members and 1 Guest are viewing this topic.

Offline montymintypieTopic starter

  • Beginner
  • *
  • Posts: 2
  • Helpful? 0
Hi all! :)

First, a little background:
I'm currently in first year engineering at uni, and our first project is to create an autonomous watercraft. It has to collect ping pong balls scattered around a tank. After a time working in 'dumb mode' (bouncing off walls using bump switches) it goes into 'smart mode', where the proper analytical stuff happens.

Basically, I make a scan of the environment using the IR sensor and then determine where the ping pong balls are by using a simple distance comparison between points using the cosine rule.

The thing I'm having trouble with is trying to make or find an algorithm that determines where would be the best place to head to get the most ping pong balls. I've got an array with angles and distances to each ball, so I can easily convert to an x/y grid of points, I just don't know how to analyse these points to work out where is the best place to go.

I have a big feeling that something like this already exists, as it just needs to determine the most densely packed region of points in a given field. I just have no clue on what I should be searching for - all the stuff I've found so far is either for pathfinding around obstacles or a travelling salesman style issue. I've also forgotten a lot of the statistical things I learnt in high school so I'm not sure if it would be of any use.

I'm trying not to reinvent the wheel here, because I'm sure something like this has been made before - I just need your help to tell me what I should be looking for.

Thanks in advance!
Will T

P.S. I'll do my best to supply extra information if it's needed, such as diagrams, tables etc. :)
« Last Edit: May 11, 2011, 01:28:31 AM by montymintypie »

Offline hopslink

  • Robot Overlord
  • ****
  • Posts: 202
  • Helpful? 14
Density based clustering.  ;)

Offline montymintypieTopic starter

  • Beginner
  • *
  • Posts: 2
  • Helpful? 0
Density based clustering.  ;)

That was quick! I don't know why I didn't ask for help sooner ::)

Thanks so much, it's exactly the term I've been looking for! ;D

 


Get Your Ad Here