This week's book giveaway is in the JDBC forum. We're giving away four copies of Make it so: Java DB Connections & Transactions and have Marcho Behler on-line! See this thread for details.

Greeting Ranchers,
First off i feel i should start by apologising for 2 things relating to this post.
1. It may not really be a java problem (It's Math related).
2. If it can be considered as a java problem then it's most likely in the wrong place(I searched through the different forums for a suitable place for the question but couldn't find one).

I finished a simple command line exercise over the weekend that involved reading in a bunch of user selected points which are meant to be input to reflect a polygon shape. the program then calculates the perimeter of the shape based on the points and the order they were input. Pretty straight forward stuff.

My question - and this is starting to drive me mad - is this. Suppose the user input the points in such a manner that the order did not circumscribe a polygon, what would be an approriate way to sort through the points and determine the shape of a polygon from them?

I've tried a few different approaches at this stage but all of them have been flawed. The closest i can get is to read through the range of y coordinates for the points, determine a mid point and then read all those y values above it in order while transversing the x axis and all those below it on a return scan. This works (mostly)but the results are not always optimal with the perimeter often needlessly crossing into the wrong sectors of the shape while there are points closer to it that would suit the shape better.

I realise that this question may be too abstract for the java in general board so you can tell me to shove off if you want but i'm hopeing someone can let me know if there is an already available approach or a different way of thinking about it or maybe you can recommend a good cure for a headache. Maybe its not possible without a load of complex Math or maybe its so simple i'm missing it. I'd post the code i already have but i have a feeling its not needed for the question. If any of you guys have encountered this problem before i'd like to hear from you.

I think you're taking a problem which is meant to be straightforward, and complicating it. That's not necessarily a bad thing. You have strayed into something called The Travelling Salesman problem, which is an interesting area in itself. Given a set of points, what is the shortest round-trip path that passes through each point? It turns out the only known way to solve this problem is to try all possible combinations, but there's also no proof that it couldn't be solved faster. It's called an NP-complete problem.

In your case, I'm not sure what would constitute "not a polygon". Crossing lines maybe? I expect that you would get an ordered set of points, and your job would be to calculate the sum of distances. Done. If you have to check for crossing lines, that would be possible too, but not as easy.

Mike Daly
Greenhorn

Joined: Nov 05, 2009
Posts: 24

posted

0

Hi Greg,
Thanks for the quick reply. I've looked up the travelling salesman problem and it is very interesting. Yes i'm guilty of needlessly complicating a problem ( but that's half the fun ) and yes my "not a polygon" would have required that no lines intersect. However after reading some of the travelling salesman i am now convinced i have bitten off more than i can chew. Looking at the maths involved i don't think i'd have a clue how to begin implementing. I get the impression that the closer i look at this the more frustrating it will get so i'll just quietly back myself out of here and run away.

Apologies for wasting anyones time reading this. I guess there are no stupid questions, just stupid people that ask them.

Well, the reason I brought up travelling salesman is that you made it sound like you didn't know in which order the points would be connected. The problem then would be given a set of points, how can they be connected into a polygon? I assume there's always some way to do it, but I think that would, in fact, be a hard problem to solve.

However, I think you know the ordering of the points, and really you just need to figure out the length of the line segments (easy) and whether they intersect. You could examine each pair of line segments to see if they intersect (easy but slow) or run some kind of line sweep algorithm (faster and not that much harder).

Mike Daly wrote:
My question - and this is starting to drive me mad - is this. Suppose the user input the points in such a manner that the order did not circumscribe a polygon, what would be an approriate way to sort through the points and determine the shape of a polygon from them?

I don't think you can. Given a bunch of points (even as little as four points), it is sometimes possible to create more than one polygons from it.

hmmm, it seems i've been using the wrong definition of a polygon. what i should have been referring to is a simple polygon, where no two sides cross. Thanks for illuminating that inconsistency Henry. The more i think about this problem the more frustrating it gets and i've begun to realise that it will demand more time than i have available currently. I guess it'll have to go on the backburner for some late night weekend rematch. Thanks for your help and suggestions guys. I really liked that travelling salesman problem Greg.

Mike Daly wrote:hmmm, it seems i've been using the wrong definition of a polygon. what i should have been referring to is a simple polygon, where no two sides cross.

Even this definition is not enough... for example...

Could be...

or

Henry

Mike Daly
Greenhorn

Joined: Nov 05, 2009
Posts: 24

posted

0

Henry that's another thing i hadn't considered. It would be interesting to see how somebody with a good understanding of the principles involved would go about solving the problem. I've asked a friend and he says spliting the shape into different sectors within the closing boundary and using differential geometry would be a possible answer. That's perfect if you know differential geometry i guess, not so perfect is you were busy watching squirrels through the window during that class.