Как да намерите ръбове и върхове на ръчно начертан многоъгълник

Бих искал да направя програма за разпознаване на форма, която да проследява мишка и да записва нейното местоположение на всяка 1/2 секунда. Как мога да използвам тези точки, за да намеря груб многоъгълник? С други думи, ако просто нарисувате фигура, наподобяваща триъгълник или квадрат, по-вероятно ще бъде 50-100-ъгълник, как мога да я опростя, за да получа формата, която се опитвах да нарисувам? Знам, че бихте могли да създадете генетичен алгоритъм, но не знам точно как ще работи това и бих искал да знам някакви алтернативи.

редактиране: изпъкнали корпуси няма да работят, необходимо е да се запази вдлъбнатината.


gesture-recognition algorithm image-recognition edges vertices
person invisible bob    schedule 04.06.2011    source източник

Отговори (2)


arrow_upward
1
arrow_downward

За всяка точка от 100-ъгълника намерете площта на малкия триъгълник, образуван от тази точка и точките от двете страни. Премахнете точката, която създава най-малкия триъгълник. Повторете, докато най-малкият триъгълник стане по-голям от някакъв праг.

person Fantius    schedule 04.06.2011
comment
Или повторете, докато най-малкият триъгълник стане по-голям от някакъв процент от площта на основната форма. - person Fantius; 04.06.2011
comment
кое би било по-ефективно, размер или ъглова мярка? - person invisible bob; 06.06.2011
comment
например за Pi в [P1, P2, P3 ... PN], премахнете точката, ако m∠p(i-1)p(i)p(i+1) › праг? - person invisible bob; 06.06.2011
comment
Не знам. Предполагам, че трябва да ги опитате и да видите. Предполагам, че размерът би бил по-ефективен, защото когато мишката се движи бавно и генерираните точки са близо една до друга, могат да възникнат големи промени в ъглите, въпреки че това не е реален ъгъл в планираната форма. - person Fantius; 06.06.2011
comment
но когато се движи по-бързо, триъгълниците стават по-големи, отколкото когато се движи бавно... почти имам ъглите, ще пробвам и двата. Може би хибридът ще работи най-добре? - person invisible bob; 08.06.2011
comment
Когато казвате по-голям, трябва да приема, че имате предвид по-дълъг. Но те също трябва да са много тънки. Така че площта все още трябва да е малка. - person Fantius; 08.06.2011
comment
Трябва да можете да създавате добри автоматизирани тестове за опитите си с алгоритъм. Бих направил това вместо субективно тестване на ръка. Например, можете да създадете масив от точки, който представлява перфектен триъгълник при различни скорости на мишката. Трябва да можете да се справите с идеалния случай добре (или перфектно), за да очаквате да се справите с по-трудни случаи. - person Fantius; 08.06.2011

arrow_upward
3
arrow_downward

ще пробвам.

  1. позволява да извикаме позицията, когато събитието с щракване на мишката надолу се случи точка START
  2. всеки интервал заема друга позиция, наречена CURR
  3. нека извикаме предишния CURR, PREV
  4. изчислете наклона (делта y/делта x) между CURR и PREV,
  5. изчислете наклона на линията между CURR и START
  6. дефинирайте някакъв праг за разлика между двата наклона
  7. if the slope crosses the threshold,
    1. store the line between START AND CURR as a SIDE
    2. дефинирайте CURR като нов START
  8. повторете, докато CURR е в определен радиус от първоначалния START или пресече една от предишните страни

може да успеете да определите формата просто като преброите страните.

person David Chan    schedule 04.06.2011
comment
Харесвам това решение, но мога да приема само един отговор, а другият е малко по-интуитивен, така че ще започна първо с него. - person invisible bob; 08.06.2011
comment
+1 IMHO, използването на наклони е много по-добро от изчисляването на триъгълни площи, като по-широко решение за отхвърляне на колинеарни точки, особено когато се работи с пикселни координати. - person mavrosxristoforos; 13.03.2016