Re: Can you do this with a convex hull? - Algorithms Discussion Boards

Kyudos12-Feb-12 12:40

12-Feb-12 12:40

I have a set of parallel-ish lines (they may not be parallel, but they don't cross) that define an area. On each line, I calculate two points (lets say P1 and P2) which define an operating region. With an ordered set of lines, I know for line 1 (L1), the polygon showing the operating region starts at P1 and ends at P2. The next point in the polygon is L2P1, whereas the (n-1)th point is L2P2 (where n is the number of lines I have).

My problem is:

1) Lines may be drawn either way, so P1 and P2 in two 'adjacent' lines may not be on the same side.
2) Lines may not be in order.

So, knowing the number of lines, and which points belong to the same line (i.e., I know which points are paired),
can I calculate the order of the lines / points, so that I can draw my polygon?

It seems like a hulling problem, but is there a way to say 'all these points are on the hull boundary'?
Wouldn't that lead to multiple solutions for certain sets of points?

Re: Can you do this with a convex hull?

Kyudos12-Feb-12 14:13

Kyudos

12-Feb-12 14:13

Actually - is this a travelling salesman problem?

Re: Can you do this with a convex hull?

BobJanova12-Feb-12 23:03

BobJanova

12-Feb-12 23:03

Can you show some diagrams of the possible scenarios? I'm not sure I have it entirely clear in my head.

If the hull is known to be convex, and we're talking 2D, I would take an approach like:
- find a point inside the shape (the average location of all the control points should do)
- go around the control points in order of angle from that central point

I don't think the pairing of points on the same line matters, once you have the collection of points.

Re: Can you do this with a convex hull?

Kyudos13-Feb-12 12:57

Kyudos

13-Feb-12 12:57

This is a very simple example, but I want to draw the polygon defined by the black lines and the green and red spots.

This[^]

Re: Can you do this with a convex hull?

BobJanova16-Feb-12 5:22

BobJanova

16-Feb-12 5:22

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.)

Re: Can you do this with a convex hull?

Kyudos16-Feb-12 9:50

Kyudos

16-Feb-12 9:50

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.

Re: Can you do this with a convex hull?

Luc Pattyn16-Feb-12 10:56

Luc Pattyn

16-Feb-12 10:56

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.

Smile | :)

Luc Pattyn [My Articles] Nil Volentibus Arduum

Re: Can you do this with a convex hull?

Kyudos16-Feb-12 15:31

Kyudos

16-Feb-12 15:31

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.

Re: Can you do this with a convex hull?

BobJanova17-Feb-12 0:36

BobJanova

17-Feb-12 0:36

I answered that as well in the last paragraph Wink | ;)

. 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.)

wordwrap with minimum raggedness

Member 858607226-Jan-12 10:09

Member 8586072

26-Jan-12 10:09

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 ?

Crosspost

Peter_in_278026-Jan-12 11:37

Peter_in_2780

26-Jan-12 11:37

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.

A type of balanced 0–1 matrix

Member 858607221-Jan-12 8:01

Member 8586072

21-Jan-12 8:01

CSS

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://en.wikipedia.org/wiki/Dynamic_programming#A_type_of_balanced_0.E2.80.931_matrix[^]

Re: A type of balanced 0–1 matrix

Alan Balkany16-Feb-12 4:08

Alan Balkany

16-Feb-12 4:08

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!"

input

AsadRana21-Jan-12 1:27

AsadRana

21-Jan-12 1:27

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

Re: input

Richard MacCutchan21-Jan-12 2:34

Richard MacCutchan

21-Jan-12 2:34

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

Re: input

BillWoodruff29-Jan-12 13:08

BillWoodruff

29-Jan-12 13:08

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

nQueens algorithm

PIEBALDconsult31-Dec-11 4:02

PIEBALDconsult

31-Dec-11 4:02

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.

Re: nQueens algorithm

DaveAuld31-Dec-11 4:49

DaveAuld

31-Dec-11 4:49

This page makes reference to it and it is from a book;
http://penguin.ewu.edu/~trolfe/SCCS-95/SCCS-95.html[^]

This article makes reference to it, and again same book;
http://drdobbs.com/architecture-and-design/184406068[^]

Dave
Find Me On: Web|Facebook|Twitter|LinkedIn

Folding Stats: Team CodeProject

Re: nQueens algorithm

PIEBALDconsult31-Dec-11 15:08

PIEBALDconsult

31-Dec-11 15:08

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. Thumbs Up | :thumbsup:

modified 1-Jan-12 10:27am.

Re: nQueens algorithm

Member 41945931-Jan-12 13:20

Member 4194593

1-Jan-12 13:20

I would be interested in seeing your algo to see how it stacks up with some of my algos for removing recursion.

Dave.

Re: nQueens algorithm

PIEBALDconsult1-Jan-12 16:14

PIEBALDconsult

1-Jan-12 16:14

Once I've seen what's in the book I'll decide whether or not mine is unique enough to form an article.

Re: nQueens algorithm

PIEBALDconsult9-Jan-12 13:15

PIEBALDconsult

9-Jan-12 13:15

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 ;
}

Re: nQueens algorithm

Member 419459311-Jan-12 8:25

Member 4194593

11-Jan-12 8:25

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)

Re: nQueens algorithm

PIEBALDconsult11-Jan-12 9:35

PIEBALDconsult

11-Jan-12 9:35

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.

Re: nQueens algorithm

Member 419459311-Jan-12 10:01

Member 4194593

11-Jan-12 10:01

Does .net limit you if the /3GB switch is used in c:\boot.ini.bat?

Dave.

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.