• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Traversing all possible combinations

 
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
We have multiple points in 2D space described by their X and Y coords. I have to program an algorythm which would display all possible squares defined by 4 points combination. As I understand it comes to making all possible 4 member combinations of out of number of entities.

Anybody could tell me such algorythm?
Thank you
 
Vladas Razas
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I forgot to mention that all points are stored in DB... Pershaps I will have to load them all into memory (otherwise I would need professional mathematician help).
 
author
Posts: 23951
142
jQuery Eclipse IDE Firefox Browser VI Editor C++ Chrome Java Linux Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The easiest way in "making all possible 4 member combinations" is probably to do it recursively.

Henry
 
Ranch Hand
Posts: 502
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Do you want squares or do you want any 4 sided figures?

Possibly, not the most efficient way of doing this, but have you thought about doing a self-join.. 4 times. If the table is small enough, the database could probably do it in memory. Don't flame me.. just a suggestion
 
Vladas Razas
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
3.1.Business requirements
Initial data set consists of random set of distinct points on a plane. Each point is defined using integer x, y coordinates from the range [0..100]. Candidate task is to find all squares that these points form on the plane. Result should be presented as list of squares (as coordinates of vertex points) as well as graphically. Example of graphical presentation is shown in picture below.

http://putfile.com/pic.php?pic=10/27803104929.jpg&s=x7

User can perform following actions from the web page.
User can see a list of points (as x, y coordinates).
User can add new point.
User can delete selected point.
User can execute task that finds all squares and displays results.


I guess that means squares - rectangles with all sides equal? At least webster defines "square" this way. Sorry english not my native language. Having that in mind this must not be just all 4-point combinations
 
Vladas Razas
Ranch Hand
Posts: 385
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
But still that might be useful to have algorythm that would allow to iterate 4 point combinations and then check if they are rectangles
 
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

[ October 06, 2005: Message edited by: Ryan McGuire ]
 
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
For any two points you get a line and for any line there are only two possible squares. Would it be faster to take each pair and see if there are squares around them than to take each quad and see if it's a square?
 
Ryan McGuire
Bartender
Posts: 1205
22
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Originally posted by Stan James:
For any two points you get a line and for any line there are only two possible squares. Would it be faster to take each pair and see if there are squares around them than to take each quad and see if it's a square?



Myabe but...
The number of points in the example given was only 18. Even if that were doubled to 36, the brute force algorithm with four nested loops will still execute pretty darn quick.

Besides, taking each pair of points, determining the possible squares, and then searching the array of points to see if the other two points are present still involves at least three nested loops.

You might get O(n^3), while four nested loops achieves O(n^4), but the simpler overhead of the n^4 algorithm may be faster for small values of n. It depends on what executed in your loops.
 
Stan James
(instanceof Sidekick)
Posts: 8791
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
With enough points it might get to be worth while to index or sort them and look for squares, but for this number I agree, just try em all.
 
Always look on the bright side of life. At least this ad is really tiny:
a bit of art, as a gift, the permaculture playing cards
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic