Algoritmo per generare il percorso parallelo all'interno del poligono

0

Un percorso è definito come un elenco di punti 2D (x, y) (e potrebbe essere aperto o chiuso).

Dato un percorso p, che cos'è un algoritmo che genera un percorso p 'che è "dentro" p e con offset costante a p cioè ogni segmento di linea di p' è parallelo al segmento di linea corrispondente di p.

    
posta Robert Onslow 01.05.2015 - 15:39
fonte

3 risposte

1

Non conosco un algoritmo formale. L'ho implementato molto tempo fa. L'algoritmo dipende non solo dall'enumerazione dei segmenti di linea, ma anche dal "lato" dei segmenti di linea che il percorso parallelo deve seguire. Supponi di conoscere il "lato".

Il mio insieme di segmenti di linea era (come descrivi) un elenco di 2 punti (x, y).

  1. Per ogni punto p , ho guardato i due vettori formati usando il suo punti precedenti e successivi nell'enumerazione.
  2. Ho trovato l'angolo tra questi due vettori utilizzando un prodotto punto
  3. Ho diviso quell'angolo a metà, facendo un terzo vettore che ha bisecato i primi due. (Qui è dove sapere "quale lato del percorso" entra)
  4. Impostando la grandezza di questo terzo vettore sullo "scostamento costante", si ottiene un punto p' sul "percorso parallelo" che corrisponde al punto p
  5. Per i punti finali di un percorso che non è chiuso, ho semplicemente usato l'offset costante per impostare la grandezza di un vettore perpendicolare al vettore formato dal punto finale e dal suo punto vicino.
risposta data 01.05.2015 - 18:03
fonte
1

Bene, questa risulta essere un'estensione non banale della soluzione di Veldaeven.

Per ogni sequenza di 3 punti, calcola i 2 vettori tra di loro, come suggerito da Veldaeven.

Trova l'angolo tra i due vettori aggiungendo gli angoli dall'asse x - (nb non utilizzare il prodotto punto che restituisce sempre un angolo inferiore a pi e quindi è troppo simmetrico per il nostro problema).

Dimezza questo angolo. Questa è la bisettrice perpendicolare lungo la quale giace il vettore risultante.

Ora per calcolare quale quadrante disegnare il punto in (il problema "quale lato"). Trova la differenza tra i 2 vettori. Se il gradiente di questo (cioè la "derivata doppia") è positivo, il percorso ritorna su se stesso per un massimo: aggiungi pi / 2. Se il gradiente è negativo, il percorso passa attraverso un minimo: sottrarre pi / 2

innerWallClockwise :: Float -> V2 Float -> [Point V2 Float] -> [V2 Float]

innerWallClockwise w acc (p : p' : p'' : ps) = 

 let v = p' .-. p
  v' = p'' .-. p'
  d2v = v' .-. v
  phi = atan2 (v ^. _y) (v ^. _x)
  rho = atan2 (v' ^. _y) (v' ^. _x)
  theta = phi + rho
  d2vtheta = atan2 (d2v ^. _y) (d2v ^. _x)

  theta' = theta / 2 + if d2vtheta > 0 then pi / 2 else (-1) * pi / 2
  v''' = w *^ angle theta'
  v'''' = acc .+^ v'''
in
  if ps == [] then [v''''] else v'''' : (innerWallClockwise w (acc .+^ v') (p' : p'' : (head ps) : (tail ps)))

Diamo un semplice percorso rettangolare

let path=[P (V2 0 0), P(V2 0 5), P(V2 5 5), P (V2 5 (-5)), P (V2 0 (-5))]

Prova la nostra funzione:

innerWallClockwise 1 (V2 0 5) path

=> [V2 0.70710677 4.2928934,V2 4.2928934 4.2928934,V2 4.2928934 (-4.2928934)]

Sì, i punti sono tutti all'interno del percorso di input a una distanza di sqrt (2) dal vertice.

NB: tutti i metodi che utilizzano ad es. il prodotto incrociato dei due vettori è troppo simmetrico.

Speriamo che questo possa aiutare qualcuno in futuro.

    
risposta data 22.05.2015 - 22:39
fonte
0

Credo che tu stia cercando un poligono offset.

Questo post di stackoverflow descrive in dettaglio gli approcci al problema.

    
risposta data 25.10.2016 - 21:01
fonte

Leggi altre domande sui tag