Hogyan jöjjön rá a program, hogy egy sokszög konvex vagy konkáv e?

Ha egy sokszög konvex, akkor bármely 2 csúcsa között húzott egyenes a sokszögön belül fut. Talán ezt kéne valahogy kihasználni.

Bár ez így még nem túl konkrét, nincs igazán ötletem milyen képlettel lehetne meghatározni hogy az a vonal a sokszögön belül fut-e :/

To find if a set of points give a convex or a concave polygon you can calculate the convex hull of the points. If all the points are on the convex hull then it is obvious that the polygon is convex. If the number of points on the convex hull is smaller of the total numbers of points then the polygon is concave. To calculate the convex hull you can use the gift wrapping algorithm. This is the simplest convex hull algorithm to implements but it is not the most efficient.For your case (100 points max) this should be enough. In the algorithm, computing the real polar angles can be not easy. A clever way to compute it is to take the determinant of two points (a 2x2 matrix) and sort these values.

[link]

forrás:

[link]

Egyenkénti hozzávétellel a konvex burok időigénye O(n log n).

Azaz:

10 pont esetén 10 időegység

100 pont esetén 200

1000 pont esetén 3000

10 000 pont esetén 40 000

Csomagkötöző algoritmus, itt kell egyenként hozzávenni a pontokat:

[link]

Gyorsabbat nem is fogsz találni.