|
Okay, so if you can find that it's the green and red lines you want, my solution will work for creating the polygon. (The average point will be somewhere in the middle and then G1, R1, R2, G2 are in order of angle from it.)
To find which lines you want, order them based on how far along the 'black axis' they cross the black lines, i.e. by r.b where r is any point on a line and b is the direction vector of the black lines.
(Sorry for not responding for a while, I forgot about this forum.)
|
|
|
|
|
Thanks - that just leaves me with the ordering problem (see my other post). Since my lines may have been draw either way around, and in a "random" order...ordering them is not as easy as it sounds. I've come up with a method that will work most of the time (I think) (Here[^]).
I think throwing the points at a Travelling Salesman algorithm might be less complicated.
|
|
|
|
|
Kyudos wrote: I think throwing the points at a Travelling Salesman algorithm might be less complicated.
No need for that. When the lines are almost parallel, and don't cross each other, you can define some kind of distance, calculate that, and order them all based on it.
Example: take one of the lines, calculate its equation in the form f(x,y)=a*x+b*y+c.
All points on the line itself have f(x,y)=0 by definition.
The green/red points have a non-zero f value, take one of them, or the average, and use that as a distance.
|
|
|
|
|
I think that is along the lines of what I described in my Physics Forum post (see above). But a TSP solution will generically work for both lines and polylines with minimum complication.
|
|
|
|
|
I answered that as well in the last paragraph  . I'm assuming that the black lines are in some known direction, otherwise you have to pick a direction vector ... but just choosing the perpendicular to any one of the lines should work fine. It doesn't actually matter whether the order ends up as ABCD or DCBA, and picking a perpendicular will guarantee one of those will be the case if the lines are close to parallel. (The average perpendicular for all the lines will be better but probably unnecessary.)
|
|
|
|
|
I have to write a program in java for wordwrap with minimum regard...
for example if we have "aaa bb cc ddddd" and want to wrap it in lines with this method the final form should be like this :
------ Line width: 6
aaa Remaining space: 3 (cost = 3 squared = 9)
bb cc Remaining space: 1 (cost = 1 squared = 1)
ddddd Remaining space: 1 (cost = 1 squared = 1)
attention that we don't know number of lines...I don't understand the algorithm which is in wikipedia ,in this link :
http://en.wikipedia.org/wiki/Word_wrap[^]
but unfortunately I still have problem with understanding the algorithm...can some one explain it with example for me ?
|
|
|
|
|
You have already asked this question in Q&A. Read the guidelines, and ask your question ONCE if you don't want to annoy people who might otherwise have an answer for you.
Software rusts. Simon Stephenson, ca 1994.
|
|
|
|
|
Hi...I wanna write a program in java that can count the number of balanced matrix of N*N...the only way that I know is to consider all the possible assginments for the matrix and then choose the answers...I searched the topic and found something about it in wikipedia...it solved the problem with dynamic programming but unfortunately I don't understand exactly the algorithm...can anyone help and explain completely with example for me what to do ?
this is the link that I found :
http:
|
|
|
|
|
Dynamic programming can be used when optimal solutions are composed of optimal sub-solutions. You start with the smallest optimal sub-solutions, and use them to build up optimal solutions to larger sub-problems.
This typically runs in polynomial time, which is faster than trying all possible solutions, which would take exponential time.
"Microsoft -- Adding unnecessary complexity to your work since 1987!"
|
|
|
|
|
plz can anyone tell me how to store the data in text file using file handling in java...
plx Mail me comprehensive program of file handling, explain with comment and few of explanation...
asadali.nazir@gmail.com
|
|
|
|
|
See here[^] for all the information you need.
Unrequited desire is character building. OriginalGriff
I'm sitting here giving you a standing ovation - Len Goodman
|
|
|
|
|
Unless you want a lot of spam in your inbox, please do not put your e-mail address in a message posted publicly.
"Science is facts; just as houses are made of stones: so, is science made of facts. But, a pile of stones is not a house, and a collection of facts is not, necessarily, science." Henri Poincare
|
|
|
|
|
This article: Graphical solution to eight queen problem[^] mentions "the old algorithm from Horowitz-Sahani". Does anyone here have more information on this? I haven't found anything online, I'm thinking it's only in a text book.
|
|
|
|
|
|
Ah, good, thanks. That first one still just shows the snippet* posted in the article I mentioned, I was hoping to see more on the algorithm.
* And that's what I came up with on my own last week.
Also, I note in the second one that he's using recursion -- my algorithm is non-recursive.
P.S. I just ordered a used copy of that book from Amazon. 
modified 1-Jan-12 10:27am.
|
|
|
|
|
I would be interested in seeing your algo to see how it stacks up with some of my algos for removing recursion.
Dave.
|
|
|
|
|
Once I've seen what's in the book I'll decide whether or not mine is unique enough to form an article.
|
|
|
|
|
The book arrove today. My code is very much like the code they show on page 338 with two main differences:
0) They have the test in a separate function and therefore a global array.
(Which also has a needless call to ABS.)
1) They have an extra while loop.
public static System.Collections.Generic.IEnumerable<System.Collections.Generic.IList<int>>
nQueens
(
int HowMany
)
{
int[] board = new int [ HowMany ] ;
int row = 0 ;
board [ row ] = -1 ;
while ( row >= 0 )
{
board [ row ]++ ;
if ( board [ row ] == HowMany )
{
row-- ;
}
else
{
int i ;
for ( i = 0 ; i < row ; i++ )
{
int diff = board [ row ] - board [ i ] ;
if ( ( diff == 0 ) || ( System.Math.Abs ( diff ) == ( row - i ) ) )
{
break ;
}
}
if ( i == row )
{
row++ ;
if ( row == HowMany )
{
yield return ( System.Array.AsReadOnly ( board ) ) ;
row-- ;
}
else
{
board [ row ] = -1 ;
}
}
}
}
yield break ;
}
|
|
|
|
|
Thank you for your reply. I gather that this is your algorithms since it only has one "while" loop. It may take me a while to digest this, I am primarily a MASM developer, but come here for algorithms.
Do you have any guesses as to how large "HowMany" can be and not run out of memory, i.e., what would be the maximum n for nQueens with this algo?
Dave. (Another Desert Rat from West Phoenix)
|
|
|
|
|
Oh, yes, that's mine. The book uses a Pascal-like language the authors created called SPARKS.
On my system (Win 7 32bit, 4GB RAM), somewhere around 438330000 depending on what else is going on:
C:\Projects>nQueens 438330000
^C
C:\Projects>nQueens 438335000
System.OutOfMemoryException: Exception of type 'System.OutOfMemoryException' was thrown.
at PIEBALD.Lib.LibMth.<nQueens>d__0.MoveNext()
at PIEBALD.Utilities.nQueens.Main(String[] args)
I have heard that .net limits the size of a structure (e.g. an array) to two gigabytes.
Member 4194593 wrote: Desert Rat from West Phoenix
Ah, then I invite you to join the Tosche Station group. http://www.codeproject.com/Members/Tosche-Station[^]
modified 11-Jan-12 16:22pm.
|
|
|
|
|
Does .net limit you if the /3GB switch is used in c:\boot.ini.bat?
Dave.
|
|
|
|
|
I expect so, but I haven't tried it.
|
|
|
|
|
If you go to try it, be aware if the pitfalls:
Boot.ini is System,Hidden,Readonly.
I think you need to be Administrator.
Change the permissions to R/W.
Even as Admin you cannot edit boot.ini with ordinary editors, use RUN NOTEPAD.
Open boot.ini
Change [OS] multi(0)... and add /3GB.
Save boot.ini
For your own safety, change permissions back to RO.
Boot the system.
Also, you do have a good disk image backup don't you?
Dave.
|
|
|
|
|
Ah, thanks, but I'm not going to try it.
|
|
|
|
|
Turing Machine Simulator
Write a program that simulates a Turing machine (Tm). A Tm is a primitive model of a general purpose computer. Programs for a Tm consist of a collection of quadruples, each of the following form:
<state> <symbol> <action> <nextstate>
where
<state> ::= a non-negative integer
<symbol> ::= 1 | B
<action> ::= <symbol> | L | R
<nextstate> ::= a non-negative integer
A Tm stores data on a tape divided into squares, each of which contains one symbol, either 1 or B. Only one square can be inspected at a time. Initially, a sequence of symbols is written on the tape (this is the input to the Tm), the Tm's "read/write head" is positioned over the leftmost symbol, and the state of the Tm is set to some "start state".
At any point in a Tm computation, the Tm is in a particular state with its read/write head scanning the symbol in a particular square. What happens next depends on whether the Tm's program contains a quadruple whose <state> is the Tm's current state and whose <symbol> is the symbol contained in the square currently being scanned. If such a quadruple exists (there cannot be more than one such), the <action> part of this quadruple controls what happens next:
if <action> specifies a symbol, then that symbol replaces whatever symbol is in the square currently under scan
if <action> is L, the Tm's read/write head is moved one square to the left (the symbol in the square previously under scan is not changed)
if <action> is R, the Tm's read/write head is moved one square to the right (the symbol in the square previously under scan is not changed)
After one of the above actions is done, the Tm changes to state <nextstate> and we repeat the process of searching for an appropriate quadruple to "execute". This is continued until no quadruple matches the current state and symbol under scan, in which case the Tm halts and we consider its output to be the sequence of symbols between the first and last 1's on the tape, inclusive (if no 1's remain, we consider the output to be just B).
The input is a sequence of Tm instruction quadruples followed by a "start" line that specifies the initial state for the Tm, followed by the sequence of symbols that make up the initial value stored on the Tm's tape. Generically:
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
<state> <symbol> <action> <nextstate>
...
start <state>
<symbol>
<symbol>
<symbol>
<symbol>
<symbol>
...
For example:
0 1 R 0
0 B 1 1
start 0
1
1
1
1
Given the above input, the output should be:
11111
Note
If a quadruple requires moving left from the leftmost symbol on the tape, or right from the rightmost symbol, a square containing the symbol B must be added to the appropriate end of the tape (which is thus "finite, but unbounded")
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
