Polygon lijnen kruisen

[ZeroXT]

Beste mensen,

Ik wil gebruikers een polygon laten maken door het teken van lijnen in een afbeelding. Maar de lijnen mogen elkaar niet kruisen:

Goed:


Fout:


Ik doe dit met Javascript, maar de taal zou niets uit moeten maken. Ik bouw een array op met de top en left positie:

JavaScript:

var objects = 
[
    [28, 47],
    [50, 47],
    etc.
];

Hoe kan ik detecteren of een lijn een andere lijn kruist?

[Hydra]

En googlen op line intersection javascript leverde je niks op?

[UltimateB]

Mja google leverde wel wat op ;p

http://stackoverflow.com/...rsect-javascript-function

[Soultaker]

Paarsgewijs lijnsegmenten tegen elkaar checken lijkt me het makkelijkste (niet superefficiënt, maar voor handgetekende polygonen efficiënt genoeg, want die kunnen nooit uit veel segmenten bestaan).

Pas op met bijzondere gevallen: eindpunten van segmenten mogen elkaar ook niet raken, tenzij die segmenten direct aan elkaar grenzen (het makkelijkst is om aanliggende segmenten helemaal niet tegen elkaar te checken, want die kunnen toch niet kruisen). Een eindpunt mag een lijnstuk waarschijnlijk ook niet raken. En parallelle lijnstukken mogen niet overlappen. (Veel standaardfuncties voor intersectie-algoritmen onderscheiden die situaties niet.)

[.oisyn]

Soultaker schreef op maandag 21 oktober 2013 @ 23:05:
(het makkelijkst is om aanliggende segmenten helemaal niet tegen elkaar te checken, want die kunnen toch niet kruisen)

Ze kunnen elkaar wel overlappen though

[R4gnax]

ZeroXT schreef op zondag 20 oktober 2013 @ 20:23:
Hoe kan ik detecteren of een lijn een andere lijn kruist?

Zoek het Shamos-Hoey algoritme eens op. Dat heeft O(n log n) looptijd en kan gebruikt worden om te detecteren of een polygon een simpel polygon is, wat wil zeggen dat het geen zichzelf kruisende zijden heeft.

[PrisonerOfPain]

R4gnax schreef op dinsdag 22 oktober 2013 @ 01:32:
[...]


Zoek het Shamos-Hoey algoritme eens op. Dat heeft O(n log n) looptijd en kan gebruikt worden om te detecteren of een polygon een simpel polygon is, wat wil zeggen dat het geen zichzelf kruisende zijden heeft.

Niet getest maar volgens mij kun je makkelijk bij het toevoegen van ieder lijn segment kijken of 'ie met alle andere intersect in O(n).

C:

float fake2dcross(vec2 a, vec2 b)
{
     return a.x * b.y - a.y * b.x;
}

// start vecs are positions
// dir vecs are non-normalized directional vectors such stat start + dir = end

bool intersect(vec2 start1, vec2 dir1, vec2 start2, vec2 dir2)
{
    vec2 dist = start2 - start1;
    float c = 1.f / fake2dcross(dir1, dir2);
    float t = fake2dcross(dist, dir2) * c;
    float u = fake2dcross(dist, dir1) * c;

   return between(t, 0, 1) & between(u, 0, 1);
} 

En dan voor iedere lijn die je tekent de intersectie testen.

[HuHu]

.oisyn schreef op maandag 21 oktober 2013 @ 23:24:
[...]

Ze kunnen elkaar wel overlappen though

Maar dan kruisen ze niet