Cześć,

Trójkąt opisany jest za pomocą trzech wierzchołków. Każde dwa
wierzchołki tworzą krawędź. Posiadam zbiór takich trójkątów gdzie każdy
ma co najmniej jedną wspólną krawędź z innym trójkątem ze zbioru.
Zakładając że kształt na płaszczyźnie który tworzą nie musi być wypukły,
jak znaleźć te krawędzie które tworzą obrys kształtu?

Jeżeli niejasno opisałem problem to stworzę ilustrację.

--
Pozdrawiam,
Mateusz Bogusz

do góry

W dniu 01.12.2016 o 19:28, Mateusz Bogusz pisze:
> Cześć,
>
> Trójkąt opisany jest za pomocą trzech wierzchołków. Każde dwa
> wierzchołki tworzą krawędź. Posiadam zbiór takich trójkątów gdzie każdy
> ma co najmniej jedną wspólną krawędź z innym trójkątem ze zbioru.
> Zakładając że kształt na płaszczyźnie który tworzą nie musi być wypukły,
> jak znaleźć te krawędzie które tworzą obrys kształtu?
>
> Jeżeli niejasno opisałem problem to stworzę ilustrację.
>
Może coś w rodzaju Weilera - Athertona?
http://pilat.free.fr/english/pdf/weiler.pdf
http://stackoverflow.com/questions/2667748/how-do-i-
combine-complex-polygons
albo wypukła otoczka
https://pl.wikipedia.org/wiki/Algorytm_Grahama
http://www.algorytm.org/geometria-obliczeniowa/znajd
owanie-wypuklej-otoczki-algorytm-grahama.html

do góry

> wypukła otoczka
> https://pl.wikipedia.org/wiki/Algorytm_Grahama
> http://www.algorytm.org/geometria-obliczeniowa/znajd
owanie-wypuklej-otoczki-algorytm-grahama.html

O, to będzie to! Co prawda punkty mam w 3D, ale już wiem od czego
zacząć. Dzięki :-)

--
Pozdrawiam,
Mateusz Bogusz

do góry

On 01.12.2016 20:39, Mateusz Bogusz wrote:
>> wypukła otoczka
>> https://pl.wikipedia.org/wiki/Algorytm_Grahama
>> http://www.algorytm.org/geometria-obliczeniowa/znajd
owanie-wypuklej-otoczki-algorytm-grahama.html
>>
>
> O, to będzie to!

Przecież wyraźnei pisałeś, że Twój obiekt nie musi być wypukły.

Zamiast obrysu rogalika dostaniesz koło ze spłaszczonym fragmentem.


Raczej policz, ile razy każda kawędź występuje.
Jeśli nalyży do 2 trójkątów, to jst w środku, jeśli do jednego,
to jest obrysem.

W ten sposób uzyskasz też obrysy dziur, to może być
dobrze, źle, albo obojętnie (bo dziur nie będzie),
zależy, co chcesz osiągnać;-)

> Co prawda punkty mam w 3D, ale już wiem od czego
> zacząć. Dzięki :-)


To i tak pewnie interesuje Cię nie obrys, a obrys
rzutu na płaszczyznę (rzutnię).
A wtedy np obrysem kuli (która brzegu nie ma)
powinien być okrąg.

To akurat niewielki problem, wysatrczy zignorować trójkąty
ustawione 'w złą stronę' względem keirunku rzutowania.

pzdr
bartekltg

do góry

W dniu czwartek, 1 grudnia 2016 20:28:16 UTC+2 użytkownik Mateusz Bogusz napisał:
> Cześć,
>
> Trójkąt opisany jest za pomocą trzech wierzchołków. Każde dwa
> wierzchołki tworzą krawędź.
[...]
> Jeżeli niejasno opisałem problem to stworzę ilustrację.
>
> --
> Pozdrawiam,
> Mateusz Bogusz

Witam,

Dawno, dawno temu napisałem dla mojego dziecka skrypt w Perlu, który generował siatki
"statków kosmicznych" do wycięcia i sklejenia. Przykładowe siatki można obejrzeć na
mojej stronie:

http://www.pawelbiernacki.net/4kids/cutandfold/space
ship_notex/index_pl.jsp

(Za każdym wejściem pokazuje losowo jeden z dwudziestu statków).

Potem ten kod trochę posprzątałem i umieściłem na githubie:

https://github.com/pawelbiernacki/Games-LatticeGener
ator.git

Ciekawy jest dlatego, że z Perla używa Prologu, a Prolog jest wykorzystywany do
reprezentowania obiektów geometrycznych za pomocą faktów. Chciałbym polecić Ci to
podejście. Dla opisywanego przez Ciebie problemu będziemy mieli np. dwa trójkąty:

jest_punktem(a).
jest_punktem(b).
jest_punktem(c).
jest_punktem(d).
jest_odcinkiem(ab).
jest_odcinkiem(bc).
jest_odcinkiem(ca).
jest_odcinkiem(bd).
jest_odcinkiem(cd).
nalezy_do(a,ab).
nalezy_do(b,ab).
....
nalezy_do(ab,abc).
jest_trojkatem(abc).


I tak dalej. Szukamy krawędzi, które należą jednego tylko trójkąta, ale można ten
sposób programowania wykorzystać bardziej finezyjnie, np. od zadanego punktu obrzeża
iterować po krawędziach obrzeża i dodawać wiedzę o tym, które punkty już przeszliśmy.

Pozdrawiam,
Paweł Biernacki

do góry