|
Hi,
this should do it:
- take one edge (two consecutive points) of the polygon
- find its equation in the form f(x,y) = a*x + b*y + c = 0
(there is one freedom left, a scale factor in each of the coefficients)
- now feed each of the other points in the f(x,y) function; all the results need to have the same sign for the poly to be convex.
- repeat for each edge.
There may be simpler, I am not aware of it though.
|
|
|
|
|
Luc's suggestions is nearly there, but:
1. You should use the orientation predicate (sign of the 3 point determinant (0,+,-)), instead of the half-plane equation.
2. Instead of testing each edge against each other point (via half-plain which btw shouldn't work), what you do is test the orientation of the next point of polygon against the current edege.
3. if the orientation is the same as the previously calculated orientation, or if the orientation is zero and the point is not in the AABB of the current edge then continue onto next edge, if any of those conditions fail for the current edge assume conconcave polygon and break from loop.
This should have a time complexity of O(n).
|
|
|
|
|
Hi,
I looked into your suggestions and have some comments.
1. The orientation predicate, a simple determinant, seems to compute the same thing I described, in a more abstract but more direct manner. An advantage is there are no divisions involved, hence it is faster and without any danger for overflows and divides by zero.
2. Testing only one point against each edge reduces complexity from O(n^2) to O(n), but IMO it may cause problems for certain shapes, such as this 9-point star[^]
3. yes, collinear points could be present, and then one might be strict on how to interpret the situation. Is a polygon with 4 or more collinear points where some go back and forth along an edge still convex? the convex hull remains the same, so I would be inclined to say yes, although one could argue there are some 180 degree angles involved.
|
|
|
|
|
Thanks
I feel that i can go ahead with the logic/algorithm that u have suggested
|
|
|
|
|
Regarding:
Point 2
That is definitely correct, if that is a case you wish your routine to handle which would be quite common then the simplest solution would be computing the convex hull (better than the half-plane approach) and testing against it. Computing the hull would be O(nlogn) and testing it would be O(n) (find an anchor point then traverse edges, or compute the areas of the polygons - if they match then convex ye be.) which would result in a final complexity of O(nlogn) less than n^2.
Now there is this issue of the difference between simple and non-simple polygons, for example the 9 point star is an example of a non-simple self intersecting polygon, perhaps the OP could have better specified the classes of polygon he was interested in as that would help narrow down the most optimal algorithm he could use for his expected input.
Point 3
These are really edge cases you're mentioning but nonetheless possible. I guess if the general shape of the polygon is convex some may call it convex, but if a strict path-wise approach is taken then it would certainly be concave, I personally would attempt to simplify such polygons as running times of future operations performed upon the polygons such as (point in polygon etc...) will become needlessly long. At the end of the day the requirements of the task matter more than the pedantic/ambiguous nature of the mathematical definitions.
|
|
|
|
|
I was thinking about this this morning. Would an epicycloid be considered convex? If the polygon were composed of line segments whose endpoints lie on the epicycloid, what would you do with the little area that overlapped the bigger area? This is sort of like the center of the 9 point star.
Dave.
|
|
|
|
|
I think assuming the Jordan curve theorem, as long as your "boundary" has distinct inside and outside areas it can be considered a polygon, however in this case the epicycloid would definitely be a non-simple self-intersecting polygon of type concave.
Those are all "simple" cases, now consider a polygon that is essentially concentric circles (aka polygon with holes and islands) would that be considered convex? 
|
|
|
|
|
well I have been working on an assigment and it states::
A program has to be developed, and coded in C language, to decipher a document written
in Italian that is encoded using a secret key. The secret key is obtained as random
permutation of all the uppercase letters, lowercase letters, numbers and blank space. As
an example, let us consider the following two strings:
Plain: “ABCDEFGHIJKLMNOPQRSTUVXWYZabcdefghijklmnopqrstuvwxyz0123456789 ”
Code: “BZJ9y0KePWopxYkQlRjhzsaNTFAtM7H6S24fC5mcIgXbnLOq8Uid 3EDv1ruVGw”
The secret key modifies only letters, numbers, and spaces of the original document, while
the remaining characters are left unchanged. The document is stored in a text file whose
length is unknown.
The program has to read the document, find the secret key (which by definition is
unknown; the above table is just an example and it is not the key used for preparing the
sample files available on the web course) using a suitable decoding algorithm, and write
the decoded document to a new text file.
And I know that I have to upload an English dictionary into the program but I don't why it has been asked.(may be not in that statement but I have to dO THAT). My question is , while I can do that program using simple encryption/decryption algorithm then what's the use of uploading the english dictionary in our program? So is there any decryption algorithm that uses a dictionary to decrypt an encrypted file? or can somebody tell me what approach or algorithm should I use to solve that problem???
An early reply (and also authentic one) will be highly appreciated from you.
Thank you guys.
|
|
|
|
|
I don't know why it's wanted in your program, but have a look at this.
http://en.wikipedia.org/wiki/Dictionary_attack[^]
Found by googling 'dictionary attack' - easy isn't it! 
Regards
David R
---------------------------------------------------------------
"Every program eventually becomes rococo, and then rubble." - Alan Perlis
|
|
|
|
|
ETOALIN....
The encryption algorithm is very weak, and you are expected to attack it using letter-frequency analysis. For example, in an substitution cipher for english the most common letter would correspond to E.
I'd assume that they have given you an Italian dictionary text file to use.
I guess they want you to try with the English dictionary to see it not work (or maybe work), so you can discuss it.
|
|
|
|
|
I need an alogithm to calculate all the points through which a bezier curve passes.
|
|
|
|
|
Since it will pass through an infinite number of points, I recommend you use a Turing_machine[^], which can store those points on its infinite tape.
|
|
|
|
|
Or just output them to the WOM drive. There is plenty of space, after all...
No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.
This message is made of fully recyclable Zeros and Ones
|
|
|
|
|
|
|
Hi
How I can write OCR algorithm?
|
|
|
|
|
I suppose it's a daunting task. Have a look at this page [^], wherein some available OCR software is listed.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
[My articles]
|
|
|
|
|
Hello!
Is there any algorithm for something like this:
bool Matches(string text, string search) {..}
Which allows me to search in the following way..
Lets say text = "hello how are you blah blah k thanks bye"
Searching for "'hello how'" would return true (Notice the ')
Searching for "'hello howdy'" would return false
Searchinf for "hoy hello are" would return true (Notice there are not ' in this search)
Well, you get the idea ( I hope so)
Its like google search but, of course simplier
|
|
|
|
|
Hi,
this should do it (pseudo-code):
stringlist list=new stringlist
string[] searches=search.split('\'')
bool quoted=false
foreach string s in searches {
if (quoted) list.add(s)
else foreach string s2 in s.split(' ') list.add(s2)
quoted=!quoted
}
foreach string s in list if !text.contains(s) return false
return true
PS: it could be handled without the list, just test right away instead of adding to list...
modified on Friday, April 24, 2009 11:38 PM
|
|
|
|
|
You could also try to solve that with a suffix tree or array approach. This is, up to my knowledge, usually the fastest solution.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
In c++:
#include <string.h>
char *strstr( const char *str1, const char *str2 );
The function strstr() returns a pointer to the first occurrence of str2 in str1, or NULL if no match is found. If the length of str2 is zero, then strstr() will simply return str1.
For example, the following code checks for the existence of one string within another string:
char* str1 = "this is a string of characters";
char* str2 = "a string";
char* result = strstr( str1, str2 );
if( result == NULL ) printf( "Could not find '%s' in '%s'\n", str2, str1 );
else printf( "Found a substring: '%s'\n", result );
|
|
|
|
|
i m an engineering student and i had selected an application of image processing.well i had to detect a ball in a specified arena or i can say area by using circle hough transform in visual basic 6 but i had not gotten any knowledge in this respect so please please help me and provide me some material to understand the knowledge for this application or technique
|
|
|
|
|
If you can't find that on the internet, I suggest you transfer to phys-ed before you flunk out.
"Republicans are the party that says government doesn't work and then they get elected and prove it." -- P.J. O'Rourke I'm a proud denizen of the Real Soapbox[ ^] ACCEPT NO SUBSTITUTES!!!
|
|
|
|
|
javeria khalid wrote: but i had not gotten any knowledge in this respect so please please help me
you go to school to learn about things you "had not gotten any knowledge". Otherwise what is the point?
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
