Dowolne czworoboki na losowych punktach i liczenie objętości

0

Witam,
trochę już tam programuję, czasem coś tam klepię. Mam pytanie, może nie jest ono czysto związane z danym językiem programowania ale bardziej zagadnieniem. Jako projekt semestralny dostałem zadanie aby wygenerować n losowych punktów w przestrzeni kartezjańskiej po czym osadzić dwa czworoboki z których każdy musi mieć w sobie wszystkie te punkty oraz w każdej ścianie musi znajdować się co najmniej jeden z nich. Jakiś pomysł jak je skontruować ktoś ma? Teoretycznie jeden mógłby tworzyć prostokąt który miałby wymiary najbardziej odległych punktów wygenerowanych przez komputer ale co z drugim?

Pozdrawiam i proszę o pomoc!
Życzę miłego wieczoru!

1

Było powiedziane, że czworoboki muszą być różne? :)

Możesz prostokąt obrócić, możesz zrezygnować z kształtu, który ma nazwę. Możesz np. użyć dwóch skrajnych punktów jako wierzchołków, a pozostałe dwa wierzchołki wygenerować takie, aby reszta warunków zadania była spełniona (wtedy możesz potraktować punkt-wierzchołek jako należący do obu boków czworokąta).

1

najkrótsza odległość C do (prostej przez A,B):

dx=( (Ax-Cx)*(By-Ay) + (Cy-Ay)*(Bx-Ax) )*(By-Ay)/((By-Ay)²+(Bx-Ax)²)
dy=( (Ay-Cy)*(Bx-Ax) + (Cx-Ax)*(By-Ay) )*(Bx-Ax)/((By-Ay)²+(Bx-Ax)²)
L=Sqrt(((Ax-Cx)*(By-Ay)+(Cy-Ay)*(Bx-Ax))²*(By-Ay)²+((Ay-Cy)*(Bx-Ax)+(Cx-Ax)*(By-Ay))²*(Bx-Ax)²)/((By-Ay)²+(Bx-Ax)²)

Jeżeli: V=(Bx-Cx)*(Ay-Cy)-(Ax-Cx)*(By-Cy):
V>0 - to punkt leży po prawej od A-B
V<0 - to punkt leży po lewej od A-B

Bierzesz losowy prostokąt.
Nazywasz parę przeciwległych krawędzi lewą i prawą, drugą parę górna i dolna.
Dla lewej krawędzi znajdujesz najdalszy punkt po lewej (jak jest po prawej to odległość jest ujemna) i przesuwasz ją w lewo o znalezioną odleglość
To samo robisz dla prawej - najdalszy punkt po prawej
Dla górnej i dolnej analogicznie.

0

_13th_Dragon napisał(a):

najkrótsza odległość C do (prostej przez A,B):

dx=( (Ax-Cx)*(By-Ay) + (Cy-Ay)*(Bx-Ax) )*(By-Ay)/((By-Ay)²+(Bx-Ax)²)
dy=( (Ay-Cy)*(Bx-Ax) + (Cx-Ax)*(By-Ay) )*(Bx-Ax)/((By-Ay)²+(Bx-Ax)²)
L=Sqrt(((Ax-Cx)*(By-Ay)+(Cy-Ay)*(Bx-Ax))²*(By-Ay)²+((Ay-Cy)*(Bx-Ax)+(Cx-Ax)*(By-Ay))²*(Bx-Ax)²)/((By-Ay)²+(Bx-Ax)²)

Jeżeli: V=(Bx-Cx)*(Ay-Cy)-(Ax-Cx)*(By-Cy):
V>0 - to punkt leży po prawej od A-B
V<0 - to punkt leży po lewej od A-B

Bierzesz losowy prostokąt.

Nazywasz parę przeciwległych krawędzi lewą i prawą, drugą parę górna i dolna.

Dla lewej krawędzi znajdujesz najdalszy punkt po lewej (jak jest po prawej to odległość jest ujemna) i przesuwasz ją w lewo o znalezioną odleglość

To samo robisz dla prawej - najdalszy punkt po prawej

Dla górnej i dolnej analogicznie.

Przepraszam, ale nie rozumiem do końca. Wygenerowałem jeden prostokąt oparty na bokach xmin, xmax, ymin, ymax . Da go rade jakos przeksztalcic wedlug tego co podales?

1

Nie, ale:

bierzesz prostokąt: 0,0 0,1 1,1 1,0 przekształcasz wg podanego algorytmu i dostaniesz dokładnie ten oparty na xmin, xmax, ymin, ymax
bierzesz prostokąt: 0,1 1,2 2,1 1,0 przekształcasz wg podanego algorytmu i dostaniesz kolejny inny niż poprzednio prostokąt
Jeżeli wybierzesz dwa prostokąty o tym samym nachyleniu do osi to w wyniku działania algorytmu dostaniesz z nich takie same prostokąty

0

Ale jeżeli wezme ten przekształcony według wzoru to jeżeli założymy że ten pierwszy prostokąt oparty na xmin, xmax, ymin, ymax zawiera wszystkie punkty w sobie to ten drugi jednak nie zawiera juz w sobie wszystkich punktow

0

Jeżeli jako start weźmiesz:
wersja A: 0,1 1,2 2,1 1,0
wersja B: 0,1000 1000,2000 2000,1000 1000,0 * Wszystko pomnożone przez 1000*
wersja C: 6600,6601 6601,6602 6602,6601 6601,6600 // Wszędzie dodano 6600
To w wyniku algorytmu opisanego tu: http://4programmers.net/Forum/1214493 z każdego z tych 3-ch wejściowych wersji dostaniesz taki sam prostokąt,
absolutnie nie ważne czy punkty znajdują się wewnątrz czy na zewnątrz czy pół na pół.

0

Ale chodzi o to żeby te wygenerowane czworoboki zawierały w sobie te wszystkie punkty + po jednym chociaz na krawędzi

http://iv.pl/images/53415060804982679763.jpg - w tym przypadku się mijają więc albo czegoś nie rozumiem albo źle wytłumaczyłem na poczatku o co mi chodzi

0

No właśnie to zapewnia algorytm podany tu: http://4programmers.net/Forum/1214493
Zrozum po kroku 1 przechodzimy do kroku 2 potem do kroku 3 i tak dalej aż do koca. Nie zatrzymujemy się na kroku 1.

0

Dobra, przemyślałem to i już chyba rozumiem ten pomysł tylko jak mam zastosować ten wzór podany przez Ciebie skoro mam normalny prostokąt (w sensie bez obrotu)?

0

Dla określonego zbioru punktów istniej tylko jeden prostokąt spełniający warunki:

każdy musi mieć w sobie wszystkie punkty
w każdej ścianie musi znajdować się co najmniej jeden punkt
jedna ściana równoległa osi (czyli bez obrotu)

0

Dobra, rozwiązałem to tak że stworzylem pierwszy prostokąt, potem przesunąłem środek układu do środka prostokąta (czyli przesunalem wszystkie punkty) i probowalem obrocic... uzylem

printf("angle of rotation in rad = %.3lf\n", rad);
    int counter2;
    for(counter2=-0; counter2<number; counter2++)
    {
        tabx[counter2] = tabx[counter2] * cos(rad) - taby[counter2] * sin(rad);
        taby[counter2] = tabx[counter2] * sin(rad) + taby[counter2] * cos(rad);
        printf("(%.3lf,%.3lf)\n", tabx[counter2], taby[counter2]);
    }

czyli
x'=xcos(rad)-ysin(rad)
y'=xsin(rad)+ycos(rad)
no i tak wygenerowalem nowe punkty i obsadzilem nowy prostokat - jak mam wrocic z tymi punktami wygenerowanymi do układu (0,0) czyli sprzed przesunięcia i obrotu układu?
układ 1 - 0,0
układ 2 - przesunięcie do środka prostokąta nr 1
układ 3 - obrót o losowy kąt w radianach

i chcę znowu z 3 do 1 zeby moc zamiescic te dwa prostokaty na jednym wykresie

jak to matematycznie zrobic? jakiego wzoru uzyc?

0

Dokładnie tych samych wzorów, użyj, tylko że kąt będzie z minusem oraz przesunięcia też.

Tak a propos podałem ci prosty sposób, długo odpytywałeś co i jak po czym wybrałeś zupełnie bezsensowny algorytm na dodatek niezbyt dokładny, do którego nawet nie znasz równań?
WTF?

0

Nie do końca rozumiem zaproponowany przez Ciebie wzór i uzyte w nim rzeczy (co mają konkretnie oznaczac Ax, Cx itd.?) Odnosi sie to jakoś do wierzcholkow wyznaczonego przeze mnie pierwszego prostokata czy nie? Jeżeli możesz to proszę wyjaśnij mi to jakoś dokładniej bo naprawdę nie rozumiem :/ Dziękuje za dotychczasową pomoc aczkolwiek jest to dla mnie niezrozumiałe.. :/

Tzn mój algorytm który chciałem wykonać to zasadę działania mniej więcej rozumiem tylko coś się krzaczy i zwraca jakiś dziwny prostokąt.

Podaję przykładowy wynik działania programu wraz z kodem:

najpierw generuję losowe punkty :

Generated 2D points:
(-33.419,-6.503)
(31.681,10.148)
(-30.980,-35.845)
(20.342,-47.925)
(-18.489,28.157)
(49.613,42.634)
(43.577,-47.557)
(-3.483,14.771)
(-38.867,-45.674)
(-40.169,-34.531)
(-21.584,38.734)
(40.595,5.011)
(-17.625,23.747)
(-20.569,17.502)
(-3.596,-41.232)
(-30.677,20.381)
(16.836,48.903)
(-29.078,8.189)
(-15.919,36.306)
(-46.170,-5.213)
(17.514,-19.250)
(-45.838,-39.347)
(-7.200,-1.345)
(-8.623,-6.447)
(-32.617,47.524)
(3.155,29.194)
(29.833,-40.638)
(-3.362,-3.432)
(-2.825,20.533)
(12.723,0.733)
(36.393,14.317)
(-39.610,31.876)
(-21.661,47.011)
(40.193,15.451)
(23.880,-14.265)
(43.714,49.813)
(-4.241,0.358)
(29.840,8.847)
(24.793,-4.743)
(2.148,-17.361)
(-1.247,9.529)
(40.573,-41.154)
(17.349,24.060)
(-8.777,-30.884)
(-13.625,40.294)
(-2.155,27.896)
(-13.500,-49.365)
(4.992,29.108)
(-0.341,22.304)
(-35.997,-43.246)

Potem szukam najmniejszego i największego x oraz y:

 for (k = 0; k<number; k++)

        if (tabx[k] < minx)

        {

            minx = tabx[k];

        }

    printf("min x = %.3lf ", minx);

    

    for (k = 0; k<number; k++)

        if (tabx[k] > maxx)

        {

            maxx = tabx[k];

        }

    printf("max x = %.3lf\n", maxx);

    

    for (k = 0; k<number; k++)

        if (taby[k] < miny)

        {

            miny = taby[k];

        }

    printf("min y = %.3lf ", miny);

    

    for (k = 0; k<number; k++)

        if (taby[k] > maxy)

        {

            maxy = taby[k];

        }

    printf("max y = %.3lf\n", maxy);

min x = -46.170 max x = 49.613
min y = -49.365 max y = 49.813

Potem wyznaczam pole pierwszego:

  double rectanglearea = (maxx - minx)*(maxy - miny);

    printf("Area of rectangle = %.3lf\n", rectanglearea);

Area of rectangle = 9499.497

Przesuwam do srodka prostokata:

 double x2origin = (maxx+minx)/2;

    double y2origin = (maxy+miny)/2;

    printf("new origin points\nx=%.5lf\ny=%.5lf\n", x2origin, y2origin);

new origin points
x=1.72134
y=0.22400

 int count;

    for (count=0;count<number;count++)

    {

        tabx[count]=tabx[count]-x2origin;

        taby[count]=taby[count]-y2origin;

        printf("(%.3lf,%.3lf)\n", tabx[count], taby[count]);

    }

These are the new coordinates of points
(-35.140,-6.727)
(29.960,9.924)
(-32.701,-36.069)
(18.620,-48.149)
(-20.211,27.933)
(47.892,42.410)
(41.856,-47.781)
(-5.204,14.547)
(-40.588,-45.897)
(-41.890,-34.755)
(-23.305,38.510)
(38.874,4.787)
(-19.346,23.523)
(-22.290,17.278)
(-5.317,-41.456)
(-32.398,20.157)
(15.115,48.679)
(-30.799,7.965)
(-17.640,36.082)
(-47.892,-5.437)
(15.792,-19.474)
(-47.560,-39.571)
(-8.921,-1.569)
(-10.345,-6.671)
(-34.339,47.300)
(1.434,28.970)
(28.111,-40.862)
(-5.083,-3.656)
(-4.547,20.309)
(11.002,0.509)
(34.672,14.093)
(-41.331,31.652)
(-23.383,46.787)
(38.472,15.227)
(22.158,-14.489)
(41.992,49.589)
(-5.962,0.134)
(28.119,8.623)
(23.072,-4.967)
(0.427,-17.585)
(-2.968,9.305)
(38.852,-41.378)
(15.628,23.836)
(-10.498,-31.108)
(-15.347,40.070)
(-3.876,27.672)
(-15.221,-49.589)
(3.271,28.884)
(-2.063,22.080)
(-37.719,-43.470)

fooNo i do tego miejsca się zgadza pole prostokąta, wiadomo ze jak go przesunę to pole będzie to samo, nie wazne w jakim ukladzie wspolrzednych

Teraz dokonuję obrotu i dzieje się jakaś magia, nie wiem czemu ale mam wrazenie ze jest to zle

   double rand_num=(double)rand()*90/(double)RAND_MAX;

    double rad = rand_num*M_PI/90;

    printf("angle of rotation in stopnie = %.3lf\n", rand_num);

    printf("angle of rotation in rad = %.3lf\n", rad);

    int counter2;

    for(counter2=-0; counter2<number; counter2++)

    {

        tabx[counter2] = tabx[counter2] * cos(rad) - taby[counter2] * sin(rad);

        taby[counter2] = tabx[counter2] * sin(rad) + taby[counter2] * cos(rad);

        printf("(%.3lf,%.3lf)\n", tabx[counter2], taby[counter2]);

    }

Rotating system of coordinates
angle of rotation in stopnie = 9.257
angle of rotation in rad = 0.323
(-29.891,-17.653)
(23.882,18.308)
(-16.409,-39.603)
(35.629,-30.849)
(-29.362,14.571)
(28.016,49.903)
(56.954,-22.348)
(-10.375,9.469)
(-19.935,-50.032)
(-25.402,-41.830)
(-36.268,21.699)
(34.083,17.466)
(-26.875,11.448)
(-27.206,5.552)
(10.952,-34.109)
(-37.646,4.217)
(-4.664,43.188)
(-31.503,-4.697)
(-30.105,21.815)
(-42.165,-21.159)
(22.043,-9.556)
(-28.796,-47.579)
(-7.642,-4.374)
(-7.004,-8.844)
(-49.825,24.632)
(-9.762,23.029)
(41.609,-21.829)
(-3.297,-4.639)
(-11.973,14.181)
(9.970,4.285)
(26.639,23.215)
(-50.298,9.995)
(-39.507,28.107)
(29.716,25.440)
(26.016,-3.430)
(19.819,53.398)
(-5.559,-2.004)
(22.679,16.646)
(23.217,4.296)
(7.124,-13.521)
(-6.303,6.185)
(51.729,-18.432)
(5.317,24.056)
(2.205,-27.896)
(-29.513,25.726)
(-14.171,20.143)
(4.914,-43.933)
(-8.032,23.612)
(-10.355,16.436)
(-18.212,-47.131)

I gdy tworze na tym prostokąt i potem próbuję go odwzorować na układzie 2 (czyli tylko przesunietym) czyli probuje cofnac obrot (tj obracam dalej o 2pi - rad obrotu) to wychodzi jakis maly i nie pokrywa wszystkich punktow.

Jakies sugestie?

0

Najprościej losujesz prostokąt:

ten cienki.
Wyznaczasz kierunki aby byli "w kółko" - czyli strzałki.
Przesuwasz każdy z czterech odcinków do najdalszego po lewej.

W oznaczeniach:
Ax,Ay - współrzędne punktu A
Bx,By - współrzędne punktu B
itp

Dowolne czworoboki na losowych punktach i liczenie objętości

_13th_Dragon napisał(a):

1 użytkowników online, w tym zalogowanych: 0, gości: 1

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami