[JAVA] Afstand punt - bézier curve

[Nephilim]

Voor een project @ stage heb ik een aantal Bézier curven. Deze worden aangemaakt door (parameters even weggelaten):

Java:

// pad clearen
gPath.reset();
// beginpunt instellen
gPath.moveTo();
// controlepunten en eindpunt instellen
gPath.curveTo();

Wanneer er nu ergens geklikt wordt, wil ik kunnen bepalen of er al dan niet op een curve geklikt is, en zo ja .. op dewelke.

Hiervoor zou ik dan kijken of er curven liggen in een radius van 5px van het punt waar geklikt werd, door naar de bounding box (getRectangle()) te kijken. Is dit er 0 of 1, dan is er geen probleem. Zijn dit er meerdere, dan moet ik de afstand van elk van die curven tot het punt kunnen berekenen.

Hiervoor heb ik deze pdf gevonden, maar echt goed snappen doe ik het toch niet. Na hier wat rondgevraagd te hebben, blijkt dat ik voor elk punt van die curve de afstand tot het punt zou moeten berekenen, zodat ik de kortste afstand van die curve tot het punt weet. Vervolgens kan ik zien welke curve de kortste afstand tot het punt heeft.

Mijn vraag (in tegenstelling tot het antwoord) is dan ook simpel: op welke manier kom ik te weten op welke curve geklikt is?

[Janoz]

Sorry, maar ik ga je probleem nog iets moeilijker maken ipv oplossen .

Wat doe je in de volgende situatie?

code:

     _
      \
       |
      /
\    +      
 \        /
  \______/

+ is de positie waar wordt gedrukt. Intuitief zal de gebruiker denken dat de bovenste curve wordt geselecteerd, maar de muisklik valt alleen maar binnen de boundingbox van de onderste curve en deze zal dan ook worden geselecteerd.

[Nephilim]

In dat geval: als de klik binnen de boundig box + 5px gebeurt en de curve zelf ligt ook binnen 5px (normaal wel denk ik), wordt de bovenste genomen. Anders wordt er niet gereageerd omdat de onderste curve er meer dan 5px vandaan ligt.

[Janoz]

Ah ok .. Dan is het goed.

De afstand tot de bezier curve is een minimalisatie probleem (maar dat had je waarschijnlijk zelf ook al wel verwacht. In principe kun je de functie herschrijven tot een afstands tot je klikpunt functie en deze vervolgens kijken of deze <5 wordt. De oplossing in je pdf-je is een numerieke. Dit wil zeggen dat net zo lang wordt gegokt todat het antwoord acceptabel is .

Misschien is het handiger en efficienter om het over een compleet andere boeg te gooien. Waarom maak je geen masker? Maak naast je beeld ook een buffer met dezelfde of lagere resolutie en teken hierin ook de bezier curves. Zorg dat elke curve in die buffer uniek te identificeren is door elk curve in de extra buffer in een unieke kleur te tekenen. Wil je dat ze tot 5px naast de curve kunnen drukken, teken deze dan 10px dikker (afhankelijk van de resolutie van de buffer). Zodra iemand ergens klikt zoek je het bijbehorende punt op in de extra buffer. Kijkt wat de waarde is en je weet op welke curve is gedrukt.

Dit kost mischien een beetje extra geheugen, maar zal altijd veel sneller zijn dan het uitrekenen van de afstand tot een curve.

[MSalters]

De laatste oplossing werkt niet, als twee curves dichter dan 20 pixels bij elkaar liggen en ze dus overlappen. Dan kies je in het overlappende gebied de laatst getekende curve, ipv de dichtsbijzijnde.
Een alternatieve oplossing is in een aparte buffer een segmentatie maken. Teken alle curves met waarde 0, achtergrond heeft waarde MAX(bv 2^16). Vervolgens geef je in een loopje elk punt met waarde MAX dat grenst aan een punt met waarde i de waarde i+1, totdat alle punten een waarde <MAX hebben. Het resultaat is dat elk punt of de waarde 0 heeft (op curve), of een waarde >0. In het laatste geval is er tenminste een buurpixel met waarde i-1.

Als je vervolgens op punt x,y klikt bepaal je de waarde i. i=0 betekent dat je een curve hebt gevonden, zoniet dan zoek je bij de buurpixels naar de kleinste waarde. Herhaal totdat je een punt met i==0 hebt gevonden.

[Soultaker]

Als je met een beperkte straal (van, zeg, 10 pixels) om de curve heen werkt, is Janoz' methode wel heel goed te doen, door simpelweg eerst de versie met 10 pixels te tekenen, daarna die met 9, 8, 7, etcetera, tot en met 1. Hierdoor correspondeert de kleur van elke pixel in je masker met de dichtstbijzijnde curve.

Dit lijkt me trouwens een vrij lompe methode, het lijkt me netter om een algoritme te zoeken dat echt de afstand tot de curven berekend. Dan hoef je niet elke keer je masker opnieuw op te bouwens als je inzoomed, roteert, etcetera. Je kunt sowieso beginnen met de bounding box van de curven met als extra rand je marge (die 10 pixels bijvoorbeeld) en alleen die curven beschouwen waarvan het aangeklikte punt binnen de bounding box ligt. Ik denk dat je (afhankelijk van het soort 'tekening' dat je hebt) dan minder dan 10 curven over hebt om uit te kiezen.

Vervolgens kun je je curven gaan opbreken in twee delen en van elk de bounding box met marge nemen. Je hebt nu een vergelijkbare situatie: weer vallen een aantal delen af en die hoef je verder niet meer te beschouwen. Dit proces kun je herhalen tot je uitsluitend delen van dezelfde curve overhoud. In theorie kan dit erg lang duren maar het is erg afhankelijk van de 'curvedichtheid', dus in de praktijk denk ik dat het heel erg meevalt.

Uiteraard kan het ook voorkomen dat je aangeklikte punt niet in een bounding box ligt; dan is er schijnbaar geen curve aangeklikt. Hoe je het probleem oplost als je de dichtstbijzijnde curve wilt hebben, zou ik niet zo 1-2-3 weten. Het opdelen van je curve is ook niet triviaal, maar dat mag je mooi zelf bedenken.

[hobbit_be]

wat je best doet is je bezier effe opdelen in segmenten van een minimum afstand ,
(je kunt dit voor elke dimensie doen bijvoorbeeld)
dan gebruik je de lijnstukken voor de afstands bepaling (wat triviaal is).

Puur mathematisch is natuurlijk beter - ipv van een bounding box kun je veel beter een Bounding circle gebruiken - is meestal acuurater en sneller voor een kwik (snelle) check.

[.oisyn]

Je kunt de curve ook extruden naar een (concave) polygoon, en dan gewoon met een simpele punt-in-polygoon check controleren of de cursor zich in de buurt van een curve bevindt