Witam,
Jak przypuszczam temat z praktycznego punktu widzenia czysto Uniwersytecki, ale nie mogę nigdzie znaleźć jego rozwiązania w sieci - otóż:
Na płaszczyźnie mam kolekcję punktów. Wszystkie te punkty chciałbym zebrać w ramach jakiejś figury łącząc kolejne punkty które znajdują się na skraju tak by wszystkie pozostałe punkty znajdowały się wewnątrz lub stanowiły część figury (są punktami linii lub są na linii).
Czy wiecie gdzie w sieci znajdę opis tego algorytmu?
--
Grzegorz Wiśniewski
http://www.algorytm.org/index.php?option=com_content&task=view&id=70&Itemid=28
o coś takiego chodzi? Wypukła otoczka (Algorytm Grahama)
Dzięki. Jest to dokładnie to co mnie interesowało.
Kolego 'pako1337' masz może implementację tego algorytmy w języku wysoko poziomowym? Starałem się z materiału z linku, który mi dałeś stworzyć wersję w C# ale nie działa mi ona najlepiej (zwraca błędne wyniki).
Pozdrawiam.
Nie mam, nigdy nie miałem potrzeby go implementować. Ale kurczę, to nie jest chyba jakieś strasznie trudne, nie? Bierzesz skrajny punkt, szukasz odpowiednich kolejnych, spełniających warunki i budujesz listę. Wydaje mi się, że jest to do ogarnięcia prosto.
Nawet bym się pobawił i napisał, ale jakoś nie mam czasu.
Oprócz algorytmu Grahama możesz spróbować wykorzystać też algorytm Monotone Chain. Masz tutaj też moją implementację obydwóch w C++ (projekt1).
PS. czy to projekt z geometrii obliczeniowej?
Muszę zaprojektować kontrolkę, która będzie mniej więcej wyglądać tak jak na rysunku: http://www.grzegorzwisniewski.eu/cad.png. Wypukłą otoczkę wykorzystuję w kilku miejscach do sprawdzenia czy jakiś punkt leży wewnątrz obszarów które widać na rysunku, czy do posortowania punktów do narysowania obszarów.
Kontynuując ten wątek mam jeszcze problem z utworzeniem tych obszarów. Znacie jakiś rozwiązanie dzięki którego mogę obszary te wydzielić?
Rozwiązaniem dość pracochłonnym jest utworzenie wszystkich możliwych linii i usuwanie tych, które się przecinają, a w kolejnych krokach grupowanie.
Witam,
Odświeżę temat z racji tego, że nie bardzo jestem w stanie poradzić sobie z implementacją w C#. Poczyniłem taką klasę:
using System.Linq;
namespace Algorithm
{
public class PointConvexSheath : System.Collections.Generic.List<Point>
{
public PointConvexSheath(System.Collections.Generic.List<Point> current)
{
if (current.Count < 3)
{
throw new System.ArgumentException("Too short list", "current");
}
unique = new System.Collections.Generic.List<Point>
(
);
current.ForEach
(
(target) =>
{
if
(
!unique.Exists
(
(match) => target.X == match.X && target.Y == match.Y
)
)
{
unique.Add(target);
}
}
);
if (unique.Count < 3)
{
throw new System.ArgumentException("Too short list", "unique");
}
var minY = unique.Min
(
(target) => target.Y
);
var minX =
(
from
item in unique
where
item.Y == minY
orderby
item.X
select
item.X
).First();
unique.Sort
(
new PointVectorsSort(minX, minY)
);
this.Add(unique[0]);
this.Add(unique[1]);
this.Add(unique[2]);
for (int i = 3; i < unique.Count; i++)
{
while (this.SkretPrawo(unique[i]) == false)
{
var last = this.LastOrDefault();
if (last != null)
{
this.Remove(last);
}
else
{
break;
}
}
this.Add(unique[i]);
}
}
private bool SkretPrawo(Point p3)
{
Point p2 = unique[unique.Count - 1];
Point p1 = unique[unique.Count - 2];
if (Delta(p1, p2, p3) > 0)
{
return false;
}
else
{
return true;
}
}
private decimal Delta(Point point, Point point1, Point point2)
{
return point.X * (point1.Y - point2.Y) + point1.X * (point2.Y - point.Y) + point2.X * (point.Y - point1.Y);
}
#region Definition variable
private System.Collections.Generic.List<Point> unique;
#endregion
}
}
Nestety w przypadku testowym obejmującym punkty:
addPoint(new Point(0, 0));
addPoint(new Point(0, 4));
addPoint(new Point(4, 4));
addPoint(new Point(4, 0));
addPoint(new Point(1, 3));
Uzyskuję błędny wynik.
Nie bardzo widzę gdzie zrobiłem błąd.
Pozdrawiam,
Grzegorz
Wg mnie algorytm opisany tutajhttp://www.algorytm.org/index.php?option=com_content&task=view&id=70&Itemid=28 jest błędny - zawsze zostawia ostatni punkt pm. Napisałem (w Javie) implementacje poprawionego algorytmu i działa. Jeśli jesteś zainteresowany daj znać.
"Bo" jak najbardziej jestem zainteresowany. Mógłbyś mi go gdzieś udostępnić?
Mogę Ci wysłać na maila. Mam dwa programiki (algorytm jest w obu taki sam).
"Bogdans" pierwszy wydaje się być najlepszym. Rzeczywiście muszę zobrazować punkty w interfejsie graficznym ale w sposób wyniku tak by użytkownik nie widział innych punktów stąd łatwiej będzie mi rozwinąć (przepisać do C#) pierwszą Twoją propozycję.
Mój adres e-mail znajdziesz w profilu.
Serdeczne dziękuję.