I’m trying to make an application that merge user free hand drawings, like lasso tool add mode in photoshop.
I tried to find the algorithms but I failed it (https://www.sciencedirect.com/topics/mathematics/simple-polygon I found this one but free hand drawing can be none simple-polygon.)
Below is how I tried to implement with flutter
-
get points and check it is clockwise. if it is, make it anti clock wise.
-
get intersect of two points.
-
combine paths and get pathmetrics
-
if computed pathmetrics is more than one, think it as it has hole and separate it (*this is wrong. there can be more than on pathmetric even if there’s no hole. for example making infinite(8) shape.)
-
sort two lines in one
-
return list with contour and interior
But as you can see, this has a lot of problem. Even I ignore pathmetrics problem, it sometimes give wrong points.
What I want to do is making application like this.
as user selected area in free hand drawing,
user can add over it and make in in one polygon => merge. (list with contour and iterior).
How can I deal this? As there are many painting tools, I thought there would be algorithm related to lasso tool add mode but I couldn’t find any.
+) I found this point but I’m more focusing at merge two points list. Algorithm to implement a lasso selection tool?
import 'dart:ui';
import 'package:label_up_study/labeling/model/drawing.dart';
import 'package:label_up_study/labeling/model/labeling_drawing.dart';
import 'package:vector_math/vector_math.dart' as vector;
const threshold = 1e-10;
class ObjectMerge {
List<LabelingDrawing> getMergedObject(
List<LabelingDrawing> labelingDrawings, Drawing drawing) {
if (labelingDrawings.length == 1) {
final List<Offset> labelingDrawingPoints = getPoints(labelingDrawings.first);
final List<Offset> drawingPoints = getPoints(drawing);
List<Offset> intersectList = [];
List<Offset> listA = !isClockWise(labelingDrawingPoints) ? labelingDrawingPoints : labelingDrawingPoints.reversed.toList();
List<Offset> listB = !isClockWise(drawingPoints) ? drawingPoints : drawingPoints.reversed.toList();
print('--- after clockwise check ---');
print('listA: $listA');
print('listB: $listB');
(listA, listB, intersectList) = getIntersectList(listA, listB);
final Path pathA = Path()..addPolygon(listA, true);
final Path pathB = Path()..addPolygon(listB, true);
if (intersectList.isEmpty) {
final Path intersectPath =
Path.combine(PathOperation.intersect, pathA, pathB);
if (arePointsContainedInPath(intersectPath, listB)) {
return [labelingDrawings.first];
} else if (arePointsContainedInPath(intersectPath, listA)) {
final LabelingDrawing labelingDrawing = labelingDrawings.first;
return [
LabelingDrawing(
id: labelingDrawing.id,
projectId: labelingDrawing.projectId,
labelingObjectId: labelingDrawing.labelingObjectId,
points: drawing.points,
isClose: labelingDrawing.isClose,
drawingMode: labelingDrawing.drawingMode)
];
} else {
final LabelingDrawing labelingDrawing = labelingDrawings.first;
return [
labelingDrawings.first,
LabelingDrawing(
id: labelingDrawing.id + 1,
projectId: labelingDrawing.projectId,
labelingObjectId: labelingDrawing.labelingObjectId,
points: drawing.points,
drawingMode: drawing.drawingMode,
isClose: true)
];
}
} else {
final List<PathMetric> pathMetrics =
Path.combine(PathOperation.union, pathA, pathB).computeMetrics().toList();
if (pathMetrics.length == 1) {
print('--- there is no hole ---');
(listA, listB, intersectList) =
deleteUnusingPoints(pathA, pathB, listA, listB, intersectList);
print('--- after deleteUnusingPoints ---');
print('listA: $listA');
print('listB: $listB');
final List<Offset> contourList =
sortContour(listA, listB, intersectList);
final LabelingDrawing labelingDrawing = labelingDrawings.first;
pathMetrics.clear();
return [
LabelingDrawing(
id: labelingDrawing.id,
projectId: labelingDrawing.projectId,
labelingObjectId: labelingDrawing.labelingObjectId,
points: contourList,
isClose: labelingDrawing.isClose,
drawingMode: DrawingMode.freeform)
];
} else {
print('--- there is a hole ---');
final List<LabelingDrawing> mergedList = [];
final LabelingDrawing labelingDrawing = labelingDrawings.first;
for (PathMetric metric in pathMetrics) {
if (metric.contourIndex == 0) {
continue;
}
print('--- catching up holes ${metric.contourIndex} ---');
final double metricLength = metric.length;
final Path extractPath = metric.extractPath(0, metricLength);
List<Offset> copylistA =
listA.where((e) => extractPath.contains(e)).toList();
List<Offset> copylistB =
listB.where((e) => extractPath.contains(e)).toList();
List<Offset> copyIntersect =
intersectList.where((e) => extractPath.contains(e)).toList();
final List<Offset> contourList =
sortContour(copylistA, copylistB, copyIntersect);
if (contourList.isNotEmpty){
mergedList.add(
LabelingDrawing(
id: labelingDrawing.id + metric.contourIndex + 1,
projectId: labelingDrawing.projectId,
labelingObjectId: labelingDrawing.labelingObjectId,
points: contourList,
isClose: true,
drawingMode: DrawingMode.freeform,
),
);
listA = listA.where((e) => !copylistA.contains(e)).toList();
listB = listB.where((e) => !copylistB.contains(e)).toList();
intersectList =
intersectList.where((e) => !contourList.contains(e)).toList();
}
}
print('--- base one ---');
(listA, listB, intersectList) =
deleteUnusingPoints(pathA, pathB, listA, listB, intersectList);
mergedList.insert(
0,
LabelingDrawing(
id: labelingDrawing.id + pathMetrics.length,
projectId: labelingDrawing.projectId,
labelingObjectId: labelingDrawing.labelingObjectId,
points: sortContour(listA, listB, intersectList),
isClose: true,
drawingMode: DrawingMode.freeform,
));
pathMetrics.clear();
return mergedList;
}
}
}
// for (int i=0 ; i<labelingDrawings.length; i++){
// print('$i list');
// print(labelingDrawings[i].points);
// }
return labelingDrawings;
}
bool isHole(Offset testPoint, List<Offset> points) {
if (points.isEmpty) {
return false;
}
return !isPointInPolygon(testPoint, points);
}
bool isPointInPolygon(Offset point, List<Offset> polygon) {
int intersections = 0;
for (int i = 0; i < polygon.length; i++) {
Offset a = polygon[i];
Offset b = polygon[(i + 1) % polygon.length];
if (rayIntersectsSegment(point, a, b)) {
intersections++;
}
}
return (intersections % 2) == 1;
}
bool rayIntersectsSegment(Offset point, Offset a, Offset b) {
double px = point.dx;
double py = point.dy;
double ax = a.dx;
double ay = a.dy;
double bx = b.dx;
double by = b.dy;
// Check if point is inside the segment's y-projection
if ((ay > py && by > py) || (ay < py && by < py) || (ax < px && bx < px)) {
return false;
}
// Check intersection with the ray
double slope = (by - ay) / (bx - ax);
double xIntersection = ax + (py - ay) / slope;
return xIntersection > px;
}
bool arePointsContainedInPath(Path path, List<Offset> points) {
for (Offset point in points) {
if (!path.contains(point)) {
return false;
}
}
return true;
}
List<Offset> getPoints(Drawing drawing) {
if (drawing.drawingMode == DrawingMode.square) {
final Offset firstPoint = drawing.points.first;
final Offset lastPoint = drawing.points.last;
return [
firstPoint,
Offset(lastPoint.dx, firstPoint.dy),
lastPoint,
Offset(firstPoint.dx, lastPoint.dy)
];
}
return drawing.points;
}
List<Offset> sortContour(
List<Offset> listA, List<Offset> listB, List<Offset> intersectList) {
bool state = false;
List<Offset> contour = [];
if (listA.isEmpty){
print('listA is empty');
return listB;
} if (listB.isEmpty){
print('listB is empty');
return listA;
}
List<Offset> copyListA = List.from(!isClockWise(listA) ? listA : listA.reversed.toList());
int frontA = 0;
List<Offset> copyListB = List.from(!isClockWise(listB) ? listB : listB.reversed.toList());
int frontB = 0;
List<Offset> currentQueue = [];
int frontCurr = -1;
print('--- in SortContour ---');
print('copyListA: $copyListA');
print('copyListB: $copyListB');
final Offset leftBottom = (copyListA + copyListB).reduce((a, b) {
if (a.dx < b.dx) {
return a;
} else if (a.dx == b.dx) {
if (a.dy > b.dy) {
return a;
} else {
return b;
}
} else {
return b;
}
});
if (listA.contains(leftBottom)) {
currentQueue = copyListA;
frontCurr = copyListA.indexOf(leftBottom);
state = true;
} else {
currentQueue = copyListB;
frontCurr = copyListB.indexOf(leftBottom);
}
while (true) {
if (currentQueue.isEmpty) {
if (state && copyListB.isNotEmpty) {
if (intersectList.length == 1) {
contour.add(intersectList.first);
}
currentQueue = copyListB;
frontCurr = frontB;
state = !state;
continue;
} else if (!state && copyListA.isNotEmpty) {
if (intersectList.length == 1) {
contour.add(intersectList.first);
}
currentQueue = copyListA;
frontCurr = frontA;
state = !state;
} else {
break;
}
}
// pop
frontCurr = frontCurr <= currentQueue.length - 1 ? frontCurr : 0;
Offset offset = currentQueue[frontCurr];
contour.add(offset);
currentQueue.removeAt(frontCurr);
// rearCurr = frontCurr > 0 ? frontCurr - 1 : currentQueue.length - 1;
// print('insert offset: $offset');
// print('');
if (intersectList.contains(offset)) {
if (state) {
frontA = frontCurr;
// rearA = rearCurr;
copyListA = List.from(currentQueue);
frontCurr = copyListB.indexOf(offset);
// rearCurr = rearB;
currentQueue = copyListB;
} else {
frontB = frontCurr;
// rearB = rearCurr;
copyListB = List.from(currentQueue);
frontCurr = copyListA.indexOf(offset);
// rearCurr = rearA;
currentQueue = copyListA;
}
currentQueue.removeAt(frontCurr);
// rearCurr = frontCurr > 0 ? frontCurr - 1 : currentQueue.length - 1;
state = !state;
}
}
print('contour: ${contour}');
return contour;
}
bool isClockWise(List<Offset> vertexList) {
Offset A = vertexList.reduce((a, b) {
if (a.dy < b.dy || (a.dy == b.dy && a.dx < b.dx)) {
return a;
} else {
return b;
}
});
final indexA = vertexList.indexOf(A);
int indexB = indexA - 1;
int indexC = indexA + 1;
if (indexB < 0) {
indexB = vertexList.length - 1;
}
if (indexC > vertexList.length - 1) {
indexC = 0;
}
final Offset B = vertexList[indexB];
final Offset C = vertexList[indexC];
final Offset AB = A - B;
vector.Vector2 vectorAB = vector.Vector2(AB.dx, AB.dy);
final Offset AC = C - A;
vector.Vector2 vectorAC = vector.Vector2(AC.dx, AC.dy);
final cross = vectorAB.cross(vectorAC);
if (cross > 0) {
return true;
} else if (cross < 0) {
return false;
} else {
if (A < C) {
return true;
// clock-wise
} else {
// anti-clockwise
return false;
}
}
}
(List<Offset>, List<Offset>, List<Offset>) deleteUnusingPoints(
Path path1,
Path path2,
List<Offset> listA,
List<Offset> listB,
List<Offset> intersectList) {
final List<Offset> copyListA = List.from(listA);
final List<Offset> copyListB = List.from(listB);
Path intersectPath = Path.combine(PathOperation.intersect, path1, path2);
Path differencePath = Path.combine(PathOperation.difference, path2, path1);
final delete = intersectList
.where((element) => intersectPath.contains(element) && !differencePath.contains(element))
.toList();
intersectList.removeWhere((element) => delete.contains(element));
copyListA.removeWhere((element) => delete.contains(element));
copyListB.removeWhere((element) => delete.contains(element));
for (int i = 0; i < listA.length; i++) {
if (path2.contains(listA[i]) && !listB.contains(listA[i])) {
copyListA.removeWhere((element) => element == listA[i]);
}
}
for (int i = 0; i < listB.length; i++) {
if (path1.contains(listB[i]) && !listA.contains(listB[i])) {
copyListB.removeWhere((element) => element == listB[i]);
}
}
return (copyListA, copyListB, intersectList);
}
(List<Offset>, List<Offset>, List<Offset>) getIntersectList(
List<Offset> listA, List<Offset> listB) {
final lengthA = listA.length;
final lengthB = listB.length;
final List<Offset> listA_1 = List.from(listA);
final List<Offset> listB_1 = List.from(listB);
final List<Offset> intersectList = [];
for (int i = 0; i < lengthA; i++) {
for (int j = 0; j < lengthB; j++) {
Offset? intersect = getIntersection(listA[i],
listA[((i + 1) % lengthA)], listB[j], listB[((j + 1) % lengthB)]);
if (intersect != null) {
insertIntersect(listA_1, listA[i], listA[((i + 1) % lengthA)],
listB[j], listB[((j + 1) % lengthB)], intersect);
insertIntersect(listB_1, listB[j], listB[((j + 1) % lengthB)],
listA[i], listA[((i + 1) % lengthA)], intersect);
intersectList.add(intersect!);
}
}
}
return (listA_1, listB_1, intersectList);
}
void insertIntersect(List<Offset> list, Offset A, Offset B, Offset C,
Offset D, Offset insert) {
final path = Path();
path.addPolygon(list, true);
if (list.contains(insert)) {
return;
}
int index1 = list.indexOf(A);
int index2 = list.indexOf(B);
int value = index2 - index1;
if (value.abs() == 1) {
list.insert(index1 + 1, insert);
} else if (value.abs() == (list.length - 1)) {
list.add(insert);
} else {
final lowPoint = index1 < index2 ? index1 : index2;
final highPoint = index1 > index2 ? index1 : index2;
value = value > 0 ? value : list.length - highPoint + lowPoint;
final insertIndex = findInsertIndex(list, value, index1, index2, C, D);
if (insertIndex >= 0) {
list.insert(insertIndex, insert);
}
}
}
int findInsertIndex(List<Offset> list, int loopLength, int startIndex,
int endIndex, Offset C, Offset D) {
int insertPoint = -1;
final listLength = list.length;
for (int i = 0; i < loopLength; i++) {
if (getIntersection(list[(startIndex + i) % listLength],
list[(startIndex + 1 + i) % listLength], C, D) !=
null) {
insertPoint = (startIndex + i) % listLength;
}
}
return insertPoint + 1;
}
Offset? getIntersection(Offset A, Offset B, Offset C, Offset D) {
final x1 = A.dx;
final x2 = B.dx;
final x3 = C.dx;
final x4 = D.dx;
final y1 = A.dy;
final y2 = B.dy;
final y3 = C.dy;
final y4 = D.dy;
final double denominator =
((x4 - x3) * (y2 - y1)) - ((y4 - y3) * (x2 - x1));
final double numeratorA = ((x4 - x3) * (y3 - y1)) - ((y4 - y3) * (x3 - x1));
final double numeratorB = ((x2 - x1) * (y3 - y1)) - ((y2 - y1) * (x3 - x1));
final double alpha = numeratorA / denominator;
final double beta = numeratorB / denominator;
if (0 <= denominator && denominator < threshold) {
return null;
} else if (alpha >= 0 && alpha <= 1 && beta >= 0 && beta <= 1) {
final x0 = x1 + alpha * (x2 - x1);
final y0 = y1 + alpha * (y2 - y1);
// print('x0: ${x0}, y0: ${y0}');
// print(Offset(x0, y0));
return Offset(x0, y0);
} else {
// print('no intersect');
return null;
}
}
}