algorithm or pseudocode help???

tommycahir

hi is there anyone out there that would be able to help me with an algorithm that would find two crossing lines in c++ and then rearrange them any pseudocode or links to web sites would be greatly appreciated i have no idea on where to start on this so any help would be greatfull:)
tanx

seamus

Hi, give us the specs of the algorithm and we may be able to help.
Two crossing lines........of what? and where?

tommycahir

on a grid i must find any line that are crossing over each other and then find the best fit where no lines are crossing each point/ intersection on the grid where a line terminates, there is a logic gate place there i must find the best fit so that there are as few as possible cross overs included are some screenshots of the applic its going to be written in c++ there has been no coding done as yet i starting to code it this week and looking for help on the sorting part of the prog
tanx

tommycahir

please please please please help me i in dire need of help please anybody outthere with programming experience

SkepticOne

I've still got a little trouble understanding the problem. Did you get given any written specification from your lecturer.

Here's what I think I understand so far: You are given a circuit diagram with crossed-over lines. The purpose of the program is to maintain the connections between the components but have no lines crossed over.

Another possibility is that you are presented with some sort of matrix specifying the interconnection between components and you must write a program that lays it out in such no lines cross over.

How is the initial data presented?

tommycahir

im given a circuit diagram with crossed-over lines. The purpose of the program is to maintain the connections between the components and have no lines crossed over.

it implemented using doubly linked pointers
i sorry bout the vagueness of the spec but that bout all we were told that we had to write a prog that would arrange the connections so that there very few or little cross overs any help would be much appreciated

even some simple pseudocode would help me

Hobbes

Normally

(a) You should already of been given the material to complete this project in your course work.

or

(b) Your not expected to know, but to instead work out a way to do it yourself.


I would guess that in either instance your supposed to do it yourself.

"doubly linked pointers" ? Do you mean doubly linked lists? Which would make sense in what you are trying to do.

SkepticOne

OK, so the circuit board is represented as a doubly-linked list with presumably the type of component and x, y coordinates for the positions of each node. The task then is to find a set of x and y coords for each component so that the lines don't cross. There probably needs to be some sort of separation between the components too.

Is this correct? I'm amased that an assignment would be given out without some sort of spec. You should check with the lecturer that this is a correct understanding of the problem.

tommycahir

yea i think that you got the understanding of the project now included is a pic of the interface if that any help to you...

str8_away

Tommychair

This is what I would do if I am you.
1) try to create the problem
2) try to solve the problem

1) Create the program with GOOD structure to represent the problem/information. Since you have to use double link list (dll) then I would create dll with following structure.

structure for line
pointer to previous dll
pointer to next dll
coord for one end of line
coord for the other end of line

structure for node
pointer for line in 1
pointer for line in 2
pointer for line out
type, AND, OR, XOR ......
other info like x,y

2)
Only after you create the enviroument to represent the problem then you can try to solve it.

You could go throught each node and each dll it has, use simple geometry equetion to find out if lines are cross over each other.
If they are then do something cleaver, like move node, split line into more lines so the it goes around the other.


This is probobly not the best solution but it should get you start thinking. Just remember you cannot solve the problem unless you can present it and solution depend on how you represent the problem. A good structure can make easier sollution.
(one little hint: all lines seems to be either vertical or horizontal you might be able to use this to make a better structures that can speed up cross over check)

There is a lot of coding to be done for this project so you better start as soon as you can.

good luck

tommycahir

tanx str8_away
that bit of the data structure helped me alot cos from that i am able to build the prob and work from there all your help is greatly appreciated
tanx