Er will aber nicht nur die beiden Schnittpunkte sondern alle Punkte innerhalb der Schnittfläche finden.

Insofern ist das Verfahren von jeffry das richtige. Will man alle Punkt finden, muss man einen Punkt nach dem anderen auf Gültigkeit nach der obigen Formel testen.
Eine Rechenzeitreduzierung könnte man durch eine grobbe Abschätzung erreichen, in welchem Bereich man suchen muss.