Buon algoritmo per la determinazione di non convessa 2D figure di collisione

Question

potresti per favore fornirmi qualche informazione (o suggerire un articolo) sul buon algoritmo di rilevamento delle collisioni per il 2D non convesse cifre?

Grazie!

Answer 1

Prova questo:
http://www.cs.man.ac.uk/~toby/alan/software/
Si noti che non è gratuito per uso commerciale.

Per maggiori dettagli è possibile continuare a questa domanda simile:

Un semplice algoritmo per poligono intersezione

---

Per determinare se due semplici poligoni intersecano:

Se due poligoni semplici hanno un'intersezione non nulla, allora una delle seguenti accadrà:

A) Uno di loro ha un angolo interno l'interno dell'altro.
B) Uno di loro ha un intero bordo interno all'interno dell'altra (gli angoli di quel bordo non può essere necessariamente in interni). Ciò significa che la metà di quel bordo saranno dentro l'interno.
C) I poligoni sono identici.
D) Ci sono due bordi che si incrociano ad angolo. Il punto di intersezione non essendo un angolo qualsiasi poligoni.

Cosa deve fare è controllare se i poligoni sono identici (hanno gli stessi angoli), o uno degli angoli o una delle metà dei bordi si trova all'interno all'interno dell'altro poligono o se vi sono due spigoli intersect da qualche altra parte che in un angolo.

determinare se un punto giace all'interno di un poligono.

Answer 2

Ho sempre trovato le pagine di Wikipedia di essere molto utile per le mie esigenze:

Sutherland Hodgman

Liang Barsky

Weiler Atherton

Così come questo documento sull'algoritmo Weiler Atherton.