Kruising tussen twee curven

Ik moet de kruising van twee bochten krijgen. Het probleem waarmee ik geconfronteerd word, kan op de volgende manier worden verklaard:

Gegeven twee curven C1 en C2, gedefinieerd door N1 en N2 punten verbonden door rechte lijnen, verkrijg alle snijpunten van C1 met C2. Beide curven snijden zichzelf niet.

Ik heb verschillende benaderingen geprobeerd, maar geen lijkt tot nu toe te werken. Enig idee?

1
@ewok: als natuurkundestudent zou ik geneigd kunnen zijn om te zeggen dat programmeren gewoon wiskunde is ... dit is een numeriek algoritme, dus het kan als een programmeervraag worden beschouwd. Het is geen huiswerk, maar om meer opmerkingen hierover te voorkomen, heb ik de tag toegevoegd.
toegevoegd de auteur Jorge Leitão, de bron
@ewok Ok, ik ben het ermee eens, is een subset. Mijn punt is dat math.stack voornamelijk voor wiskunde is, en ik geloof dat de vraag gemakkelijker kan worden beantwoord door mensen die computeralgoritmen programmeren en kennen dan mensen die wiskunde doen.
toegevoegd de auteur Jorge Leitão, de bron
Dit lijkt meer op een wiskundeprobleem dan een programmeerprobleem en zou daarom van het onderwerp af zijn. als het een programmeerprobleem is, vertel ons dan welke taal en plaats elke code die u heeft.
toegevoegd de auteur ewok, de bron
En als dit huiswerk is, label het dan als zodanig.
toegevoegd de auteur ewok, de bron
Als het geen huiswerk is, is het label niet nodig. Ik zou aanraden een opmerking toe te voegen in de vraag dat het geen huiswerk is. die tag kan voorkomen dat sommige mensen eenduidige antwoorden geven.
toegevoegd de auteur ewok, de bron
Ik zou ook willen zeggen dat programmeren een subset van wiskunde is, in plaats van hetzelfde te zijn als wiskunde. als dit te maken heeft met een algoritme dat moet worden geïmplementeerd in code, dan is het prima, maar als het simpelweg is "wat is de wiskundige manier om dit probleem op te lossen", dan denk ik dat het bij math.stackexchange.com . Waarom zijn anders 2 verschillende sites?
toegevoegd de auteur ewok, de bron
@ewok algoritme vragen worden hier ondersteund, er zijn talloze voorbeelden van meer wiskundige vragen dan deze.
toegevoegd de auteur Codie CodeMonkey, de bron

2 antwoord

De eenvoudigste manier is om alle paren segmenten te testen, één uit elke curve. Als dat te langzaam is, probeer dan een stripboom . Het onderstaande papier is te vinden op de website van de auteur .

Ballard, D. H. (1981), Strookbomen: een hiërarchische weergave voor   curves, communicatie van de ACM, v.24 n.5,310-321

1
toegevoegd
heel leuk artikel. Bedankt!
toegevoegd de auteur Jorge Leitão, de bron

Omdat uw curven bestaan ​​uit lijnsegmenten, zou ik willen voorstellen een ruimtelijke structuur te gebruiken (bijv. Een quadtree ) om alleen segmenten te controleren die zich dicht bij elkaar bevinden. Dit zal de complexiteit van uw algoritme verminderen van O (N1 N2) naar O (N log N) (waarbij N = N1 + N2 ) , ervan uitgaande dat het aantal zeer nauwe kruispunten klein is.

Anders dan dat, kunt u kruispunten vinden in deze manier .

0
toegevoegd
Quadtree is een goede tip; lijnen kunnen overal worden onderschept, en hier hebben we te maken met segmenten.
toegevoegd de auteur Jorge Leitão, de bron